java如何为给定节点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());