第6章 树和二叉树,6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树 6.4 线索二叉树 6.5 树和森林 6.6 哈夫曼树,教学目的、要求,1领会树和二叉树的类型定义，理解树和二叉树的结构差别。 2熟记二叉树的主要特性，并掌握它们的证明方法。 3熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作。 4理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。 5熟练掌握二叉树和树的各种存储结构及其建立的算法。 6学会编写实现树的各种操作的算法。 7了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。,6.1 树的定义和基本术语 6.1.1树的定义,树是由n（n0）个结点组成的有限集合。若n=0，称为空树；若n0，则： 有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱； 除根结点以外的其它结点可以划分为m（m0）个互不相交的有限集合T0，T1，Tm-1，每个集合Ti（i=0,1,m-1）又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。 由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。,树的结构参见下图：,图6.1树的结构,在图6.1(c)中，树的根结点为A，该树还可以分为三个互不相交子集T0，T1，T2，其中T0=B，E，F，J，K，L，T1=C，G，T2=D，H，I，M，其中的T0，T1，T2都是树，称为图6.1(C)中树的子树，而T0，T1，T2又可以分解成若干棵不相交子树。如T0可以分解成T00，T01两个不相交子集，T00=E，J，K，L，T01=F，而T00又可以分为三个不相交子集T000，T001，T002，其中，T000=J，T001=K，T002=L。,树的抽象数据类型定义见教材P118-119,6.1.2 基本术语,1. 结点 指树中的一个数据元素，一般用一个字母表示。 2. 度 一个结点包含子树的数目，称为该结点的度。 3. 树叶（叶子） 度为0的结点，称为叶子结点或树叶，也叫终端结点。 4. 孩子结点 若结点X有子树，则子树的根结点为X的孩子结点，也称为孩子，儿子，子女等。如图6.1（c）中A的孩子为B，C，D。 5. 双亲结点 若结点X有子女Y，则X为Y的双亲结点。,6. 祖先结点 从根结点到该结点所经过分枝上的所有结点为该结点的祖先，如图6-1（c）中M的祖先有A，D ，H 。 7. 子孙结点 某一结点的子女及子女的子女都为该结点子孙。 8. 兄弟结点 具有同一个双亲的结点，称为兄弟结点。 9. 分枝结点 除叶子结点外的所有结点，为分枝结点，也叫非终端结点。 10. 层数 根结点的层数为1，其它结点的层数为从根结点到该结点所经过的分支数目再加1。,11. 树的深度（高度） 树中结点所处的最大层数称为树的高度，如空树的高度为0，只有一个根结点的树高度为1。 12. 树的度 树中结点度的最大值称为树的度。 13. 有序树 若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。 14. 无序树 若一棵树中所有子树的次序无关紧要，则称为无序树。 15森林 若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。,6.1.3 树的表示 1. 树形结构表示法,2. 凹入法表示法,图6.1（c）的树的凹入法表示,3. 嵌套集合表示法,图6.1（c）的嵌套集合表示,4. 广义表表示法,对图6-1（c）的树结构，广义表表示法可表示为： （A（B（E（J，K，L），F），C（G），D（H（M），I）,6.1.4 树的性质,性质1 树中的结点数等于所有结点的度加1。 证明：根据树的定义，在一棵树中，除根结点以外，每个结点有且仅有一个直接前驱，也就是说，每个结点与指向它的一个分支一一对应，所以，除根结点以外的结点数等于所有结点的分支数（即度数），而根结点无直接前驱，因此，树中的结点数等于所有结点的度数加1。,性质2 度为k的树中第i层上最多有ki-1个结点（i1）。 下面用数学归纳法证明： 对于i=1，显然成立，假设对于i-1层，上述条件成立，即第i-1层最多有ki-2个结点， 对于第i层，结点数最多为第i-1层结点数的k倍（因为度为k），故第i层的结点数为ki-2*k= ki-1。,性质3 深度为h的 k叉树最多有 个结点。 证明： 由性质2可知，若每一层的结点数最多，则整个k叉树结点数最多，共有 当一棵K叉树上的结点数达到 时，称为满K叉树。,性质4 具有n个结点的k叉树的最小深度为 。 （ 表示取不小于x的最小整数） 证明：设具有n个结点的k叉树的深度为h，在该树的前面h-1层都是满的，即每一层的结点数等于ki-1个(1ih-1)，第h层（即最后一层）的结点数可能满，也可能不满，这时，该树具有最小的深度。 由性质3知道，结点数n应满足下面条件：,通过转换为：kh-1n(k-1)+1kh，再取以k为底的对数后，可以得到： h-1logk(n(k-1)+1)h 即有：logk(n(k-1)+1)hlogk(n(k-1)+1)+1，而h只能取整数，所以，该k叉树的最小深度为： h=,6.2 二叉树,为何要重点研究每结点最多只有两个 “叉“ 的树？ 二叉树的结构最简单，规律性最强； 可以证明，所有树都能转为唯一对应的二叉树，不失一般性。,6.2.1 二叉树的定义,和树结构定义类似，二叉树的定义也可以递归形式给出： 二叉树是n（n0）个结点的有限集，它或者是空集（n=0），或者由一个根结点及两棵不相交的左子树和右子树组成。,二叉树的特点是每个结点最多有两个孩子，或者说，在二叉树中，不存在度大于2的结点，并且二叉树是有序树（树为无序树），其子树的顺序不能颠倒，因此，二叉树有五种不同的形态，参见图6.5。,图6.5 二叉树的五种不同形态,问：具有3个结点的二叉树可能有几种不同形态？,有五种,二叉树的的抽象数据类型定义见教材P121。,性质1 二叉树的第i层结点数，最多为2i-1个（i1）。 性质2 深度为k的二叉树最大结点数为2k-1（i1）。,性质3 对任意一棵二叉树，如果叶子结点个数为n0，度为2的结点个数为n2，则有n0=n2+1。 证明：设二叉树中度为1的结点个数为n1，根据二叉树的定义可知，该二叉树的结点数n=n0+n1+n2。 又因为在二叉树中，度为0的结点没有孩子，度为1的结点有1 个孩子，度为2的结点有2个结孩子，故该二叉树的孩子结点数为 n0*0+n1*1+n2*2 。 而一棵二叉树中，除根结点外所有的结点都为孩子结点，故该二叉树的结点数应为孩子结点数加1即：n=n0*0+n1*1+n2*2+1。 因此，有 n=n0+n1+n2=n0*0+n2*1+n2*2+1，最后得到n0=n2+1。,为继续给出二叉树的其它性质，先定义两种特殊的二叉树。 满二叉树 深度为k具有2k-1个结点的二叉树，称为满二叉树。 从上面满二叉树定义可知，必须是二叉树的每一层上的结点数都达到最大，否则就不是满二叉树。 完全二叉树 对满二叉树的结点，从根结点起，自上而下，自左至右进行连续编号。 如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1 n的结点一一对应，则称这棵二叉树为完全二叉树。,从满二叉树及完全二叉树定义可以知道，满二叉树一定是一棵完全二叉树，反之完全二叉树不一定是一棵满二叉树。 满二叉树的叶子结点全部在最底层，而完全二叉树的叶子结点可以分布在最下面两层。深度为4的满二叉树和完全二叉树如图6.6所示。,图6.6 满二叉树和完全二叉树,性质4 具有n个结点的完全二叉树深度为 或 。 性质5 如果将一棵有n个结点的完全二叉树从上到下，从左到右对结点编号1，2，n，并简称编号为i的结点为i(1in)，则有如下结论成立： 若 i=1，则结点i为根结点，无双亲，否则i的双亲为 ； 若2in，则结点i无左孩子，否则i的左孩子为2i。即满足2in的结点为叶子结点； 若2i+1n，则结点i无右孩子，否则i的右孩子为2i+1； 若结点i为奇数且不等于1，则它的左兄弟为i-1； 若结点i为偶数且不等于n，它的右兄弟为i+1； 结点i所在层数(层次)为 ；,6.2.3 二叉树的存贮结构 1. 顺序存贮结构,按二叉树的结点“自上而下、从左至右“编号，用一组连续的存储单元存储。 若该二叉树为非完全二叉树，则必须将相应位置空出来，使存放的结果符合完全二叉树形状。,图6.7 二叉树的顺序存储,对于一棵二叉树，若采用顺序存贮时，当它为完全二叉树时，比较方便,若为非完全二叉树，将会浪费大量存贮存贮单元。最坏的非完全二叉树是全部只有右分支，设高度为K，则需占用2K-1个存贮单元，而实际只有k个元素，实际只需k个存储单元。因此，对于非完全二叉树，宜采用下面的链式存储结构。,2. 二叉链表存贮结构 二叉链表表示,将一个结点分成三部分，一部分存放结点本身信息，另外两部分为指针，分别存放左、右孩子的地址。 注：如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉链表。,对于图6.7所示二叉树，用二叉链表形式描述。,图6.8 二叉树的二叉链表表示, 二叉链表的数据类型 bitree.h,/二叉链表定义 #include using namespace std; typedef char TElemType; struct BiTNode TElemType data; BiTNode *lchild,*rchild; ; typedef BiTNode *BiTree;,void initBiTree(BiTree , 二叉链表的建立,为了后面遍历二叉树方便，先介绍建立二叉链表的算法（假设ElemType 为char型）。,/按先序次序输入二叉树中结点的值（#表示空格）， /构造二叉链表表示的二叉树T。 void createBiTree(BiTree / 构造右子树 ,6.3 遍历二叉树,遍历是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。 所谓遍历二叉树，就是遵从某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。 这里提到的“访问“是指对结点施行某种操作，操作可以是输出结点信息，修改结点的数据值等，但要求这种访问不破坏它原来的数据结构。在本书中，我们规定访问是输出结点信息data，且以二叉链表作为二叉树的存贮结构。,由于二叉树是一种非线性结构，每个结点可能有一个以上的直接后继，因此，必须规定遍历的规则，并按此规则遍历二叉树，最后得到二叉树所有结点的一个线性序列。 令L、R、D分别代表二叉树的左子树、右子树、根结点，则遍历二叉树有6种规则：DLR、DRL、LDR、LRD、RDL、RKD。若规定二叉树中必须先左后右(左右顺序不能颠倒)，则只有DLR、LDR、LRD三种遍历规则。DLR称为前根遍历(或前序遍历、先序遍历、先根遍历)，LDR称为中根遍历(或中序遍历)，LRD称为后根遍历(或后序遍历)。,6.3.1 前序遍历,所谓前序遍历，就是根结点最先遍历，其次左子树，最后右子树。,1. 递归遍历,前序遍历二叉树的递归遍历算法描述为： 若二叉树为空，则算法结束； 否则 输出根结点； 前根遍历左子树; 前根遍历右子树。,/ 先序递归遍历T，对每个结点调用函数Visit一次且仅一次 void preOrderTraverse(BiTree T,void (*visit)(TElemType) if(T) / T不空 visit(T-data); / 先访问根结点 preOrderTraverse(T