java - 二叉树，在前序遍历中返回下一个节点

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 的右子节点和左子节点。

一个节点有两个链接(一个到左侧，另一个到右子节点)，并且没有到头的链接。

因此，使用当前方法，我能够成功进行前序遍历，我通过编写节点存储的元素的打印语句进行测试。

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

你知道我哪里出错了吗？变量 prev 应该保存对最后访问的节点的引用，因此如果它等于节点 v (这是我指定的节点，返回 v 之后的节点)，我不应该获取下一个节点吗？

Answer 1

我不确定递归执行该任务是否那么容易。

使用堆栈以迭代方式解决任务可能是更好的方法:

public BinaryTree preOrderNext(BinaryTree toSearch) {

    Stack<BinaryTree> openList = new Stack<BinaryTree>();

    openList.push(root);

    while (openList.empty() == false) {
        BinaryTree curr = openList.pop();

        if (curr.getRight() != null)
            openList.push(curr.getRight());

        if (curr.getLeft() != null)
            openList.push(curr.getLeft());

        if (curr.equals(toSearch) && openList.empty() == false){
            return openList.pop();
        }
    }
    return null;
}

此方法未经测试，但应该有效。