2

我了解算法，但不确定如何将其放入实际代码中。请帮忙！也请详细说明。除了复制答案之外，我真的很想了解这一点。;)

这是我的代码：

 public boolean getLeftChild(){
    Node insertNode = root;
    while(insertNode!=null){
        insertNode = insertNode.left;
    }
    return true;
}
public Boolean removeMin(){
    Node insertNode = root;
    Node parentNode =root;

        if (insertNode.left ==null){
            insertNode.right = parentNode;
            insertNode = null;

        }else if (getLeftChild() ==true && insertNode.right != null){
            insertNode.left = null;
        }else{
            parentNode.left = insertNode.right;

    }
        return true;
}
4

1 回答 1

0

首先要做的事情：对于树，我强烈推荐递归。

仅举一个例子：

getSmallestNode(Node node){
     if(node.left != null){
         return getSmallestNode(node.left)
     }

     return node;
}

对于删除，如果要删除二叉树的最小（因此是“最左叶”子节点），可能有两种情况。

情况1：叶子没有子节点，在这种情况下只需将父节点中的相应条目设置为null（mostLeftChild.getParent().left = null）

情况 2：叶子有一个右子节点（不能有左子节点，因为这意味着会有一个较小的节点并且您当前选择的节点不是最小的）在这种情况下，您将当前的左节点替换为右子树的最小节点mostLeftChild.getParent().left = getSmallestFromSubtree(mostLeftChild.right)

所以现在把它变成代码，它可能看起来像这样（不保证它真的有效）

public Node deleteSmallest(Node node){
    // haven't reached leaf yet
    if(node.left != null{
        return deleteSmallest(node.left)
    }

    // case 1, no child nodes
    if(node.right == null){
        node.getParent().left = null;
    } else { // case 2, right child node
        node.getParent().left = deleteSmallest(node.right)
    }

    return node;
}

你会用它来称呼它deleteSmallest(root)

于 2013-11-10T23:34:13.553 回答