Skip to content
第4章

4.10 由遍历序列构造二叉树 ​

只有先序,定不出这棵树 ​

4.8节,给一棵树,能写出它的三种序列。反过来,给出序列,能不能把树画回来?

本节问题
一棵二叉树的先序序列是ABDEGCF,中序序列是DBGEACF。这棵树是什么样的?

先看只有一个序列行不行:

只给先序。先序是AB。B可以是A的左孩子,也可以是A的右孩子,两棵树的先序都是AB。先序只说谁先谁后,不说左右。

AB
先序AB
AB
先序也是AB

先序能告诉我们什么。先序是根、左、右,第一个一定是根。题目里先序的第一个是A,A就是根。

ABDEGCF根

中序能告诉我们什么。中序是左、根、右。知道了根是谁,在中序里找到它:左边的都在左子树,右边的都在右子树。

DBGEACF左根右

一个定根,一个分左右。两个序列合起来,就能把树画回来。

学完这一节,你能由先序和中序、或者后序和中序,画出唯一的一棵二叉树,并写出构造它的递归函数。

选中正文里的任意文字,就可以针对它发表评论