时间戳

首页 > 解决方案 > 为什么我们需要在二叉树子类中进行前序、序中和后序遍历的字段？

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

问题描述

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

但是，我正在完成我遇到的练习，我真的不知道它在问什么。看看ODS 中的练习 6.7，内容如下：

练习 6..7 创建一个子类，BinaryTree其节点具有用于存储前序号、后序号和中序号的字段。编写递归方法preOrderNumber(),inOrderNumber()和postOrderNumbers()正确分配这些数字。这些方法都应该在 O(n) 时间内运行。

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

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

标签： javaalgorithmdata-structurestreebinary-tree

解决方案

听起来作者有兴趣让您创建以下类：

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

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

给定一个节点u，确定 的深度u。

通常，解决这个问题需要从根遍历到uO(n) 时间复杂度的树。但是作者解释说，给定一个预处理的，可以使用三个字段（和）在 O(1) 时间内LabeledNode推断节点的深度。upreOrderNuminOrderNumpostOrderNum

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

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

如需进一步说明，请查看您提出的问题上方的描述和图表。

推荐阅读