java - 为什么我们需要在二叉树子类中进行前序、中序和后序遍历的字段？

Question

我正在使用开放数据结构在线教科书自学二叉树相关内容。

但是，我正在完成练习，我真的不知道它在问什么。看看Exercise 6.7 in ODS ，内容如下:

Exercise 6..7 Create a subclass of BinaryTree whose nodes have fields for storing pre-order, post-order, and in-order numbers. Write recursive methods preOrderNumber(), inOrderNumber(), and postOrderNumbers() that assign these numbers correctly. These methods should each run in O(n) time.

我不是在这里寻求解决方案，我只是很难理解教科书的作者要求为这个特定练习做些什么。在我看来，应该使用前序、中序或后序来遍历，那么留一个字段来存储数字有什么用呢？事实上，我也对他指的是什么数字感到困惑。

在此非常感谢任何建议。提前致谢!

Answer 1

听起来作者有兴趣让您创建如下类:

class LabeledBinaryTree extends BinaryTree {
    void preOrderNumber();
    void inOrderNumber();
    void postOrderNumber();
}

和

class LabeledNode<T> extends Node<T> {
    T data;
    LabeledNode<T> left;
    LabeledNode<T> right;
    int preOrderNum;
    int inOrderNum;
    int postOrderNum;

    public LabeledNode(T data, LabeledNode<T> left, LabeledNode<T> right);
}

这一点与后续挑战有关，这些挑战要求您使用填充的订购号值来有效地解决更高级别的问题，例如

Given a node u, determine the depth of u.

通常，解决这个问题需要从根到 u 遍历树，时间复杂度为 O(n)。但是作者解释说，给定一个预处理的 LabeledNode，可以使用三个字段 ( >preOrderNum、inOrderNum 和 postOrderNum)。

至于数字本身，它们表示节点在规定的遍历中的位置。例如，如果我们有这样一棵树:

   [A]
  /   \
[B]   [C]
        \
        [D]

运行 LabeledBinaryTree 类的方法后，我们得到:

           [A pre=0,in=1,post=3]
              /              \
[B pre=1,in=0,post=0] [C pre=2,in=2,post=2]
                               \
                         [D pre=3,in=3,post=1]

因为遍历是

pre  => [A, B, C, D]
in   => [B, A, C, D]
post => [B, D, C, A]

如需进一步说明，请查看 description and diagram高于你提出的问题。