二叉树-已知先序或后续遍历和中序遍历求画出二叉树及后续或先序遍历

Author Avatar
itning 5月 04, 2018
  • 在其它设备中阅读本文章

二叉树有三种遍历方式:先序遍历,中序遍历,后续遍历

1.先序遍历

(1)访问根结点;

(2)先序遍历左子树;

(3)先序遍历右子树。

2.中序遍历

(1)中序遍历左子树;

(2)访问根结点;

(3)中序遍历右子树。

3.后序遍历

(1)后序遍历左子树;

(2)后序遍历右子树;

(3)访问根结点。

我们只要知道 先序中序或 后序中序 就能确定一棵二叉树 如果我们只知道 先序 后续 是无法确定一棵二叉树的

以 2009年上半年程序员上午试题38题为例

某二叉树的先序遍历序列为ABFCDE、中序遍历序列为BFADCE,则该二叉树根的左孩子和右孩子结点分别是(38)。

(38)A.B 和 F B.F 和 B C.B 和 C D.C 和 B

  1. 首先 题中给我们了 这棵二叉树 的先序序列和中序序列

  2. 通过先序序列 我们能够知道第一个字母是根节点 也就是 节点A 为 整个二叉树的根节点(因为先序序列首先访问的就是根节点)

  3. 通过中序序列 我们能够通过根节点A 判断二叉树的左子节点有BF 右子节点有DCE (因为根节点将整棵二叉树分为左右两边,可以通过中序序列来确定左右子树都有哪些节点)

  4. 这个时候我们可以先画出根节点及左右子树都有哪些节点

  5. 接下来我们看 先序序列 ABFCDE 把根节点去除 BFCDE 这个时候先序遍历是先访问根节点然后再访问左子树最后右子树.那么BFCDE 这个序列中的B 为 左子树的根节点.序列中去掉左子树的节点和根节点 还剩 CDE 这三个节点 那么C节点则为右子树的根节点(因为先序遍历是先访问根节点的,而C在序列的开头则C为右子树根节点)

  6. 现在我们知道了这棵二叉树的根节点和左子树,右子树的根节点,接下来就要确定左子树剩下的F节点是在左子树的左边还是右边

  7. 首先我们假设F节点在B节点的左侧

  8. 用先序序列ABFCDE验证:先访问根节点(A),先序遍历左子树(BF),左子树先访问根节点(B),再遍历左子树左节点(F).先序遍历看起来没问题,那么我们用中序序列BFADCE去验证下:首先访问左子树(BF),左子树中先访问左节点(F),再访问左子树根节点(B) 貌似不对 因为这样 中序遍历应该是以 FB开头 而不是 BF开头,那么将F节点放到B节点右侧

  9. 这回左子树就对了 先序遍历:先访问根节点A,再访问左子树,左子树先访问根节点B,然后要访问左节点,但是左节点没有,所以继续访问,访问右节点F. 中序遍历:先访问左子树,然后是左子树的左节点,依然为空,则继续访问左子树根节点B,然后访问左子树右节点F

  10. 用同样的方法可以确定右子树,右子树的根节点为C 中序遍历右子树为DCE 则 先访问右子树左节点D 然后访问右子树根节点C 最后访问右子树右节点E. 整个二叉树如图:

这道题正确答案为 C

原创内容,转载请注明出处!
本文链接:https://blog.itning.top/posts/DataStructure/20180504-Binary-Trees-Known-Preceding-or-Subsequent-Traversal-and-In-Order-Traversal-Finding-a-Binary-Tree-and-Follow-Up or-First-Order-Traversal.html