如果其元素等于最大元素，如何删除整个节点

Question

如何删除 Binarytree 中的最大节点。如果其元素等于最大元素，我想删除整个节点。我可以 return 最大节点，但我不知道如何删除它。不在 BinarySearchTree 中。

public class MyLinkedBinaryTree extends LinkedBinaryTree {
MyLinkedBinaryTree() {
    super();
}

public void removeMax(BinaryTreeNode t, int i) {
    if ((int) t.element != i && t.rightChild != null && t.leftChild != null) {
        if (t.leftChild != null)
            removeMax(t.leftChild, i);
        if (t.rightChild != null)
            removeMax(t.rightChild, i);
    } else if ((int) root.element == i) {
        root = null;
    }
}

public int findMax(BinaryTreeNode t) {
    if (t == null)
        return 0;
    int res = (int) t.element;
    int lres = findMax(t.rightChild);
    int rres = findMax(t.leftChild);
    if (lres > res)
        res = lres;
    if (rres > res)
        res = rres;
    return res;
}

Answer 1

您是只想删除最大节点（并重新分支其 children）还是删除节点及其所有 children？

此外，节点应该可以访问其 children 但不能访问其根。您需要重构您的代码，以便能够删除 children 中的一个，如果它是您的目标（在您的情况下，如果我理解得很好，该节点具有最大的价值）。

Answer 2

一种方法是将 findMax 更改为 return，不是值，而是包含它的实际节点：

//DISCLAIMER: untested code
public BinaryTreeNode findMaxNode(BinaryTreeNode t) {
    if (t == null)
        return null;
    BinaryTreeNode max = t;
    BinaryTreeNode maxLeft = findMax(t.rightChild);
    BinaryTreeNode maxRight = findMax(t.leftChild);
    if (maxLeft!=null && maxLeft.element > t.element) {
        max = maxLeft;
    }
    if (maxRight !=null && maxRight .element > t.element) {
        max = maxRight ;
    }
    return max;
}

然后你必须弄清楚如何从树中删除该节点。我假设它的父节点有一个 link 。然后我们可以将它从它的父级中移除，从而将它从树中移除：

public void removeMax(BinaryTreeNode t) {
    if(t==null) return;
    BinaryTreeNode max = findMaxNode(t);
    //removing a node from its parent
    BinaryTreeNode parent = max.parent;
    if(parent==null) {
         //figure out what to do is the maximum value is at the root
    } else if(parent.leftChild==max) {
         parent.leftChild = null;
    } else if(parent.rightChild==max) {
         parent.rightChild = null;
    }
}

你需要弄清楚当根拥有最大值并且整棵树都被删除时要做什么。

如果您的节点没有对其父节点的引用，您必须将 findMaxNode 更新为 return 最大节点的父节点。

如果其元素等于最大元素，如何删除整个节点

How to delete entire Node if its element equals to maximum element

java

binary-tree