如何为给定节点 BST 查找后继节点

Question

我正在尝试构建一种算法来查找节点的后继节点，方法是递归调用以下内容：

public static BTreeNode inorderFirst(BTree T) {
BTreeNode n = T.getRoot();
if (n == null)
return null;
while (n.getLeftChild() != null)
n = n.getLeftChild();
return n;
}

并称其为"

public static BTreeNode inorderNext(BTreeNode n) {
//returns successor. if it finds one.
// TODO
// if node has a right child get its left descendant.
// otherwise get the first ancestor of which in the left sub-tree the node n is.
// if it didn't find
return null;
} // inorderNext()

我正在使用自定义导入，它具有获取getLeftChild()的方法，等等，也有不难弄清楚的getParent()。如果有人对如何开始构建它有任何想法。我补充了一些我自己的计划的评论。我只是不知道如何开始执行。我想要这个结构，因为它使测试方法更容易。 我想出了一种在不使用递归的情况下使其工作的方法：

public static BTreeNode inorderNext(BTreeNode n) {

if (n.getRightChild() != null) {
BTreeNode temp = n.getRightChild();
while (temp.getLeftChild() != null)
temp = temp.getLeftChild();
return temp;
}
else {
BTreeNode temp = n;
BTreeNode par = n.getParent();
while (par != null) {
if (par.getLeftChild() == temp)
return par;
else {
temp = par;
par = par.getParent();
}
}
}
return null;
} // inorderNext()

但我仍然想知道是否有办法在这个函数上递归使用第一个函数。

Answer 1

您的代码如下所示：

if(n.getLeftChild() != null)
        inorderNext(n.getLeftChild());
    System.out.print(n.data);
    if(n.getRightChild() != null)
        inorderNext(n.getRightChild());