第一二节 树及二叉树.

Presentation on theme: "第一二节 树及二叉树."— Presentation transcript:

1 第一二节 树及二叉树

2 简介 树是一种非线性的数据结构，用它能很好地描述有分支和层次特性的数据集合。树型结构在现实世界中广泛存在，如社会组织机构的组织关系图就可以用树型结构来表示。树在计算机领域中也有广泛应用，如在编译系统中，用树表示源程序的语法结构。在数据库系统中，树型结构是数据库层次模型的基础，也是各种索引和目录的主要组织形式。在许多算法中，常用树型结构描述问题的求解过程、所有解的状态和求解的对策等。在这些年的国内、国际信息学奥赛、大学生程序设计比赛等竞赛中，树型结构成为参赛者必备的知识之一，尤其是建立在树型结构基础之上的搜索算法。 在树型结构中，二叉树是最常用的结构，它的分支个数确定、又可以为空、并有良好的递归特性，特别适宜于程序设计，因此也常常将一般树转换成二叉树进行处理。

3 第一节 树的概念----树的定义 一棵树是由n（n>0）个元素组成的有限集合，其中： （1）每个元素称为结点(node)；
第一节 树的概念----树的定义 一棵树是由n（n>0）个元素组成的有限集合，其中： （1）每个元素称为结点(node)； （2）有一个特定的结点，称为根结点或树根（root）； （3）除根结点外，其余结点能分成m（m>=0）个互不相交的有限集合T0,T1,T2,……Tm-1。其中的每个子集又都是一棵树，这些集合称为这棵树的子树。 如下图是一棵典型的树：

4 树的基本概念 树是递归定义的； 一棵树中至少有1个结点。这个结点就是根结点，它没有前驱，其余每个结点都有唯一的一个前驱结点。每个结点可以有0或多个后继结点。因此树虽然是非线性结构，但也是有序结构。至于前驱后继结点是哪个，还要看树的遍历方法，我们将在后面讨论； 一个结点的子树个数，称为这个结点的度（degree，结点1的度为3，结点3的度为0）；度为0的结点称为叶结点（树叶leaf，如结点3、5、6、8、9）；度不为0的结点称为分支结点（如结点1、2、4、7）；根以外的分支结点又称为内部结点（结点2、4、7）；树中各结点的度的最大值称为这棵树的度（这棵树的度为3）。 在用图形表示的树型结构中，对两个用线段（称为树枝）连接的相关联的结点，称上端结点为下端结点的父结点，称下端结点为上端结点的子结点。称同一个父结点的多个子结点为兄弟结点。如结点1是结点2、3、4的父结点，结点 2、3、4是结点1的子结点，它们又是兄弟结点，同时结点2又是结点5、6的父结点。称从根结点到某个子结点所经过的所有结点为这个子结点的祖先。如结点1、4、7是结点8

5 的祖先。称以某个结点为根的子树中的任一结点都是该结点的子孙。如结点7、8、9都是结点4的子孙。
E.定义一棵树的根结点的层次（level）为1，其它结点的层次等于它的父结点层次加1。如结点2、3、4的层次为1，结点5、6、7的层次为2，结点8、9的层次为3。一棵树中所有的结点的层次的最大值称为树的深度（depth）。如这棵树的深度为3。 F.对于树中任意两个不同的结点，如果从一个结点出发，自上而下沿着树中连着结点的线段能到达另一结点，称它们之间存在着一条路径。可用路径所经过的结点序列表示路径，路径的长度等于路径上的结点个数减1。如上图中，结点1和结点8之间存在着一条路径，并可用（1、4、7、8）表示这条路径，该条路径的长度为3。注意，不同子树上的结点之间不存在路径，从根结点出发，到树中的其余结点一定存在着一条路径。 G.森林（forest）是m(m>=0)棵互不相交的树的集合。

6 树的存储结构 方法1：数组，称为“父亲表示法”。
　　const int m = 10; //树的结点数 　　struct node 　　{ 　　 int data, parent; //数据域，指针域 　　}; 　　node tree[m]; 优缺点：利用了树中除根结点外每个结点都有唯一的父结点这个性质。很容易找到树根，但找孩子时需要遍历整个线性表。

7 方法2：树型单链表结构，称为“孩子表示法”。每个结点包括一个数据域和一个指针域（指向若干子结点）。称为“孩子表示法”。假设树的度为10，树的结点仅存放字符，则这棵树的数据结构定义如下：
const int m = 10; //树的度 typedef struct node; typedef node *tree; struct node { char data; //数据域 tree child[m]; //指针域，指向若干孩子结点 }; tree t; 缺陷：只能从根（父）结点遍历到子结点，不能从某个子结点返回到它的父结点。但程序中确实需要从某个结点返回到它的父结点时，就需要在结点中多定义一个指针变量存放其父结点的信息。这种结构又叫带逆序的树型结构。

8 方法3：树型双链表结构，称为“父亲孩子表示法”。每个结点包括一个数据域和二个指针域（一个指向若干子结点，一个指向父结点）。假设树的度为10，树的结点仅存放字符，则这棵树的数据结构定义如下：
const int m = 10; //树的度 typedef struct node; typedef node *tree; //声明tree是指向node的指针类型 struct node { char data; //数据域 tree child[m]; //指针域，指向若干孩子结点 tree father; //指针域，指向父亲结点 }; tree t;

9 方法4：二叉树型表示法，称为“孩子兄弟表示法”。也是一种双链表结构，但每个结点包括一个数据域和二个指针域（一个指向该结点的第一个孩子结点，一个指向该结点的下一个兄弟结点）。称为“孩子兄弟表示法”。假设树的度为10，树的结点仅存放字符，则这棵树的数据结构定义如下： 　　typedef struct node; 　　typedef node *tree; 　　struct node 　　{ 　　 char data; //数据域 　　 tree firstchild, next; //指针域，分别指向第一个孩子结点和下一个兄弟结点 　　}; 　　tree t;

10 【例3-1】找树根和孩子 【问题描述】 　　给定一棵树，输出树的根root，孩子最多的结点max以及他的孩子 【输入格式】 　　第一行：n（结点数<=100），m（边数<=200）。 　　 以下m行；每行两个结点x和y， 表示y是x的孩子(x,y<=1000)。 【输出格式】 　　第一行：树根：root。 　　 第二行：孩子最多的结点max。 　　 第三行：max的孩子。 【输入样例】 　　8 7 　　4 1 　　4 2 　　1 3 　　1 5 　　2 6 　　2 7 　　2 8 【输出样例】 　　4 　　2 　　6 7 8

11 【参考程序】 #include<iostream> using namespace std; int n,m,tree[101]={0}; int main() { int i,x,y,root,maxroot,sum=0,j,Max=0; cin>>n>>m; for(i=1;i<=m;i++) cin>>x>>y; tree[y]=x; } for(i=1;i<=n;i++) //找出树根 if(tree[i]==0) root=i;break; for(i=1;i<=n;i++) //找孩子最多的结点 sum=0; for(j=1;j<=n;j++) if(tree[j]==i) sum++; if(sum>Max) { Max=sum;maxroot=i; } cout<<root<<endl<<maxroot<<endl; for(i=1;i<=n;i++) if(tree[i]==maxroot) cout<<i<<" "; return 0;

12 树的遍历 在应用树结构解决问题时，往往要求按照某种次序获得树中全部结点的信息，这种操作叫作树的遍历。遍历的方法有多种，常用的有：
　　A、先序（根）遍历：先访问根结点，再从左到右按照先序思想遍历 各棵子树。 如上图先序遍历的结果为： ； 　　B、后序（根）遍历：先从左到右遍历各棵子树，再访问根结点。如 上图后序遍历的结果为： ； 　　C、层次遍历：按层次从小到大逐个访问，同一层次按照从左到右的 次序。 如上图层次遍历的结果为： ； 　　D、叶结点遍历：有时把所有的数据信息都存放在叶结点中，而其余 结点都是用来表示数据之间的某种分支或层次关系，这种情况就 用这种方法。如上图按照这个思想访问的结果为：56389；

13 大家可以看出，AB两种方法的定义是递归的，所以在程序实现时往往也是采用递归的思想。既通常所说的“深度优先搜索”。如用先序遍历编写的过程如下：
　　void tral(tree t, int m) 　　{ 　　 If (t) 　　 { 　　 cout << t->data << endl; 　　 for(int i = 0 ; i < m ; i++) 　　 tral(t->child[i], m); 　　 } 　　} C方法应用也较多，实际上是我们讲的“广度优先搜索”。思想如下：若某个结点被访问，则该结点的子结点应记录，等待被访问。顺序访问各层次上结点，直至不再有未访问过的结点。为此，引入一个队列来存储等待访问的子结点，设一个队首和队尾指针分别表示出队、进队的下标。程序框架如下：

14 　　const int n = 100; 　　int head, tail, i; 　　tree q[n]; 　　tree p; 　　void work() 　　{ 　　 tail = head = 1; 　　 q[tail] = t; 　　 tail++; //队尾为空 　　 while(head < tail) 　　 { 　　 p = q[head]; 　　 head++; 　　 cout << p->data << ' '; 　　 for(i = 0 ; i < m ; i++) 　　 if(p->child[i]) 　　 { 　　 q[tail] = p->child[i]; 　　 tail++; 　　 } 　　 } 　　}

15 【例3-2】单词查找树 【问题描述】 在进行文法分析的时候，通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度，通常都画出与单词列表所对应的单词查找树，其特点如下： 1．根结点不包含字母，除根结点外每一个结点都仅包含一个大写英文字母； 2．从根结点到某一结点，路径上经过的字母依次连起来所构成的字母序列，称为该结点对应的单词。单词列表中的每个单词，都是该单词查找树某个结点所对应的单词； 3．在满足上述条件下，该单词查找树的结点数最少。 4．例如图左边的单词列表就对应于右边的单词查找树。注意，对一个确定的单词列表，请统计对应的单词查找树的结点数（包含根结点）。

16 【问题输入】 　　输入文件名为word.in，该文件为一个单词列表，每一行仅包含一个单词和一个换行/回车符。每个单词仅由大写的英文字母组成，长度不超过63个字母 。文件总长度不超过32K，至少有一行数据。 【问题输出】 　　输出文件名为word.out，该文件中仅包含一个整数，该整数为单词列表对应的单词查找树的结点数。 【样例输入】 　　　A 　　　AN 　　　ASP 　　　AS 　　　ASC 　　　ASCII 　　　BAS 　　　BASIC 【样例输出】 13

17 【算法分析】 首先要对建树的过程有一个了解。对于当前被处理的单词和当前树：在根结点的子结点中找单词的第一位字母，若存在则进而在该结点的子结点中寻找第二位……如此下去直到单词结束，即不需要在该树中添加结点；或单词的第n位不能被找到，即将单词的第n位及其后的字母依次加入单词查找树中去。但，本问题只是问你结点总数，而非建树方案，且有32K文件，所以应该考虑能不能不通过建树就直接算出结点数？为了说明问题的本质，我们给出一个定义：一个单词相对于另一个单词的差：设单词1的长度为L，且与单词2从第N位开始不一致，则说单词1相对于单词2的差为L-N+1，这是描述单词相似程度的量。可见，将一个单词加入单词树的时候，须加入的结点数等于该单词树中已有单词的差的最小值。 单词的字典顺序排列后的序列则具有类似的特性，即在一个字典顺序序列中，第m个单词相对于第m-1个单词的差必定是它对于前m-1个单词的差中最小的。于是，得出建树的等效算法：

18 ① 读入文件； ② 对单词列表进行字典顺序排序； ③ 依次计算每个单词对前一单词的差，并把差累加起来。注意：第 一个单词相对于“空”的差为该单词的长度； ④ 累加和再加上1（根结点），输出结果。 就给定的样例，按照这个算法求结点数的过程如下表：

19 【数据结构】 先确定32K（32*1024=32768字节）的文件最多有多少单词和字母。当然应该尽可能地存放较短的单词。因为单词不重复，所以长度为1的单词（单个字母）最多26个；长度为2的单词最多为26*26=676个；因为每个单词后都要一个换行符（换行符在计算机中占2个字节），所以总共已经占用的空间为：（1+2）*26+（2+2）*676=2782字节；剩余字节（ =29986字节）分配给长度为3的单词（长度为3的单词最多有 26*26*26=17576个）有29986/（3+2）≈5997。所以单词数量最多为 =6699。 定义一个数组：string a[32768]；把所有单词连续存放起来，用选择排序或快排对单词进行排序。

20 【参考程序】 #include <iostream> #include <cstdio>
#include <string> using namespace std; int i, j, n, t, k; string a[8001]; //数组可以到32768 string s; int main() { freopen("word.in", "r", stdin); freopen("word.out", "w", stdout); while(cin >> a[++n]); //读入文件中的单词并且存储到数组中 n--; for(i = 1 ; i < n ; i++) //单词从小到大排序，选择排序可改为快排sort(a + 1, a + n + 1) for(j = i + 1 ; j <= n ; j++) if(a[i] > a[j]) //两个单词进行交换 s = a[i];

21 a[i] = a[j]; a[j] = s; } t = a[1].length(); //先累加第1个单词的长度 for(i = 2 ; i <= n ; i++) //依次计算每个单词对前一单词的差 { j = 0; while(a[i][j] == a[i - 1][j] && j < a[i - 1].length()) j++; //求两个单词相同部分的长度 t += a[i].length() - j; //累加两个单词的差length(a[i])-j cout << t + 1 << endl; return 0;

22 第二节 二叉树----二叉树基本概念 二叉树（binary tree,简写成BT）是一种特殊的树型结构，它的度数为2的树。即二叉树的每个结点最多有两个子结点。每个结点的子结点分别称为左孩子、右孩子，它的两棵子树分别称为左子树、右子树。二叉树有5中基本形态： 前面引入的树的术语也基本适用于二叉树，但二叉树与树也有很多不同，如：首先二叉树的每个结点至多只能有两个结点，二叉树可以为空，二叉树一定是有序的，通过它的左、右子树关系体现出来。

23 二叉树的性质 【性质1】在二叉树的第i层上最多有2i-1个结点（i>=1）。
证明：很简单，用归纳法：当i=1时，2i-1=1显然成立；现在假设第i-1层时命题成立，即第i-1层上最多有2i –2 个结点。由于二叉树的每个结点的度最多为2，故在第i层上的最大结点数为第i-1层的2倍， 即 2*2i-2=2i–1。 【性质2】深度为k的二叉树至多有2k –1个结点（k>=1）。 证明：在具有相同深度的二叉树中，仅当每一层都含有最大结点数时，其树中结点数最多。因此利用性质1可得，深度为k的二叉树的结点数至多为： 20+21+…+2k-1=2k-1 故命题正确。

24 【特别】一棵深度为k且有2k–1个结点的二叉树称为满二叉树。如下图A为深度为4的满二叉树，这种树的特点是每层上的结点数都是最大结点数。
可以对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，从左到右，由此引出完全二叉树的定义，深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。 下图B就是一个深度为4，结点数为12的完全二叉树。它有如下特征：叶结点只可能在层次最大的两层上出现；对任一结点，若其右分支下的子孙的最大层次为m，则在其左分支下的子孙的最大层次必为m或m+1。下图C、D不是完全二叉树，请大家思考为什么？

25

26 【性质3】对任意一棵二叉树，如果其叶结点数为n0，度为2的结点数为n2，则一定满足：n0=n2+1。
n=no+n1+n2 ……(式子1) 另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是： nl+2n2 树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为： n=n1+2n2+1 ……(式子2) 由式子1和式子2得到： no=n2+1

27 【性质4】具有n个结点的完全二叉树的深度为floor(log2n)+1
证明：假设深度为k，则根据完全二叉树的定义，前面k-1层一定是满的，所以n>2k –1 -1。但n又要满足n<=2k -1。所以，2k–1–1<n<=2k -1。变换一下为2k–1<=n<2k。 以2为底取对数得到：k-1<=log2n<k。而k是整数，所以k= floor(log2n)+1。 【性质5】对于一棵n个结点的完全二叉树，对任一个结点（编号为i），有： ①如果i=1,则结点i为根，无父结点；如果i>1,则其父结点编号为i/2。 如果2*i>n，则结点i无左孩子（当然也无右孩子，为什么？即结点i为叶结点）；否则左孩子编号为2*i。 ②如果2*i+1>n，则结点i无右孩子；否则右孩子编号为2*i+1。

28 证明：略，我们只要验证一下即可。总结如图：

29 二叉树的存储结构 ①链式存储结构，即单链表结构或双链表结构（同树）。数据结构修改如下： 如左图的一棵二叉树用单链表就可以表示成右边的形式：
　　typedef struct node; 　　typedef node *tree; 　　struct node 　　{ 　　 char data; 　　 tree lchild, rchild; 　　}; 　　tree bt; 　　或： 　　 tree lchild, rchild,father; 如左图的一棵二叉树用单链表就可以表示成右边的形式：

30 ②顺序存储结构，即几个数组加一个指针变量。数据结构修改如下：
　　const int n = 10; 　　char data[n]; 　　char lchild[n]; 　　char rchild[n]; 　　int bt; //根结点指针 二叉树在处理表达式时经常用到，一般用叶结点表示运算元，分支结点表示运算符。这样的二叉树称为表达式树。如现在有一个表达式：（a+b/c）*(d-e)。可以用以图表示：

31 二叉树的操作: 最重要的是遍历二叉树，但基础是建一棵二叉树、插入一个结点到二叉树中、删除结点或子树等。
数据结构定义如下： 按表达式的书写顺序逐个编号，分别为1..9，注意表达式中的所有括号在树中是不出现的，因为表达式树本身就是有序的。叶结点的左右子树均为空（用0表示）。 　　char data[9] = {'a', '+', 'b', '/', 'c', '*', 'd', '-', 'e'}; 　　int lchild[9] = {0,1,0,3,0,2,0,7,0}; 　　int rchild[9] = {0,4,0,5,0,8,0,9,0}; 　　int bt; //根结点指针,初值=6，指向'*' 二叉树的操作: 最重要的是遍历二叉树，但基础是建一棵二叉树、插入一个结点到二叉树中、删除结点或子树等。

32 【例3-3】医院设置 【问题描述】 设有一棵二叉树（如图3-8，其中圈中的数字表示结点中居民的人口，圈边上数字表示结点编号。现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻结点之间的距离为1。就本图而言，若医院建在1处，则距离和=4+12+2*20+2*40=136；若医院建在3处，则距离和=4* =81…… 【输入格式】 输入文件名为hospital.in，其中第一行一个整数n，表示树的结点数（n<=100）。接下来的n行每行描述了一个结点的状况，包含三个整数，整数之间用空格（一个或多个）分隔，其中：第一个数为居民人口数；第二个数为左链接，为0表示无链接；第三个数为右链接，为0表示无链接。 【输出格式】 输出文件名为hospital.out，该文件只有一个整数，表示最小距离和。

33 【样例输入】 　　5 　　13 2 3 　　4 0 0 　　12 4 5 　　20 0 0 　　40 0 0 【样例输出】 　　81 【算法分析】 这是一道简单的二叉树应用问题，问题中的结点数并不多，数据规模也不大，采用邻接矩阵存储，用Floyed法求出任意两结点之间的最短路径长，然后穷举医院可能建立的n个结点位置，找出一个最小

34 距离的位置即可。当然也可以用双链表结构或带父结点信息的数组存储结构来解决，但实际操作稍微麻烦了一点。 【参考程序】
#include <iostream> #include <cstdlib> include <cstdio> using namespace std; int a[101]; int g[101][101]; int main() { int n, i, j, k, l, r, min, total; freopen("hospital.in", "r", stdin); freopen("hospital.out", "w", stdout); cin >> n; for(i = 1 ; i <= n ; i++) for(j = 1 ; j <= n ; j++) g[i][j] = ; for(i = 1 ; i <= n ; i++) //读入、初始化

35 { g[i][i] = 0; cin >> a[i] >> l >> r; if(l > 0) g[i][l] = g[l][i] = 1; if(r > 0) g[i][r] = g[r][i] = 1; } for(k = 1 ; k <= n ; k++) //用Floyed求任意两结点之间的最短路径 for(i = 1 ; i <= n ; i++) if(i != k) for(j = 1 ; j <= n ; j++) if(i != j && k != j && g[i][k] + g[k][j] < g[i][j]) g[i][j] = g[i][k] + g[k][j]; min = 0x7fffffff; for(i = 1 ; i <= n ; i++) //穷举医院建在N个结点，找出最短距离 total = 0; for(j = 1 ; j <= n ; j++) total += g[i][j] * a[j]; if(total < min) min = total; cout << min << endl; return 0;

36 【后记】 在各种竞赛中经常遇到这样的问题：N-1条公路连接着N个城市，从每个城市出发都可以通过公路到达其它任意的城市。每个城市里面都有一定数量的居民，但是数量并不一定相等，每条公路的长度也不一定相等。X公司（或者是政府）决定在某一个城市建立一个医院/酒厂/游乐场……，问：将它建在哪里，可以使得所有的居民移动到那里的总耗费最小？这种题目都是本题的“变型”，一般称为“树的中心点问题”。除了简单的穷举法外，还有更好的时间复杂度为O(n)的算法，我们讲在后面的章节中继续讨论。

37 遍历二叉树 在二叉树的应用中，常常要求在树中查找具有某种特征的结点，或者对全部结点逐一进行某种处理。这就是二叉树的遍历问题。所谓二叉树的遍历是指按一定的规律和次序访问树中的各个结点，而且每个结点仅被访问一次。“访问”的含义很广，可以是对结点作各种处理，如输出结点的信息等。遍历一般按照从左到右的顺序，共有3种遍历方法，先（根）序遍历，中（根）序遍历，后（根）序遍历。 ㈠先序遍历的操作定义如下： 若二叉树为空，则空操作，否则 ①访问根结点 ②先序遍历左子树 ③先序遍历右子树 void preorder(tree bt) //先序遍历根结点为bt的二叉树的递归算法 { if(bt) cout << bt->data; preorder(bt->lchild); preorder(bt->rchild); } 先序遍历此图结果为：

38 ㈡中序遍历的操作定义如下： 若二叉树为空，则空操作，否则 ①中序遍历左子树 ②访问根结点 ③中序遍历右子树
　 ②访问根结点 ③中序遍历右子树 　　　void inorder(tree bt) //中序遍历根结点为bt的二叉树的递归算法 　　　{ 　　　 if(bt) 　　　 { 　　　 inorder(bt->lchild); 　　　 cout << bt->data; 　　　 inorder(bt->rchild); 　　　 } 　　　} 中序遍历此图结果为：

39 ㈢后序遍历的操作定义如下： 若二叉树为空，则空操作，否则 ①后序遍历左子树 ②后序遍历右子树 ③访问根结点
void postorder(tree bt) //后序遍历根结点为bt的二叉树的递归算法 { if(bt) postorder(bt->lchild); postorder(bt->rchild); cout << bt->data; } 后序遍历此图结果为：

40 当然，我们还可以把递归过程改成用栈实现的非递归过程，以先序遍历为例，其它的留给读者完成。
　　void preorder(tree bt) //先序遍历bt所指的二叉树 　　{ 　　 tree stack[n]; //栈 　　 int top = -1; //栈顶指针 　　 tree P; 　　 while(bt || top) 　　 { 　　 while(bt) //非叶结点 　　 { 　　 cout << bt->data; //访问根 　　 stack[++top] = bt->rchild; //右子树压栈 　　 bt = bt->lchild; //遍历左子树 　　 } 　　 if(top) //栈中所有元素出栈，遍历完毕 　　 bt = stack[top--]; 　 } 　　 } 　　}

41 关于前面讲的表达式树，我们可以分别用先序、中序、后序的遍历方法得出完全不同的遍历结果，如对于下图中遍历结果如下，它们正好对应着表达式的3种表示方法。
-+a*b-cd/ef (前缀表示、波兰式) a+b*c-d-e/f (中缀表示) abcd-*+ef/- (后缀表示、逆波兰式)

42 二叉树的其它重要操作 除了“遍历”以外，二叉树的其它重要操作还有：建立一棵二叉树、插入一个结点到二叉树中、删除结点或子树等。
1、建立一棵二叉树 void pre_crt(tree &bt) //按先序次序输入二叉树中结点的值，生成 { char ch; ch = getchar(); //二叉树的单链表存储结构，bt为指向根结点的指针,'$'表示空树 if(ch != '$') bt = new node; //建根结点 bt->data = ch; pre_crt(bt->lchild); //建左子树 pre_crt(bt->rchild); //建右子树 } else bt = NULL;

43 2、删除二叉树 3．插入一个结点到排序二叉树中 void dis(tree &bt) //删除二叉树 { if(bt)
dis(bt->lchild); //删左子树 dis(bt->rchild); //删右子树 delete bt; //释放父结点 } 3．插入一个结点到排序二叉树中 void insert(tree &bt, int n) //插入一个结点到排序二叉树中 if(n < bt->data) insert(bt->lchild, n); else if(n > bt->data) insert(bt->rchild, n); else bt = new node; //新开一个空间 bt->data = n; bt->lchild = bt->rchild = NULL;

44 5．用嵌套括号表示法输出二叉树 4．在排序二叉树中查找一个数，找到返回该结点,否则返回NULL
tree findn(tree bt, int n) //在二叉树中查找一个数，找到返回该结点,否则返回NULL。 { if(bt) if(n < bt->data) findn(bt->lchild, n); else if(n > bt->data) findn(bt->rchild, n); else return bt; } else return NULL; 5．用嵌套括号表示法输出二叉树 void print(tree bt) //用嵌套括号表示法输出二叉树 cout << bt->data; if(bt->lchild || bt->rchild) cout << '('; print(bt->lchild); if(bt->rchild) cout << ',';

45 print(bt->rchild);
cout << ')'; } 下面我们换个角度考虑这个问题，从二叉树的遍历已经知道，任意一棵二叉树结点的先序序列和中序序列是唯一的。反过来，给定结点的先序序列和中序序列，能否确定一棵二叉树呢？又是否唯一呢？ 由定义，二叉树的先序遍历是先访问根结点，再遍历左子树，最后遍历右子树。即在结点的先序序列中，第一个结点必是根，假设为root。再结合中序遍历，因为中序遍历是先遍历左子树，再访问根，最后遍历右子树。所以结点root正好把中序序列分成了两部分，root之前的应该是左子树上的结点，root之后的应该是右子树上的结点。依次类推，便可递归得到整棵二叉树。

46 结论：已知先序序列和中序序列可以确定出二叉树；
　　　已知中序序列和后序序列也可以确定出二叉树； 但，已知先序序列和后序序列却不可以确定出二叉树；为什么？举个3个结点的反例。 例如：已知结点的先序序列为ABCDEFG，中序序列为CBEDAFG。构造出二叉树。过程见下图：

47 【例3-4】求后序遍历 【问题描述】 　　输入一棵二叉树的先序和中序遍历序列，输出其后序遍历序列。 【输入格式】 　　输入文件为tree.in，共两行，第一行一个字符串，表示树的先序遍 历，第二行一个字符串，表示树的中序遍历。树的结点一律用小写 字母表示。 【输出格式】 　　输出文件为tree.out，仅一行，表示树的后序遍历序列。 【样例输入】 　　abdec 　　dbeac 【样例输出】 　　debca

48 【参考程序】 #include <cstring> #include <iostream>
#include <cstdio> using namespace std; string s1, s2; void calc(int l1, int r1, int l2, int r2) { int m = s2.find(s1[l1]); if(m > l2) calc(l1 + 1, l1 + m - l2, l2, m - 1); if(m < r2) calc(l1 + m - l2 + 1, r1, m + 1, r2); cout << s1[l1]; } int main() freopen("tree.in", "r", stdin); freopen("tree.out", "w", stdout); cin >> s1 >> s2; calc(0, s1.length() - 1, 0, s2.length() - 1); cout << endl; return 0;

49 【例3-5】扩展二叉树 【问题描述】 由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树，所以对二叉树做如下处理，将二叉树的空结点用·补齐，如图所示。我们把这样处理后的二叉树称为原二叉树的扩展二叉树，扩展二叉树的先序和后序序列能唯一确定其二叉树。 现给出扩展二叉树的先序序列，要求输出其中序和后序序列。 【输入样例】tree_b.in ABD..EF..G..C.. 【输出样例】tree_b.out DBFEGAC DFGEBCA

50 #include <iostream>
#include <stdlib.h> #include <string> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; typedef struct node; typedef node *tree; struct node { char data; tree lchild, rchild; }; tree bt; int i; string s; void build(tree &bt) //建树 if(s[++i]!='.') bt = new node;

51 bt = new node; bt->data = s[i]; build(bt->lchild); build(bt->rchild); } else bt = NULL; void printzx(tree bt) //输出中序序列 { if(bt) printzx(bt->lchild); cout << bt->data; printzx(bt->rchild); void printhx(tree bt) //输出后序序列 printhx(bt->lchild); printhx(bt->rchild);

52 int main() { freopen("tree_b.in", "r", stdin); freopen("tree_b.out", "w", stdout); cin >> s; i = -1; build(bt); printzx(bt); cout << endl; printhx(bt); return 0; }

53 普通树转换成二叉树 由于二叉树是有序的，而且操作和应用更广泛，所以在实际使用时，我们经常把普通树转换成二叉树进行操作。如何转换呢？一般方法如下： 1．将树中每个结点除了最左边的一个分支保留外，其余分支都去掉； 2．从最左边结点开始画一条线，把同一层上的兄弟结点都连起来； 3．以整棵树的根结点为轴心，将整棵树顺时针大致旋转45度。 第一节中的图A所示的普通树转换成二叉树的过程如图B所示：

54 同样我们可以把森林也转换成二叉树处理，假设F={T1，T2，…，Tm}是森林，则可按如下规则转换成一棵二叉树B=(root,lb,rb)。
1．若F为空，即m=0，则 B为空树； 2．若F非空，即m!=0，则B的根root即为森林中第一棵树的根root(T1)；B的左子树lb是从T1中根结点的子树森林F1={T11，T12，…，T1m1}转换而成的二叉树；其右子树rb是从森林F’={T2，T3，…，Tm}转换而成的二叉树。

55 树的计数问题 具有n个结点的不同形态的二叉树有多少棵？具有n个结点的不同形态的树有多少棵？首先了解两个概念，“相似二叉树”是指两者都为空树或者两者均不为空树，且它们的左右子树分别相似。“等价二叉树”是指两者不仅相似，而且所有对应结点上的数据元素均相同。二叉树的计数问题就是讨论具有n个结点、互不相似的二叉树的数目Bn。 在n很小时，很容易得出，B0=1，B1=1，B2=2，B3=5（下图）。

56 一般情况，一棵具有n(n>1)个结点的二叉树可以看成是由一个根结点、一棵具有i个结点的左子树和一棵具有n-i-1个结点的右子树组成，其中0<=i<=n-1,
由此不难得出下列递归公式： 我们可以利用生成函数讨论这个递归公式，得出：Bn= 类推到具有n个结点、互不相似的多叉树的数目Tn 由于树可以转换成二叉树且转换之后的根节点没有右儿子，所以，可以推出：Tn=Bn-1。

57 【课堂练习】 1、一棵完全二叉树的结点总数为18，其叶结点数为 。 A.7个 B.8个 C.9个 D.10个
1、一棵完全二叉树的结点总数为18，其叶结点数为 。 　　　A.7个 B.8个 C.9个 D.10个 2、 二叉树第10层的结点数的最大数目为 。 　　　A B C D.1024 3、一棵深度为K的满二叉树有（ ）个结点。 　　　A.2K B.2K C.2*K D.2*K-1 4、对任何一棵二叉树T，设n0、n1、n2分别是度数为0、1、2的顶点数，则下列判断中正确的是 。 A.n0=n B.n1=n C. n2=n D.n2=n0+1 5、一棵n个节点的完全二叉树，则该二叉树的高度h为( )。 　　　A.n/ B.log(n) C.log(n)/ D. 6、一棵完全二叉树上有1001个结点，其中叶子结点的个数是 。 　　　A B C D.501

58 7、如果一棵二叉树有N个度为2的节点，M个度为1的节点，则该树的叶子个数为 。
　　　A. N B. 2 * N C.N D. M+N-1 8、一棵非空二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定满足 。 　　　A.所有结点均无左孩子 B.所有的结点均无右孩子 　　　C.只有一个叶子结点 D.是任意一棵二叉树 9、将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度是 。 　　　A B C D.7 10、在一棵具有K层的满三叉树中，结点总数为 。 　　　A.(3k-1)/ B.3k C.(3k-1)/ D.3k 11、设树T的高度为4，其中度为1、2、3和4的结点个数分别为4、2、1、1，则T中的叶子数为 。 　　　A B C D.8

59 12、一棵树T有2个度数为2的结点、有1个度数为3的结点、有3个度数为4的结点，那么树T有（ ）个树叶。
　　　A B C D.7 13、某二叉树中序序列为abcdefg，后序序列为bdcafge，则前序序列是 。 　　　A.egfacbd B.eacbdgf C.eagcfbd D.以上答案都不对 14、已知某二叉树的中序遍历序列是debac，后序遍历序列是dabec，则它的前序遍历序列是 。 A.a c b e d B.d e c a b C.d e a b c D.c e d b a 15、一颗二叉树的中序遍历序列为DGBAECHF，后序遍历序列为GDBEHFCA，则前序遍历序列是 。 　　　A. ABCDFGHE B. ABDGCEFH C. ACBGDHEF D. ACEFHBGD 16、已知一棵二叉树的前序序列为ABDEGCFH，中序序列为DBGEACHF，则该二叉树的层次序列为 。 A.GEDHFBCA B.DGEBHFCA C.ABCDEFGH D.ACBFEDHG

60 17、已知一棵二叉树的前序遍历结果为ABDECFHJIG，中序遍历的结果为DBEAJHFICG，则这棵二叉树的深度为 。
　　　A B C D.6 18、二叉树的先序遍历和中序遍历如下：先序遍历:EFHIGJK，中序遍历:HFIEJKG。 　　该二叉树根的右子树的根是__________。 　　　A. E B. F C. G D.H 19、中缀表达式A-（B+C/D）*E的后缀形式是 。 A.AB-C+D/E* B.ABC+D/-E* C.ABCD/E*+- D.ABCD/+E*- 20、设森林F对应的二叉树为B，它有M个结点，B的根为P，P的右子树结点个数为N，森林F中第一棵树的结点个数是 。 　　　A.M-N B.M-N C.N D.条件不充分，无法确定

61 【练习答案】 1.C 2.C 3.A 4.A 5.D 6.D 7.A 8.A 9.B 10.A 11.D 12.A 13.B 14.D 15.B 16.C 17.C 18.C 19.D 20.A 7、此树的边数为2N+M，故而总共有2N+M+1个顶点。除去度为1、2的顶点，度为0的节点（即叶子节点）有(2N+M+1)-(N+M)=N+1。答案：A 12、设树T有n个结点，m条边。边数为结点的度数之和， 　　即m=2×2＋1×3＋3×4=19，n=m+1=20。n个结点中 　　有1+2+3=6个分支结点，有叶结点20-6=14个。答案：A 15、中序遍历DGBAECHF和后序遍历GDBEHFCA唯一对应 　　一棵二叉树前序遍历为ABDGCEFH。答案：B

62 16、由前序序列和中序序列可以唯一地确定一棵二叉树，根据题设中的前序序列和中序序列确定的二叉树为：
由此可见，其层次序列为ABCDEFGH。答案：C 17、由题目给出二叉树先序遍历结点的顺序：ABDECFHJIG可知结点A为二叉树的根结点。再由中序遍历的结点顺序：DBEAJHFICG可知结点A前的DBE为根结点A的左子树的结点，而JHFICG为根结点A的右子树的结点。

63 先来看A结点的左子树的结点DBE。在先序遍历顺序中，B结点在A结点之后，说明B结点是左子树的根结点，D结点又在B结点之后，则D是B的左子树的根结点。结点E由中序遍历的顺序可知是B的右子树的根结点。同样求出右子树JHFICG，如下图。 由图可知，二叉树的深度为5。答案：C。 19、该题答案是（D），本题主要考察学生怎样将中缀表达式 转换为后缀表达式。可以先画出该二叉树，对其进行后根遍历 即为答案。

64 【上机练习】 1、小球(DROP) 【问题描述】
许多的小球一个一个的从一棵满二叉树上掉下来组成FBT（Full Binary Tree，满二叉树），每一时间，一个正在下降的球第一个访问的是非叶子节点。然后继续下降时，或者走右子树，或者走左子树，直到访问到叶子节点。决定球运动方向的是每个节点的布尔值。最初，所有的节点都是FALSE，当访问到一个节点时，如果这个节点是FALSE，则这个球把它变成TRUE，然后从左子树走，继续它的旅程。如果节点是TRUE，则球也会改变它为FALSE，而接下来从右子树走。满二叉树的标记方法如下图。

65 因为所有的节点最初为FALSE，所以第一个球将会访问节点1，节点2和节点4，转变节点的布尔值后在在节点8停止。第二个球将会访问节点1、3、6,在节点12停止。明显地，第三个球在它停止之前，会访问节点1、2、5，在节点10停止。 　　现在你的任务是，给定FBT的深度D，和I，表示第I个小球下落，你可以假定I不超过给定的FBT的叶子数，写一个程序求小球停止时的叶子序号。 【输入格式】 输入文件仅一行包含两个用空格隔开的整数D和I。其中2<=D<=20，1<=I<=524288。 【输出格式】 对应输出第I个小球下落停止时的叶子序号。 【输入样例】DROP.IN 　　4 2 【输出样例】DROP.OUT 　　　12

66 2、二叉树遍历(flist) 【问题描述】 　　树和二叉树基本上都有先序、中序、后序、按层遍历等遍历顺序，给定中序和其它一种遍历的序列就可以确定一棵二叉树的结构。 　　假定一棵二叉树一个结点用一个字符描述，现在给出中序和按层遍历的字符串，求该树的先序遍历字符串。 【输入格式】 输入文件flist.in共两行，每行是由字母组成的字符串（一行的每个字符都是唯一的），分别表示二叉树的中序遍历和按层遍历的序列。 【输出格式】 输出文件flist.out就一行，表示二叉树的先序序列。 【输入样例】flist.in 　　DBEAC 　　ABCDE 【输出样例】flist.out 　　ABDEC

67 3、FBI树(fbi) 【问题描述】 我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。 FBI树是一种二叉树[ 二叉树：二叉树是结点的有限集合，这个集合或为空集，或由一个根结点和两棵不相交的二叉树组成。这两棵不相交的二叉树分别称为这个根结点的左子树和右子树。]，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下： T的根结点为R，其类型与串S的类型相同； 若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。 现在给定一个长度为2N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历[ 后序遍历：后序遍历是深度优先遍历二叉树的一种方法，它的递归定义是：先后序遍历左子树，再后序遍历右子树，最后访问根。]序列。

68 【输入文件】 输入文件fbi.in的第一行是一个整数N（0 <= N <= 10），第二行是一个长度为2N的“01”串。 【输出文件】 输出文件fbi.out包括一行，这一行只包含一个字符串，即FBI树的后序遍历序列。 【样例输入】fbi.in 　　3 　　 【样例输出】fbi.out 　　IBFBBBFIBFIIIFF 【数据规模】 　　对于40%的数据，N <= 2； 　　对于全部的数据，N <= 10。

69 4、二叉树输出(btout) 【问题描述】 树的凹入表示法主要用于树的屏幕或打印输出，其表示的基本思想是兄弟间等长，一个结点要不小于其子结点的长度。二叉树也可以这样表示，假设叶结点的长度为1，一个非叶结点的长并等于它的左右子树的长度之和。 一棵二叉树的一个结点用一个字母表示（无重复），输出时从根结点开始： 每行输出若干个结点字符（相同字符的个数等于该结点长度）， 如果该结点有左子树就递归输出左子树； 如果该结点有右子树就递归输出右子树。 假定一棵二叉树一个结点用一个字符描述，现在给出先序和中序遍历的字符串，用树的凹入表示法输出该二叉树。

70 【输入格式】 输入文件btout.in共两行，每行是由字母组成的字符串（一行的每个字符都是唯一的），分别表示二叉树的先序遍历和中序遍历的序列。 【输出格式】 输出文件btout.out的行数等于该树的结点数，每行的字母相同。 【输入样例】btout.in 　　ABCDEFG 　　CBDAFEG 【输出样例】btout.out 　　AAAA 　　BB 　　C 　　D 　　EE 　　F 　　G

71 5、查找二叉树 【问题描述】 已知一棵二叉树用邻接表结构存储，中序查找二叉树中值为x的结点，并指出是第几个结点。例：如图二叉树的数据文件的数据格式如下 7 15 5 2 3 12 4 5 10 0 0 29 0 0 15 6 7 8 0 0 23 0 0 　　第一行n为二叉树的结点个树，n<=100；第二行x表示要查找的结点的值；以下第一列数据是各结点的值，第二列数据是左儿子结点编号，第三列数据是右儿子结点编号。 　　输出一个数即查找的结点编号。 本例的输出样例: 4

72 6、对称二叉树 【问题描述】 如果二叉树的左右子树的结构是对称的，即两棵子树皆为空，或者皆不空，则称该二叉树是对称的。编程判断给定的二叉树是否对称. 例：如下图中的二叉树T1是对称的，T2是不对称的。 　　　 二叉树用顺序结构给出，若读到#则为空，二叉树T1=ABCDE，T2=ABCD#E，如果二叉树是对称的，输出“Yes”,反之输出“No”。 【输入样例】tree_c.in 　　　ABCDE 【输出样例】tree_c.out 　　　Yes