树和二叉树汇编

1、树形结构树形结构全校学生档案管理的组织方式全校学生档案管理的组织方式树形结构树形结构 结点间具有分层次的连接关系结点间具有分层次的连接关系HBCDEFGA第六章第六章 树和二叉树树和二叉树6.1 树的定义树的定义 由由n(n0)n(n0)个结点个结点组成的组成的有限集合有限集合。仅有一个根结点，结点间有。仅有一个根结点，结点间有明显的明显的层次层次结构关系。结构关系。n1n1时，其余结点可分为时，其余结点可分为m(m0)m(m0)个互不相交的个互不相交的有限集有限集T T1 1,T,T2 2,.,T,.,Tm m，其中每一个集合本身又是一棵树，称为根的子其中每一个集合本身又是一棵树，称为根的子

2、树。树。 A C G T2D H I T3J M B E L KT1 F现实世界中，能用树的结构表示的例子：现实世界中，能用树的结构表示的例子：学校的行政关系、书的层次结构、人类的家族血缘关系等。学校的行政关系、书的层次结构、人类的家族血缘关系等。介绍几个概念：介绍几个概念：结点（结点（Node）：树中的元素，包含树中的元素，包含数据项数据项及若干指向其子树的及若干指向其子树的分支分支。结点的度（结点的度（Degree）：结点拥有的结点拥有的子树数子树数。叶子（叶子（Leaf）：度为零度为零的结点，也称端结点的结点，也称端结点。孩子（孩子（Child）：结点结点子树的根子树的根称为该结点的孩子

3、结点称为该结点的孩子结点。双亲（双亲（Parent）：孩子结点的孩子结点的上层上层结点，称为这些结点的双亲。结点，称为这些结点的双亲。兄弟（兄弟（Sibling）：同一双亲同一双亲的孩子的孩子。结点的层次：结点的层次：从根结点开始算起，根为第一层从根结点开始算起，根为第一层。深度（深度（Depth)： 树中结点的树中结点的最大层次数最大层次数。森林（森林（Forest）：m(m0)棵棵互不相交互不相交的树的的树的集合集合。 A C G T2D H I T3J M B E L KT1 F因为树的每个结点的度不同，存储困难，使对树的处理算法因为树的每个结点的度不同，存储困难，使对树的处理算法很复杂

4、。所以引出二叉树的讨论。很复杂。所以引出二叉树的讨论。树的基本操作：树的基本操作： 构造树、销毁树、插入、删除、遍历等。构造树、销毁树、插入、删除、遍历等。6.2 二叉树二叉树 （Binary Tree）1 、二叉树的定义及其性质、二叉树的定义及其性质(1) 二叉树的定义二叉树的定义二叉树的五种基本形态二叉树的五种基本形态二叉树是另外一种树型结构，特点是树中每个结点只有两棵二叉树是另外一种树型结构，特点是树中每个结点只有两棵子树，且子树有左右之分，次序不能颠倒。子树，且子树有左右之分，次序不能颠倒。 空二叉树空二叉树 仅有仅有根结点根结点 右子树右子树为空为空 左子树左子树为空为空左右子树左右

5、子树均非空均非空 二叉二叉树树是是n(nn(n 0)0)个结点的有限集合。它或为空个结点的有限集合。它或为空树树( (n=0),n=0),或由一个根结点和两棵分别称为根的左子或由一个根结点和两棵分别称为根的左子树和右子树的互不相交的二叉树组成。树和右子树的互不相交的二叉树组成。 特别要注意：特别要注意：二叉树不是二叉树不是树的特殊情况。树的特殊情况。a aa ab bb b两棵不同的二叉树两棵不同的二叉树 二叉树的基本操作：二叉树的基本操作： 构造二叉树、销毁二叉树、插入、删除、遍历等。构造二叉树、销毁二叉树、插入、删除、遍历等。InsertChild(T,p,LR,c);初始条件：二叉树初始

6、条件：二叉树T T存在，存在，p p指向指向T T中某个结点，中某个结点，LRLR为为0 0或或1 1，非空二叉树，非空二叉树c c 与与T T不相交且右子树为空。不相交且右子树为空。操作结果：根据操作结果：根据LRLR为为0 0或或1 1，插入，插入c c为为T T中中p p所指结点的左或右子树。所指结点的左或右子树。p p所指结所指结 点的原有左或右子树则成为点的原有左或右子树则成为c c的右子树。的右子树。ABCc421356TpLR=0542136TpABCcInsertChild(T,p,LR,c);初始条件：二叉树初始条件：二叉树T T存在，存在，p p指向指向T T中某个结点，中

7、某个结点，LRLR为为0 0或或1 1，非空二叉树，非空二叉树c c 与与T T不相交且右子树为空。不相交且右子树为空。操作结果：根据操作结果：根据LRLR为为0 0或或1 1，插入，插入c c为为T T中中p p所指结点的左或右子树。所指结点的左或右子树。p p所指结所指结 点的原有左或右子树则成为点的原有左或右子树则成为c c的右子树。的右子树。ABCc421356TpLR=1654213TpABCcDeleteChild(T,p,LR);初始条件：二叉树初始条件：二叉树T T存在，存在，p p指向指向T T中某个结点，中某个结点，LRLR为为0 0或或1 1。操作结果：根据操作结果：根据

8、LRLR为为0 0或或1 1，删除，删除T T中中p p所指结点的左或右子树。所指结点的左或右子树。421356TpLR=0421356TpLR=1421356Tp练习练习: 给出给出InsertChild(T,p,LR,c)后的结果后的结果, 其中其中T,c如下图所示，如下图所示， LR=0。ABCc7421356TpLR=042136TpABCc57A、 二叉树的第i层上至多有2 i-1（i 1）个结点。(2) 二叉树的基本性质二叉树的基本性质423167891011121314155第三层上第三层上( (i=3)i=3)，有有2 23-13-1=4=4个节点。个节点。第四层上第四层上(

9、(i=4)i=4)，有有2 24-14-1=8=8个节点。个节点。A、 二叉树的第i层上至多有2 i-1（i 1）个结点。 B、 深度为h的二叉树中至多有2h-1个结点。(2) 二叉树的基本性质二叉树的基本性质423167891011121314155此树的深度此树的深度h=4h=4，共有共有2 24 4-1=15-1=15个节点。个节点。A、 二叉树的第i层上至多有2 i-1（i 1）个结点。B、 深度为h的二叉树中至多含有2h-1个结点。C、 若在任意一棵二叉树中，有n0个叶子结点， 有n2个度为2的结点，则：n0=n2+1(2) 二叉树的基本性质二叉树的基本性质4231678910111

10、21314155n n0 0=8=8n n2 2=7=7性质性质1：二叉树的第二叉树的第i层上至多有层上至多有2 i-1（i 1）个结点。个结点。证明：根据二叉树的特点，结论是显然的。证明：根据二叉树的特点，结论是显然的。性质性质2：深度为深度为h的二叉树中至多含有的二叉树中至多含有2h-1个结点。个结点。证明：深度为证明：深度为h的二叉树最多有的二叉树最多有h层，根据性质层，根据性质1，只要将第，只要将第1层层到第到第h层的最大结点数相加，就可得到整个二叉树中结点的最层的最大结点数相加，就可得到整个二叉树中结点的最大值。大值。21-1 + 2 2-1+ 2 h-1 = 2 h-1 性质性质3

11、：度为：度为0的结点总比度为的结点总比度为2的结点多一个的结点多一个,即即 n0= n2+1 。证明：设有证明：设有n0个叶子结点，有个叶子结点，有n1个度为个度为1的结点，有的结点，有n2个度为个度为2的结点，的结点， 则二叉树中结点总数为则二叉树中结点总数为：n=n0+n1+ n2 设所有进入分支的总数为设所有进入分支的总数为m,则总的结点个数为：则总的结点个数为：n=m+1总的射出分支与总的进入分支数相等：总的射出分支与总的进入分支数相等：m= n1+2 n2 因此：因此： n0+n1+ n2 = n1+2 n2 +1 所以：所以： n0= n2+1 （3）满二叉树）满二叉树423167

12、891011121314155特点：每一层上都含有最大结点数。特点：每一层上都含有最大结点数。4231678910 11125 非完全二叉树非完全二叉树（4）完全二叉树）完全二叉树4231678910 11125 完全二叉树完全二叉树特点：除最后一层外，每一层都取最大结点数，特点：除最后一层外，每一层都取最大结点数，最后一层结点都集中在该层最左边的若干位置。最后一层结点都集中在该层最左边的若干位置。（5）树与二叉树的区别）树与二叉树的区别A树中结点的最大度数没有限制，二叉树结点最大度数为树中结点的最大度数没有限制，二叉树结点最大度数为2。B树的结点无左、右之分，二叉树的结点子树有明确的左、右之

13、分。树的结点无左、右之分，二叉树的结点子树有明确的左、右之分。 树 二叉树2、二叉树的存储结构、二叉树的存储结构 (2) 链式存储结构链式存储结构(1) 顺序存储结构顺序存储结构(1) 顺序存储结构顺序存储结构用一组连续的存储单元存放二叉树的用一组连续的存储单元存放二叉树的数据元素。结点在数组中的相对位置数据元素。结点在数组中的相对位置蕴含着结点之间的关系。蕴含着结点之间的关系。T16若双亲结点在数组中若双亲结点在数组中i下标处，其左孩子在下标处，其左孩子在2*i处，右孩子在处，右孩子在2*i+1处。处。11 A B C F E D 1 2 4 8 910 5 6 3 7121314152h-

14、1= 24-1 = 150000FE000DC0BA15141312111098765432100一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。(2) 链式存储结构链式存储结构lchildDatarchildADBCEF图为一般二叉图为一般二叉树的二叉链表树的二叉链表结构结构AECBDF每个结点由数据域、左指针域和右指针域组成。每个结点由数据域、左指针域和右指针域组成。链式存储结构的描述：链式存储结构的描述：Typedef struct BiTNode TElemType data; struct BiTNode *lchild

15、, *rchild; BiTNode, * BiTree;lchilddatarchildlchilddatarchildlchilddatarchild6.3、 二叉树的遍历二叉树的遍历 查找某个结点，或对二叉树中全部结点进行某种处理，就需要查找某个结点，或对二叉树中全部结点进行某种处理，就需要遍历。遍历。（1）遍历定义及遍历算法）遍历定义及遍历算法 遍历遍历是指是指按某条搜索路线寻访树中每个结点，按某条搜索路线寻访树中每个结点，且每个结且每个结点只被访问一次。点只被访问一次。 按按先左后右先左后右的原则，一般使用三种遍历：的原则，一般使用三种遍历：先序遍历先序遍历(D L R): 访问根结

16、点，按先序遍历左子树，按先序遍历右子树。访问根结点，按先序遍历左子树，按先序遍历右子树。中序遍历中序遍历(L D R): 按中序遍历左子树，访问根结点，按中序遍历右子树。按中序遍历左子树，访问根结点，按中序遍历右子树。后序遍历后序遍历(L R D): 按后序遍历左子树，按后序遍历右子树，访问根结点。按后序遍历左子树，按后序遍历右子树，访问根结点。 二叉树为空时，执行空操作，即空二叉树已遍历完。二叉树为空时，执行空操作，即空二叉树已遍历完。 （2）遍历算法遍历算法先序遍历：先序遍历：D L R中序遍历：中序遍历：L D R后序遍历：后序遍历：L R DADBCT1T2T3D L RAD L RD

17、 L RBDCD L R以先序遍历以先序遍历D L RD L R为例演示遍历过程为例演示遍历过程 ABDCBDAC DBCAVoid PreOderTraverse(BiTree T)if(T! =NULL) printf (T-data); PreOrderTraverse(T-lchild); PreOrderTraverser(T-rchild); /*先序遍历先序遍历*/主程序主程序Pre( T )返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);

18、DTCprintf(C);pre(T L);C返回T左是空返回左是空返回pre(T R);T左是空返回左是空返回T右是空返回右是空返回T左是空返回左是空返回T右是空返回右是空返回pre(T R);中序遍历二叉树的递归算法：中序遍历二叉树的递归算法： void inOrderTraverse(BiTree T) if(T!=NULL) inOrderTraverse(T-lchild); printf(T-data); inOrderTraverse(T-rchild); 后序遍历二叉树的递归算法：后序遍历二叉树的递归算法： void PostOrderTraverse(BiTree T) if

19、(T!=NULL) PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); printf(T-data); 层序遍历二叉树的算法：层序遍历二叉树的算法：void LevelOrder(BiTree BT) if (!BT) exit; InitQueue(Q); p=BT; Visit(p); EnQueue(&Q,p); /*访问根结点，并将根结点入队访问根结点，并将根结点入队 */ while (!QueueEmpty(Q) /*当队非空时重复执行下列操作当队非空时重复执行下列操作*/ DeQueue(&Q,&p); /*出队出队

20、*/ if (p-lchild) Visit(p-Lchild);EnQueue(&Q,p-Lchild); if (p-rchild) Visit(p-Rchild);EnQueue(&Q,p-Rchild); （3）遍历二叉树的应用）遍历二叉树的应用 1) 建立一棵二叉树建立一棵二叉树 (在遍历过程生成结点，建立二叉树的存储结构，在遍历过程生成结点，建立二叉树的存储结构，用链式存储结构）用链式存储结构）void CreatBiTree( BiTree T ) scanf(&ch); if(ch= = ) T=NULL; else T=(BiTNode )malloc(sizeof(BiTN

21、ode); T-data=ch; /*生成根结点生成根结点*/ CreatBiTree(T-lchild); /*构造左子树构造左子树*/ CreatBiTree (T-rchild); /*构造右子树构造右子树*/ ADBCA B D CA B D C 按先序遍历按先序遍历ch=ATTAcreat(T L)T= , Creat(T) 返回creat(T R)Tch=D|=返回creat(T R)D=Tch=返回ch=DTTDcreat(T L)=|creat(T R)ch=CTTCcreat(T L)+ch=BTTBcreat(T L)Tch=BTCch=+返回creat(T R)TCch=

22、+返回ATABABD|=ABDABDC+BAABDCA B D C （2）统计二叉树中叶子结点的个数）统计二叉树中叶子结点的个数方法：对二叉树进行遍历，判断被访问的结点是否叶子结点，若是方法：对二叉树进行遍历，判断被访问的结点是否叶子结点，若是叶子结点，则将计数器加叶子结点，则将计数器加1。 实现算法：实现算法： int countleaf(BiTree T) int n1,n2; if (T= =NULL) return 0; else if (T-lchild= =NULL) & (T-rchild= =NULL) return 1; else n1=countleaf (T-lchild

23、); n2=countleaf (T-rchild); return (n1+n2); void change(BiTree T) if (T!=NULL) T-LT-R; change(T-L); change(T-R); ABCDACBDACBD练习：练习：试以二叉链表作为存储结构，将二叉树中所有结试以二叉链表作为存储结构，将二叉树中所有结点的左右子树进行交换。点的左右子树进行交换。2.5.3哈夫曼树及其应用哈夫曼树及其应用1、哈夫曼树、哈夫曼树 树的路径长度的概念：树的路径长度的概念： 从一个结点到另一个结点之间的从一个结点到另一个结点之间的分支数目分支数目称为称为这对结点之间的这对结点

24、之间的路径长度路径长度。 树的路径长度树的路径长度是从树的根结点到每一结点的是从树的根结点到每一结点的路径长度之和路径长度之和。1 12 2453 367PL=0+1+1+2+2+2+2=10树的路径长度用树的路径长度用PLPL表示。表示。1 12 2453 367PL=0+1+1+2+2+2+2=101 12 245367PL=0+1+1+2+2+3+3=12树的路径长度用树的路径长度用PLPL表示。表示。 结点的带权路径长度：结点的带权路径长度： 从该结点到树根之间的从该结点到树根之间的路径长度路径长度与与结点上权结点上权的的乘积乘积。树的带权路径长度：树的带权路径长度： 树中所有叶子结点

25、的树中所有叶子结点的带权路径长度之和带权路径长度之和。abcd7524WPL=7*2+5*2+2*2+4*2=36树的带权路径长度记作：树的带权路径长度记作： 其中：其中：Wk为树中每个叶子结点的权；为树中每个叶子结点的权； L k为每个叶子结点到根的路径长度。为每个叶子结点到根的路径长度。nkKKLWWPL1abcd7524WPL=7*2+5*2+2*2+4*2=36WPL最小的二叉树就称作最小的二叉树就称作最优二叉树最优二叉树或或哈夫曼树哈夫曼树 。abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL

26、=7*1+5*2+2*3+4*3=35 哈夫曼树哈夫曼树 （最优树）（最优树）加权路径长度最小的二叉树就加权路径长度最小的二叉树就是哈夫曼树。是哈夫曼树。公式：公式：nkKLKWWPL1675cd(b)11b57cd(c)18a711cdb5624(d)abcd7524(a)2、哈夫曼树的构造、哈夫曼树的构造Huffman算法算法例：给定权值例：给定权值7，5，2，4，构造哈夫曼树。，构造哈夫曼树。方法：方法：(1) 由原始数据生成森林；由原始数据生成森林；(2) 在森林中选取两棵根结点权值在森林中选取两棵根结点权值最小最小的和的和次小次小的二的二叉树作为左右子树构造一棵新的二叉树，其根结点的

27、叉树作为左右子树构造一棵新的二叉树，其根结点的权值为左右子树根结点权值之和。权值为左右子树根结点权值之和。规定左子树根结点规定左子树根结点的权值小于右子树根结点的权值。的权值小于右子树根结点的权值。(3) 将新的二叉树加入到森林将新的二叉树加入到森林F中，删除原来两棵权值中，删除原来两棵权值最小的树；最小的树；(4)重复重复2、3步骤，直至步骤，直至F中只剩一棵树为止。中只剩一棵树为止。练习：练习：给定权值给定权值5，15，40，30，10，构造哈夫曼树。，构造哈夫曼树。练习：练习：给定权值给定权值5，15，40，30，10，构造哈夫曼树。，构造哈夫曼树。cabde515403010练习：练习

28、：给定权值给定权值5，15，40，30，10，构造哈夫曼树。，构造哈夫曼树。15bcaed154030510练习：练习：给定权值给定权值5，15，40，30，10，构造哈夫曼树。，构造哈夫曼树。15bcae习：练习：给定权值给定权值5，15，40，30，10，构造哈夫曼树。，构造哈夫曼树。15bcaed1540305103060练习：练习：给定权值给定权值5，15，40，30，10，构造哈夫曼树。，构造哈夫曼树。15bcaed1540305103060100WPL=40*1+30*2+15*3+5*4+10*4=2053、哈夫曼树的应用、哈夫曼树的应用（1）判定树）判

29、定树在解决某些判定问题时，利用哈夫曼树可以得到最在解决某些判定问题时，利用哈夫曼树可以得到最佳判定算法。佳判定算法。例例1 将学生百分成绩按分数段分级的程序。将学生百分成绩按分数段分级的程序。若学生成绩分布是均匀的，可用图（若学生成绩分布是均匀的，可用图（a)二叉树结构二叉树结构来实现。来实现。 a60 a70 a80 a90 不及格不及格中等中等良好良好优秀优秀及格及格YNYNYNYN(a)分数分数0596069707980899099比例比例0.050.150.40.30.1 70a 80 a60 及格及格中等中等良好良好 80a90 60a70 不及格不及格优秀优秀YNYYYNNN(b) 不及格不及格Y a90 a80 a70 a60 优秀优秀中等中等及格及格良好良好YNNN(c)YYY 学生成绩分布不是均匀的情况：学生成绩分布不是均匀的情况：以比例数为权构造一棵哈夫曼以比例数为权构造一棵哈夫曼树，如（树，如（b)判断树所示。判断树所示。再将每一比较框的两次比较再将每一比较框的两次比较改为一次，可得到（改为一次，可得到（c)判定树判定树。输入输入10000个个数据，仅需进数据，仅需进行行22000次比次比较。较。 a60 a70