BST：inOrder后代和前任 [英] BST : inOrder successor and predecessor

问题描述

他们看起来正确吗？我实现了它们，并且正在寻找它们。

 节点前身（Node node）{
 if（（node.left == null）&&（node.right == null））{
 return node; 
} 
 if（node.right！= null）{
 return前辈（node.right）; 
} 
 if（node.left！= null）{
 return前辈（node.left）; 
} 
} 
 
 
节点后继（节点节点）{
 if（（node.left == null）&& right == null））{
 return node; 
} 
 if（node.left！= null）{
 return successor（node.left）; 
} 
 if（node.right！= null）{
 return successor（node.right）; 
} 
} 
  

解决方案

否，他们是不正确的。
节点的前身不能在右边的子树中。
节点的后继不能在左子树中。

Do they look correct? I implemented them and was looking to review them

Node predecessor(Node node) {
    if ((node.left == null) && (node.right==null)) {
        return node;
    }
    if (node.right != null) {
        return predecessor(node.right);
    }
    if (node.left != null) {
        return predecessor(node.left);
    }
}


Node successor(Node node) {
    if ((node.left == null) && (node.right==null)) {
        return node;
    }
    if (node.left != null) {
        return successor(node.left);
    }
    if (node.right != null) {
        return successor(node.right);
    }
}

解决方案

No, they aren't correct. The predecessor of a node can't be in right subtree. The successor of a node can't be in left subtree.

这篇关于BST：inOrder后代和前任的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！