二叉树的遍历

三种深度优先遍历(递归)

  • 前序遍历(根左右):先访问根,再遍历左子树,最后遍历右子树
  • 中序遍历(左根右):先遍历左子树,再访问根,最后遍历右子树
  • 后序遍历(左右根):先遍历左子树,再遍历右子树,最后访问根
// 前序遍历
void PreOrder(BiTree T) {
    if (T != NULL) {
        visit(T);            // 访问根结点
        PreOrder(T->lchild); // 遍历左子树
        PreOrder(T->rchild); // 遍历右子树
    }
}

// 中序遍历
void InOrder(BiTree T) {
    if (T != NULL) {
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

// 后序遍历
void PostOrder(BiTree T) {
    if (T != NULL) {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
}

时间复杂度:O(n)O(n)(每个结点访问一次)。空间复杂度:最坏 O(n)O(n)(递归栈深度等于树高,最坏为链状)。

层序遍历

按层次从上到下、从左到右访问,需要借助队列实现:

void LevelOrder(BiTree T) {
    InitQueue(Q);
    EnQueue(Q, T);
    while (!QueueEmpty(Q)) {
        DeQueue(Q, p);
        visit(p);
        if (p->lchild != NULL) EnQueue(Q, p->lchild);
        if (p->rchild != NULL) EnQueue(Q, p->rchild);
    }
}

由遍历序列构造二叉树

  • 前序 + 中序:前序确定根,中序划分左右子树,递归构造
  • 后序 + 中序:后序确定根(最后一个),中序划分左右子树,递归构造
  • 前序 + 后序:不能唯一确定一棵二叉树

习题

习题 1

某二叉树的前序遍历序列为 A、B、C,后序遍历序列为 C、B、A,则中序遍历序列为( )

A. A、B、C B. C、B、A C. B、A、C D. 不能唯一确定

二叉树遍历前序遍历后序遍历中序遍历

解题思路:

本题考查由前序与后序序列能否唯一确定二叉树。关键在于这两种遍历都无法单独确定根的两棵子树各含哪些结点,必须借助中序序列中根的位置来划分左右子树,因此缺少中序序列时答案不唯一。

详细步骤:

  1. 前序序列的首元素是根,后序序列的末元素是根,两者的根一致,都为 A。
  2. 但前序与后序都只给出“根—左—右”和“左—右—根”的次序,无法指出剩余的 B、C 究竟属于左子树还是右子树。
  3. 例如把 BC 作为 A 的左子树时中序为 B、C、A;把 BC 作为 A 的右子树时中序为 A、B、C。
  4. 两种不同的二叉树都符合给定的前序与后序序列,故不能唯一确定。

最终答案:

D。

习题 2

已知某二叉树的中序遍历序列为 JGDHKBAELIMCF,后序遍历序列为 JGKHDBLMIEFCA,则其前序遍历序列为( )

A. ABDGHJKCEFILM B. ABDGJHKCEILMF C. ABDHKGJCEILMF D. ABDGJHKCEIMLF

二叉树遍历中序遍历后序遍历前序遍历

解题思路:

本题已知中序与后序序列,要求前序序列。思路是反复使用“后序末元素为根、中序中根的位置把序列切成左右两半”这一规律,递归确定每棵子树,再把各子树的前序序列拼接起来。

详细步骤:

  1. 第 1 步:确定根结点。后序遍历的最后一个元素是整棵树的根,即 A。
  2. 第 2 步:用中序序列划分左右子树。中序遍历为 JGDHKB | A | ELIMCF,所以左子树中序为 JGDHKB,右子树中序为 ELIMCF。
  3. 第 3 步:递归构造左子树。后序序列去掉根 A 后,左子树部分为 JGKHDB,其最后一个元素 B 是左子树的根;在左子树中序 JGDHKB 中 B 右边为空,所以 B 没有右子树,B 左边是 JGDHK。继续:JGDHK 对应后序 JGKHD,根为 D,中序中 D 左边是 JG、右边是 HK;JG 对应后序 JG,根为 G,中序中 G 右边是 J,所以 G 的左孩子为空、右孩子为 J,前序得到 ABDGJ;HK 对应后序 KH,根为 H,中序中 H 左边是 K,所以 H 的左孩子为 K、右孩子为空,前序追加得到 ABDGJHK。
  4. 第 4 步:递归构造右子树。右子树后序为 LMIEFC,最后一个元素 C 是右子树的根;在右子树中序 ELIMCF 中 C 右边为空、C 左边是 ELIMF。ELIMF 对应后序 LMIEF,根为 F,中序中 F 右边是 E、F 左边是 LIM;LIM 对应后序 LMI,根为 I,中序中 I 左边是 L、右边是 M,前序追加得到 CEILM;最后 F 的右孩子为 E,前序得到 CEILMF。
  5. 第 5 步:合并前序序列。前序遍历 = 根 + 左子树前序 + 右子树前序 = A + BDGJHK + CEILMF = ABDGJHKCEILMF,即选项 B。

最终答案:

B(ABDGJHKCEILMF)。

习题 3

二叉树的前序、中序、后序遍历顺序分别是什么?

前序遍历中序遍历后序遍历二叉树遍历

解题思路:

本题考查二叉树三种深度优先遍历的访问次序。思路是抓住三者唯一的差别——“访问根结点的时机”,其余部分都是“递归地先遍历左子树、再遍历右子树”。

详细步骤:

  1. 前序遍历(根左右):先访问根结点,再遍历左子树,最后遍历右子树。
  2. 中序遍历(左根右):先遍历左子树,再访问根结点,最后遍历右子树。
  3. 后序遍历(左右根):先遍历左子树,再遍历右子树,最后访问根结点。
  4. 三者的区别只在于访问根结点的时机:前序最先访问根,中序在中间访问根,后序最后访问根。

最终答案:

前序(根左右):先访问根,再遍历左子树,最后遍历右子树。中序(左根右):先遍历左子树,再访问根,最后遍历右子树。后序(左右根):先遍历左子树,再遍历右子树,最后访问根。三者的区别在于访问根结点的时机:前序最先访问根,中序在中间,后序最后。

发现内容有问题?

告诉我们哪里需要改进。