0

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

所以我有一棵这样的树：

                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 之后的节点），我不应该得到下一个节点吗？

4

3 回答 3

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;
}

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

于 2013-03-04T17:54:50.073 回答
0

这是 a 如何preorder traversal递归完成的实现。

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

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

笔记：

  1. 我不确定你的方法；你为什么要返回一个节点？在任何情况下，当root使用这种方法时，您可以返回一个 " emptyNode" 并通过 if 语句处理它。
  2. 如您所见，我只处理root, 任何级别的root更改。尝试通过贯穿来形象化这一点，您将理解这个概念。
  3. 您在开始时缺少对空节点的检查（尤其是对于t）。

您可以继续调整结果以适应此情况。

最后一点是关于这种方法的运行时复杂性，我强烈建议您了解递归函数的运行时复杂性。将来会对你有很大帮助。检查此维基百科文章以了解重复关系。

于 2013-03-04T17:23:26.397 回答
0

我提供了一个在O(h)运行时运行的答案。

class Node {
    public int key;
    public Node l;
    public Node r;
    public Node p;

    public Node(int key) {
        this.key = key;
        this.l = null;
        this.r = null;
        this.p = null;
    }
}

public Node preorderNext(Node v) {
    if (v.l != null) {
        return v.l;
    } else if (v.r != null) {
        return v.r;
    } else {
        while (v.p != null) {
            if (v == v.p.l) {
                if (v.p.r != null) {
                    return v.p.r;
                } else {
                    v = v.p;
                }
            } else {
                if (v.p.p == null) {
                    return null;
                } else if (v.p == v.p.p.l) {
                    if (v.p.p.r != null) {
                        return v.p.p.r;
                    } else {
                        v = v.p;
                    }
                } else {
                    v = v.p;
                }
            }
        }
        return null;
    }
}
于 2013-10-10T04:45:53.593 回答