外观
4.10 由遍历序列构造二叉树
只有先序,定不出这棵树
4.8节,给一棵树,能写出它的三种序列。反过来,给出序列,能不能把树画回来?
本节问题一棵二叉树的先序序列是ABDEGCF,中序序列是DBGEACF。这棵树是什么样的?
先看只有一个序列行不行:
只给先序。先序是AB。B可以是A的左孩子,也可以是A的右孩子,两棵树的先序都是AB。先序只说谁先谁后,不说左右。
先序能告诉我们什么。先序是根、左、右,第一个一定是根。题目里先序的第一个是A,A就是根。
中序能告诉我们什么。中序是左、根、右。知道了根是谁,在中序里找到它:左边的都在左子树,右边的都在右子树。
一个定根,一个分左右。两个序列合起来,就能把树画回来。
学完这一节,你能由先序和中序、或者后序和中序,画出唯一的一棵二叉树,并写出构造它的递归函数。
第一步:先序定根,中序分左右
先处理整棵树:
先序定根。先序的第一个是A,A是根。
中序分左右。在中序里找到A。A左边是D、B、G、E,4个,都在左子树;右边是C、F,2个,都在右子树。灰色虚线框是还没拆开的子树。
先序也要切。左子树有4个结点。先序里A后面紧跟的4个,B、D、E、G,就是左子树的先序;剩下的C、F,是右子树的先序。
现在左子树有了自己的先序BDEG、中序DBGE;右子树有了先序CF、中序CF。每一边又是"一个先序加一个中序",和开头是同一个问题,只是变小了。
左子树:同样的事再做一遍
左子树的先序是BDEG,中序是DBGE:
定根B。先序BDEG的第一个是B,B是这棵子树的根。
分左右。在中序DBGE里找到B。左边只有D,右边是G、E。
切先序。左边1个,先序里B后面的1个D是左子树;剩下的E、G是右子树的先序。D只有一个结点,左子树就定了。
再拆EG。先序EG的第一个E是根。中序GE里,G在E的左边,E的右边没有结点。所以G是E的左孩子,E的右子树是空的。
右子树和整棵树
右子树CF。先序CF的第一个C是根。中序CF里,C的左边没有结点,右边是F。所以C的左子树是空的,F是C的右孩子。
验算。对画出来的树重新写先序、中序,得到ABDEGCF和DBGEACF,和题目给的一样。
回到本节问题。这棵树的根是A。A的左孩子是B,右孩子是C;B的左孩子是D,右孩子是E;E只有左孩子G;C只有右孩子F。
整个过程是交错进行的:先序定根,中序分左右,再按中序给的个数把先序切开,左右两边各自重复。每重复一次,问题就变小,一直小到只剩一个结点,或者是空的。这正是递归。
后序加中序
后序是左、右、根,根在最后一个。其余的做法不变。用同一棵树的后序DGEBFCA和中序DBGEACF:
后序定根。最后一个A是根。
中序分左右。和先序时一样:左边D、B、G、E,4个;右边C、F,2个。
切后序。后序是左、右、根:前4个D、G、E、B是左子树的后序,接着2个F、C是右子树的后序,最后是根。
往下同理。左子树的后序DGEB,最后的B是根;右子树的后序FC,最后的C是根。一路拆下去,得到的和先序加中序画出来的是同一棵树。
两种组合里,中序都少不了:只有它能分左右。先序、后序只负责定根,一个在最前,一个在最后。
写成函数
每一步做的事都一样,写成一个递归函数。参数要说清这一步拿的是哪一段:先序从第i个开始,中序从第j个开始,各取n个。下标从0开始:
c
/* 先序从pre[i]起、中序从in[j]起,各取n个,建出这棵子树 */
BiTree Build(char pre[], char in[], int i, int j, int n) {
if (n == 0) return NULL; /* 没有结点:空树 */
BiTNode *T = (BiTNode *)malloc(sizeof(BiTNode));
T->data = pre[i]; /* 先序的第一个是根 */
int k = 0;
while (in[j + k] != pre[i]) k++; /* 中序里找到根,左边有k个 */
T->lchild = Build(pre, in, i + 1, j, k); /* 左子树 */
T->rchild = Build(pre, in, i + 1 + k, j + k + 1, n - 1 - k); /* 右子树 */
return T;
}两次递归调用,就是切开的两段:
- 左子树:先序从根的下一个
i + 1开始,中序从j开始,各取k个。 - 右子树:先序跳过根和左子树,从
i + 1 + k开始;中序跳过左子树和根,从j + k + 1开始;剩下n - 1 - k个。
先建根,再建左右子树,这是4.8节的先序:先做自己,再做孩子。4.9节算属性用后序,要等孩子的答案;建树用先序,有了根,才能把孩子挂上去。
这个办法有个前提:结点的值各不相同。要是有两个A,在中序里就找不准根。
完整程序用本节的两个序列建树,再打印三种序列验算:
c
#include <stdio.h>
#include <stdlib.h>
typedef struct BiTNode {
char data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
/* 先序从pre[i]起、中序从in[j]起,各取n个,建出这棵子树 */
BiTree Build(char pre[], char in[], int i, int j, int n) {
if (n == 0) return NULL; /* 没有结点:空树 */
BiTNode *T = (BiTNode *)malloc(sizeof(BiTNode));
T->data = pre[i]; /* 先序的第一个是根 */
int k = 0;
while (in[j + k] != pre[i]) k++; /* 中序里找到根,左边有k个 */
T->lchild = Build(pre, in, i + 1, j, k); /* 左子树 */
T->rchild = Build(pre, in, i + 1 + k, j + k + 1, n - 1 - k); /* 右子树 */
return T;
}
void PreOrder(BiTree T) {
if (T == NULL) return;
printf("%c", T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
void InOrder(BiTree T) {
if (T == NULL) return;
InOrder(T->lchild);
printf("%c", T->data);
InOrder(T->rchild);
}
void PostOrder(BiTree T) {
if (T == NULL) return;
PostOrder(T->lchild);
PostOrder(T->rchild);
printf("%c", T->data);
}
void Destroy(BiTree T) {
if (T == NULL) return;
Destroy(T->lchild);
Destroy(T->rchild);
free(T);
}
int main(void) {
char pre[] = "ABDEGCF";
char in[] = "DBGEACF";
BiTree T = Build(pre, in, 0, 0, 7);
printf("先序:");
PreOrder(T);
printf("\n中序:");
InOrder(T);
printf("\n后序:");
PostOrder(T);
printf("\n");
Destroy(T);
return 0;
}text
先序:ABDEGCF
中序:DBGEACF
后序:DGEBFCA后序加中序的函数改三处:根取这一段后序的最后一个,post[i + n - 1];左子树的后序从i开始,右子树的后序从i + k开始。因为后序里根在最后,不占前面的位置。
练习1:先序加中序
填空
一棵二叉树的先序是ABCDEF,中序是CBDAEF:
- 根是
- 左子树的中序是
- 右子树的先序是
- 左子树的根是
先序第一个A是根。中序里A左边CBD是左子树,3个;右边EF是右子树。先序里A后面3个BCD是左子树的先序,第一个B是左子树的根;剩下的EF是右子树的先序。
练习2:后序加中序
填空
一棵二叉树的后序是DBECA,中序是BDAEC:
- 它的先序是
- 根的右孩子是
后序最后的A是根。中序里A左边BD、右边EC。后序前2个DB是左子树,B是根,中序BD里D在B右边;接着EC是右子树,C是根,中序EC里E在C左边。先序是ABDCE。
练习3:哪两个序列不够
单选
下面哪一组序列,不能唯一确定一棵二叉树?
A
先序和中序
先序定根,中序分左右,能唯一确定。
B
后序和中序
后序定根,中序分左右,能唯一确定。
C
先序和后序
两个都只能定根,没有一个能分左右。先序AB、后序BA,B在A的左边、右边都对。
D
三种组合都能唯一确定
先序加后序就不行,B在左在右都对得上。
关键是有没有一个序列能分左右:只有中序能。
到这里你有了由序列构造二叉树:先序(或后序)定根,中序分左右,再按中序给的个数把先序(或后序)切开,左右两边各自重复,交错往下,直到空。一定要有中序;先序加后序定不了左右。写成函数是先序:先建根,再建左右子树。下一步一段文字里,常用的字符用短编码。怎样的二叉树能让编码最短?