二叉树，返回预序遍历中的下一个节点

Question

我有一个任务，我需要一些方法的帮助。

所以我有一棵这样的树：

                A
              /   \
             B     C
           /   \ /   \
          D    E F     G
        /   \
       H      I
     /   \
   J       K

而我的方法是：

public BinaryTree preorderNext(BinaryTree t, BinaryTree v, BinaryTree prev) {       

    prev = t;

    if(t.getLeft() != null) {
        preorderNext(t.getLeft(), v, prev);
    }

    if(t.getRight() != null) {
        preorderNext(t.getRight(), v, prev);
    }


    if(prev == v) {
        return t;
    }

    return null;
}

讲师给出了树的一个简单实现。这个类叫做BinaryTree，如果您想让一个节点链接到它，那么您可以指定右子BinaryTree节点和左子BinaryTree节点。

一个节点有两个链接（一个指向左边，另一个指向右边的子节点），没有指向头部的链接。

因此，使用当前的方法，我能够成功地进行预购遍历，我通过编写存储在节点中的元素是什么的print语句进行测试。

但当我运行测试时，它告诉我A的下一个预排序节点是B，而K的下一个预排序节点抛出一个空异常，但应该是I？

你知道我错在哪里吗？变量prev应该包含对访问的最后一个节点的引用，所以如果它等于节点v（这是我指定的节点，以返回v之后的节点），难道我不应该得到下一个节点吗？

Answer 1

下面是如何递归完成预购遍历的实现。

public void preOrderTraversal(BinaryTree root){
    if(root == null) return;

    System.out.println(root);
    preOrderTraversal(root.getLeft());
    preOrderTraversal(root.getRight());
}

备注：

1. 我不确定你的做法；为什么要返回节点？在任何情况下，当根为null时，您可以使用该方法返回“emptyNode”并通过if语句处理它。
2. 正如您所看到的，我只处理根，根在任何级别都有更改。尝试用一个贯穿的方式将其可视化，您就会理解这个概念。
3. 在开头缺少对空节点的检查（特别是T)。

您可以继续使您的结果适应于此。

最后一个注意事项是这种方法的运行时复杂性，我强烈建议理解递归函数的运行时复杂性。以后会帮你大忙的。查看这篇维基百科文章寻找复发关系。