第六章 树和二叉树

《第六章 树和二叉树》由会员分享，可在线阅读，更多相关《第六章 树和二叉树（73页珍藏版）》请在金锄头文库上搜索。

1、 第六章 树和二叉树6.1 树树的定义义和基本术语术语 6.2 二叉树树 6.3 遍历历二叉树树和线线索二叉树树 6.4 树树和森林 6.5 赫夫曼树树及其应应用1.树(Tree)：是n(n0)个结点的有限集。在任意一棵 非空树中(1) 有且只有一个称为根(Root)的结点。(2) 其余的结点被分为m(m0)个互不相交的有限集， 其中每个集合本身又是一棵树，称为根(Root)结点的 子树(Sub_Tree)。6.1 树的定义和基本术语6.1.1 基本术语树的定义本身是递归的。递归定义和递归操作在树 和二叉树中应用是比较广泛的，应注意领会递归的 实质。2.树的表示法：有图示法、集合表示法、广义表

2、表示 法和缩进表示法，见图6.1。 (A(B(E,F(L),G),C(H,I(M,N),D(J,K) (b) 广义表表示法ACEFGHJKLNMBID(a) 图示法 ADBCIMNHGEFLKJ(c) 集合表示法 ABEFLGCHIMNDKJ(d) 缩进 表示法图4.1 树的几种表示法 3.结点的分类：从计算机的角度来分，可以分为终端结点和 非终端结点；以树的特征来分，可以分根结点、分支结点和叶 子结点；用族谱的关系来分，可以分为双亲结点和孩子结点、 祖先结点和子孙结点、兄弟结点和堂兄弟结点。 4.度：分为结点的度和树的度两种。结点的度是指与该结点 相连接的孩子结点的数目。树的度是指该棵树中所

3、有结点的度 中的最大值。 5.深度：树是一种分层结构，根结点作为第一层。结点的层 次(或称深度)就是指从根结点开始的层次数。树的深度(或层数) 是指该树中所有结点的层次中的最大值。用图示法表示的二叉树中，边的数目(或称分支数， 用e表示)恰好比结点数目(用n表示)少一个，即e=n-1 。这是树状结构中最重要的一个结论。6.有序树与无序树：如果将树中结点的各棵子树看成是从左到右有 次序的(即不能互换),则称该树为 有序树，否则称为无序树。7有向树与无向树：如果树的每个分支都是从一个结点到另一个 结点有方向的，则称该树为 有向树，否则称为无向树。8.n元树：树的度为n的有向树。9.位置树：是一棵有

4、向树。如果树中结点的每个孩子结点位置是不 能被改变的(改变则不是原树)，则称该树为 位置树。如某结点可能 没有第一个孩子结点，但却可能会有第二个、第三个孩子结点。10.m叉树：是树的度为m的有向位置树，即m元位置树。11.森林：是m(m0)棵互不相交的树的集合。对于树中的每个结点 而言，其子树的集合就是森林。因此，森林和树是密切相关的。森 林中的树也可以有顺序关系和位置关系。树状结构也是用于存储数据的，我们也要对其中的数据进行加 工处理。总体上，树的基本操作有如下几种：InitTree(T)构造一棵空树T。ClearTree(T)将已经存在的树T清空。TreeEmpty(T)判断树T是否为空树

5、。TreeDepth(T)计算树T的深度。InsertChild(T,p,i,c)插入子树c为树T中p指向结点的第i棵子 树。DeleteChild(T,p,i)删除树T中p所指结点的第i棵子树。TraverseTree(T)按某种次序对树T中的所有结点进行访问 ，每个结点仅访问 一次。6.1.2 树的基本操作二叉树(Binary Tree)是一种特殊的有向树，也称二元 位置树。它的特点是每个结点至多有两棵子树，即二 叉树中的每个结点至多有两个孩子结点，且每个孩子 结点都有各自的位置关系。或者说，二叉树的子树有 左右之分，其次序不能任意颠倒。给二叉树下个更加 确切的定义，就是：二叉树或者为空，

6、或者是由一个 根结点加上两棵分别称为左子树和右子树的、互不相 交的二叉树组成。6.2 二叉树6.2.1 二叉树的定义可以看出，二叉树的定义是递归的，前面提到的树 的定义也是递归的。这说明树状结构在处理数据时 很多操作是可以通过递归 来完成的。图6.2 二叉树的五种基本形态(a)空二叉树(b)仅 有根 结点(c)右 子树 为空(d)左 子树 为空(e)左右 子树均 非空根据二叉树的定义，可以总结出二叉树有如图6.2所示 的五种形态： 【例6.1】列举出只有两个结点、三个结点的二叉树的所 有形态 1. 只有两个结点的二叉树的形态有两种，如图6.3所示 图6.3 只有两个结点的二叉树的所有形态2.

7、只有三个结点的二叉树的形态有五种，如图6.4所示 图6.4 只有三个结点的二叉 树的所有形态6.2.2 二叉树的性质与结论 性质1：在二叉树的第i(i1)层上至多有2i-1个结点。(该性质证明利用归纳法很容易实现，留给读者自己去思考)性质2：深度为k(k1)的二叉树上至多有2k-1个结点。(该性质证明直接利用性质1即可，留给读者自己去思考)性质3：任意一棵二叉树中，叶子结点的数目(用n0表示)总 比度为2的结点的数目(用n2表示)多一个，即n0=n2+1。证明：设结点总数为n，度为1的结点数目为n1，则有n=n0+n1+n2 (6-1)由于二叉树中除根之外的每个结点都带有一个向上的分支， 设分

8、支总数为e，则e=n-1 (6-2)由于这些分支不是度为1的结点射出的分支，就是度为2的结点 射出的分支,则e=1n1+2n2 (6-3)由(6-2)式和(6-3)式，得n-1=n1+2n2 (6-4)由(6-1)式和(6-4)式，得1=n0-n2 即 n0=n2+1 证毕。两种特殊形态的二叉树 满二叉树: 除叶子结点外的任何结点均有两个孩子结 点，且所有的叶子结点都在同一层上的二叉树。特 点是每一层上的结点数都是最大的。完全二叉树:除去最底层结点后的二叉树是一棵满二 叉树，且最底层结点均靠左对齐的二叉树。在这里 ，靠左对齐的含义是左边是满的，即没有空隙再放 入任何一个结点。423167891

9、0 111256.5(b)如图6.5(a)是一棵深度为4的满二叉树，而图6.5(b)是一棵深度 为4的完全二叉树。实质上，满二叉树是完全二叉树的一个特 例423167891 01 11 21 31 41 556.5(a)证明：设具有n个结点的完全二叉树的深度为k，则由性质2可知2k-1-11) *pa=bti/2;else printf(“该结点为根结点!”);if(2*idata);/*访问 根结点*/PreOrderTraverse(bt-lchild);/* 遍历左子树 */PreOrderTraverse(bt-rchild); /* 遍历右子树 */2. 遍历二叉树的递归算法(3)

10、后序遍历二叉树的递归 算法void PostOrderTraverse(BitTree bt) if(bt!=NULL)PostOrderTraverse(bt-lchild);PostOrderTraverse(bt-rchild);printf(“%d “,bt-data); (2) 中序遍历二叉树的递归 算法void InOrderTraverse(BitTree bt) if(bt!=NULL) InOrderTraverse(bt-lchild);printf(“%d “,bt-data);InOrderTraverse(bt-rchild); 3. 二叉树的建立算法因为在含有n个结

11、点的二叉链表中一定有n+1个空指针域，所以在 输出数据时一定要给出n+1个空指针值。对于数值型数据一般以“- 1”代替空指针，对于字符型数据一般以空格“”代替空指针。 BitTree CreateBiTree(void) BitTree bt;TelemType x;scanf(“%d“, /* 读读入数据 */if(x=-1) bt=NULL; /* 安排空指针针 */ else bt=(BitTree)malloc(sizeof(BitNode);bt-data=x; /* 生成新结结点 */bt-lchild=CreateBiTree(); /* 建立左子树树 */bt-rchild=C

12、reateBiTree(); /* 建立右子树树 */ return bt; /* 返回根结结点的指针针 */若输入如下数据：124-1- 1-1357-1-18-1- 16-1-1，则建立的二叉树如 图6.13所示，其中-1用来安排空 指针。若data域为字符型，则输 入如下数据： 12435786,也可以建 立如图4.13所示的二叉树，其中 “”表示空格符，用来安排空指针 。需要注意的是n个结点的二叉 树中一定有n+1个空指针，所以 要输入n+1个“-1”或空格“”。 12435876图6.13二叉树递归 遍历应用举例 【例6. 10】统计二叉树中叶子结点的个数。int n=0; /* 定

13、义一个全局变量用来存放叶子结点的个数 */void leafcount(BitTree bt) if(bt!=NULL) if(bt-lchild=NULL /* 将访问换 成统计个数的语句 */leafcount(bt-lchild);leafcount(bt-rchild);【例6.11】交换二叉树中所有结点的左右子树。BitTree exchangetree(BitTree bt) BitTree t;if(bt!=NULL) if(bt-lchild!=NULL|bt-rchild!=NULL) /* 将访问换 成交换指 针的语句 */ t=bt-lchild;bt-lchild=bt

14、-rchild;bt-rchild=t;bt-lchild=exchangetree(bt-lchild);bt-rchild=exchangetree(bt-rchild); 【例6.12】求二叉树的高度。int hightree(BitTree bt) int H,H1,H2;if(bt=NULL) H=0; /* 树空，则高度为0 */else H1=hightree(bt-lchild); /* 否则，分别计算左右子树的高度 */H2=hightree(bt-rchild);H=(H1H2?H1:H2)+1;/* 取左右子树高度的最大值再加1(根结点 )作为树的高度 */ return

15、 H;【例6.13】查找值为x的结点。找到带回该结点的指针，否则带回 空指针。int find=0; /* 设置查找标记：0表示未找到，1表示找到 */void searchtree(BitTree bt,TElemType x,BitTree *p) if(bt!=NULL*p=bt; /* 若找到，则通过p带回该结点的指针 */else *p=NULL; /* 未找到，通过p带回空指针 */searchtree(bt-lchild,x,p);searchtree(bt-rchild,x,p);【例6.14】删除值为x的结点，使得其左右子树的安排仍然满足 原来的中序遍历序列。分析：为了保持中序遍历序列不变，对于找到 的结点p可以分为四种情况考虑： 若结点p 为叶子结点，则只需将该结点的双亲结点(f) 的左指针或右指针置为空即可； 若结点p的 左子树为空，则只需将该结点(p)的双亲结点 (f)的左指针或右指针指向该结点(p)的右孩子 结点即可； 若结点p的左子树非空，则只需 找到结点p的左子树中最右下的结点s(s的右指 针必为空)，将该结点(s)的左子树接到该结点 (s)的双亲结点(q)上，再用该结点(s)中