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

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.

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

非常感谢任何建议。提前致谢！

Answer 1

听起来作者有兴趣让您创建 class 如下：

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 class 的方法之后，我们得到：

           [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。

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

Why do we need fields for pre-, in- and post-order traversals in a Binary Tree subclass?

java

algorithm

tree

binary-tree

data-structures