ch6-1树和二叉树

1、1数据结构课程的内容：数据结构课程的内容：26.1 树的基本树的基本概念概念6.2 二叉树二叉树6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 树和森林树和森林6.5 赫夫曼树及其应用赫夫曼树及其应用特点：特点：非线性结构，一个直接前驱，但可能有多个非线性结构，一个直接前驱，但可能有多个直接后继。直接后继。（一对多或（一对多或1:n1:n）二叉树的定义、二叉树的定义、性质和存储结构性质和存储结构二叉树的运算二叉树的运算第第6 6章章 树和二叉树树和二叉树（Tree & Binary TreeTree & Binary Tree）36.1 树的基本概念树的基本概念一、

2、树的定义一、树的定义二、若干术语二、若干术语三、逻辑结构三、逻辑结构四、存储结构四、存储结构五、树的运算五、树的运算数据元素之间是一种层次关系数据元素之间是一种层次关系4一、一、 树的定义树的定义注注1：过去许多书籍中都定义树为过去许多书籍中都定义树为n1，曾经有，曾经有“空树不是树空树不是树”的说法，但现在树的定义已的说法，但现在树的定义已修改。修改。注注2：树的定义具有树的定义具有递归性递归性，即，即“树中还有树树中还有树”。由由n n个个( (n0n0) )结点组成的有限集合结点组成的有限集合T T，有且仅有，有且仅有一一个结点称为根个结点称为根（rootroot），），当当n1n1时，

3、其余的结点分为时，其余的结点分为m m(m0)(m0)个个互不相交互不相交的有限集合的有限集合T T1 1,T,T2 2，T Tm m。每个。每个集合本身又是棵树，被称作这个根的集合本身又是棵树，被称作这个根的子树子树 。递归定义：递归定义：5ABCDEFGHIJMKLA( )T1T3T2树根例如例如: :B(E, F(K, L), C(G), D(H, I, J(M)6二、二、 若干术语若干术语上层的那个结点上层的那个结点( (直接前驱直接前驱) )下层结点的子树的根下层结点的子树的根( (直接后继直接后继) )同一双亲的孩子之间互称兄弟同一双亲的孩子之间互称兄弟从根到该结点所经分支的所有结

4、点从根到该结点所经分支的所有结点该结点下层子树中的任一结点该结点下层子树中的任一结点叶子节点叶子节点: :根结点根结点( (没有前驱没有前驱) )双亲双亲:孩子孩子:兄弟兄弟:祖先祖先:子孙子孙:树的数据元素及若干指向其子树的分支树的数据元素及若干指向其子树的分支结点的度结点的度(degree):结点结点: :结点拥有的子树个数。结点拥有的子树个数。根（根（rootroot）: :终端结点终端结点( (没有后继没有后继),),即度为即度为0 0的节点的节点分支节点分支节点: : 即度不为即度不为0 0的结点的结点（也称为内部结点，非终端结点）（也称为内部结点，非终端结点）7结点的层次结点的层次

5、:堂兄弟堂兄弟:树的度树的度: :树的深度树的深度: :( (或高度或高度) )从根到该结点的层数（根结点算第一层）从根到该结点的层数（根结点算第一层）双亲位于同一层的结点双亲位于同一层的结点所有结点度中的最大值（所有结点度中的最大值（MaxMax各结点各结点 的度的度 ）指所有结点中最大的层次（指所有结点中最大的层次（MaxMax各结各结 点的层次点的层次 ）问：上图中的结点数问：上图中的结点数 ；树的度；树的度 ；树的深度；树的深度13133 34 4EFBAGKLMHIJCDB B、C C、D D是是A A的孩子。的孩子。 A A 是是B B、C C 、D D的双亲。的双亲。 结点结点H

6、 H、I I、 J J互为兄弟结点。互为兄弟结点。12348() 有确定的根；有确定的根；() 树根和子树根之间为有向关系。树根和子树根之间为有向关系。有向树：有向树：有序树：有序树： 子树之间存在确定的次序关系。子树之间存在确定的次序关系。无序树：无序树：子树之间不存在确定的次序关系。子树之间不存在确定的次序关系。任何一棵非空树是一个二元组任何一棵非空树是一个二元组 Tree = Tree = （rootroot，F F）其中：其中：root root 被称为根结点，被称为根结点， F F 被称为子树森林被称为子树森林指指m m棵棵互不相交的互不相交的树的集合树的集合森林：森林：9三、树的逻

7、辑结构三、树的逻辑结构 特点：特点：线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 ( (无前驱无前驱) )最后一个数据元素最后一个数据元素 (无后继无后继) 根结点根结点 ( (无前驱无前驱) )多个叶子结点多个叶子结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 多个后继多个后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 一个后继一个后继) )一对多一对多（1:n1:n），有多个直接后继（如家谱），有多个直接后继（如家谱树、目录树、网页链接等等），但只有树、目录树、网页链接等等），但只有一一个根结点个根结点，且，且子树之间互不相交

8、。子树之间互不相交。10讨论讨论1 1：树是非线性结构，该怎样存储？：树是非线性结构，该怎样存储？仍然有顺序存储、链式存储等方式。仍然有顺序存储、链式存储等方式。 讨论讨论2 2：树的：树的顺序存储顺序存储方案应该怎样制定？方案应该怎样制定？可规定为：可规定为：从上至下、从左至右将树的结点依次存从上至下、从左至右将树的结点依次存入内存。入内存。重大缺陷：重大缺陷： 复原困难复原困难讨论讨论3：树的：树的链式存储链式存储方案应该怎样制定？方案应该怎样制定？可用多重链表：可用多重链表：一个前趋指针，一个前趋指针，n n个后继指针。个后继指针。11细节问题细节问题: :树中结点的结构类型样式该如何设

9、计？树中结点的结构类型样式该如何设计？ 即应该设计成即应该设计成“等长等长”还是还是“不等长不等长”？缺点缺点: :等长结构太浪费（每个结点的度不一定相同）；等长结构太浪费（每个结点的度不一定相同）； 不等长结构太复杂（要定义好多种结构类型）。不等长结构太复杂（要定义好多种结构类型）。先研究最简单、最有规律的树，然先研究最简单、最有规律的树，然后设法把一般的树转化为简单树。后设法把一般的树转化为简单树。解决思路：解决思路： 因为树是一种非线性结构，所以不能简单地用一因为树是一种非线性结构，所以不能简单地用一维数组或单链表来存储树。为了存储树，必须把树维数组或单链表来存储树。为了存储树，必须把树

10、中每个结点之间存在的关系反映在存储结构之中，中每个结点之间存在的关系反映在存储结构之中，才能如实的表现一棵树。才能如实的表现一棵树。 补充：树的补充：树的4 4种表示法：种表示法：v 图形表示法图形表示法v 嵌套集合表示法嵌套集合表示法v 广义表表示法广义表表示法v 凹入表示法凹入表示法13图形表示法图形表示法教师教师学生学生其他人员其他人员20102010级级 20112011级级 20122012级级20132013级级武汉理工大学武汉理工大学计算机系计算机系数学系数学系自控系自控系叶子叶子根根子树子树14嵌套集合表示法嵌套集合表示法15( A ( B ( E ( K, L ), F ),

11、 C ( G ), D ( H ( M ), I, J ) ) 约定：约定：根根作为由子树森林组成的作为由子树森林组成的表的名字写在表的左边表的名字写在表的左边广义表表示法广义表表示法16凹入表示法凹入表示法又称目录表示法又称目录表示法17五、树的运算五、树的运算 本章重点：本章重点：二叉树的表示和实现二叉树的表示和实现1. 1. 普通树（即多叉树）若不转化为二叉树，则运算普通树（即多叉树）若不转化为二叉树，则运算很难实现。很难实现。2. 2. 二叉树的运算仍然是插入、删除、修改、查找孩二叉树的运算仍然是插入、删除、修改、查找孩子或者双亲、排序等，但这些操作必须建立在子或者双亲、排序等，但这些

12、操作必须建立在对对树结点能够树结点能够“遍历遍历”的基础上！的基础上！186.2 6.2 二叉树二叉树一、一、 二叉树的定义二叉树的定义二、二、 二叉树的性质二叉树的性质三、三、 二叉树的存储结构二叉树的存储结构注：二叉树的运算见注：二叉树的运算见6.36.3节节遍历遍历为何要重点研究每结点最多只有两个为何要重点研究每结点最多只有两个 “叉叉” 的树？的树？（1 1）二叉树的结构最简单，规律性最强；）二叉树的结构最简单，规律性最强；（2 2）可以证明所有树都能转为唯一对应的二叉树。）可以证明所有树都能转为唯一对应的二叉树。19一、二叉树的定义一、二叉树的定义定义：定义：是是n（n0）个结点的有

13、限集合，由一个根结）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为点以及两棵互不相交的、分别称为左子树和右左子树和右子树子树的二叉树组成的二叉树组成 。逻辑结构：逻辑结构： 一对二（一对二（1:2） 基本特征基本特征: : 每个结点最多只有两棵子树（不存在度大于每个结点最多只有两棵子树（不存在度大于2 2的的结点）；结点）； 左子树和右子树左子树和右子树次序不能颠倒次序不能颠倒。由此定义可以看出，一个二叉树中的每个结点只能含由此定义可以看出，一个二叉树中的每个结点只能含有有0 0、 1 1或或2 2个孩子，而且每个孩子有左右之分。个孩子，而且每个孩子有左右之分。把位于左边的孩子叫做

14、把位于左边的孩子叫做左孩子左孩子，位于右边的孩子叫做位于右边的孩子叫做右孩子右孩子。 二叉树或为空树空树；或是由一个根结根结点点加上两棵两棵分别称为左子树左子树和右子树的、互不相交的互不相交的二叉树二叉树组成。ABCDEFGHK根结点左子树右子树21二叉树的二叉树的5 5种基本形态：种基本形态： 有有5种种（1 1）左右子树不为空（）左右子树不为空（2)2)只有左子树（只有左子树（3 3）只有右子树（）只有右子树（4 4）只有根节点（）只有根节点（5 5）空树）空树22 二叉树的基本操作二叉树的基本操作（1 1）构造一棵二叉树）构造一棵二叉树T T InitBiTreeInitBiTree (

15、&T) (&T)（2 2）清空以）清空以T T为根的二叉树为根的二叉树ClearBiTree(&TClearBiTree(&T) )（3 3）判断二叉树）判断二叉树T T是否为空是否为空 BiTreeEmpty(TBiTreeEmpty(T) )（4 4）获取给定结点）获取给定结点e e的左孩子和右孩子的左孩子和右孩子 LeftChild(T,eLeftChild(T,e) )，RightChild(T,eRightChild(T,e) )（5 5）获取给定结点）获取给定结点e e的双亲的双亲 Parent(T,eParent(T,e) )（6 6）遍历二叉树）

16、遍历二叉树 Traverse(TTraverse(T) )23l性质性质1: 在二叉树的第在二叉树的第i层上至多有层上至多有2i-1个结点个结点(i1)。 证明：证明： 用数学归纳法。用数学归纳法。 1) 当当i=1时，整个二叉树只有一根结点，此时时，整个二叉树只有一根结点，此时2i-1=20=1，结论成立。结论成立。 2) 设设i=k时结论成立，即第时结论成立，即第k层上结点总数最多为层上结点总数最多为2k-1个。个。 现证明当现证明当i=k+1时，时， 结论成立：结论成立： 因为二叉树中每个结点的度最大为因为二叉树中每个结点的度最大为2，则第，则第k+1层的结点层的结点总数最多为第总数最多

17、为第k层上结点最大数的层上结点最大数的2倍，即倍，即22k-1=2(k+1)-1，故结论成立。故结论成立。 度为度为m的树中第的树中第i层上至多有层上至多有mi-1个结点个结点, (i1)。二、二叉树的性质二、二叉树的性质 (3+2)24l性质性质2: 深度为深度为k的二叉树至多有的二叉树至多有2k-1个结点（个结点（k1）。 证明：因为深度为证明：因为深度为k的二叉树，其结点总数的最大值的二叉树，其结点总数的最大值是将二叉树每层上结点的最大值相加，所以深度为是将二叉树每层上结点的最大值相加，所以深度为k的二的二叉树的结点总数至多为叉树的结点总数至多为 kikikii111122层上的最大结点

18、个数第深度为深度为k的的m叉树至多有叉树至多有 个结点。个结点。11kmm101111.1kkikimmmmmm25l 性质性质3: 3: 对任意一棵二叉树，若终端结点数（度为对任意一棵二叉树，若终端结点数（度为0 0的节的节点数）为点数）为n0，度为，度为2 2的结点数为的结点数为n2，则，则n0=n2+1。 证明：设二叉树中结点总数为证明：设二叉树中结点总数为n，n1为二叉树中度为为二叉树中度为1 1的结点总数，的结点总数，设二叉树中分支数目为设二叉树中分支数目为B 。 n=n0+n1+n2 ( (叶子数叶子数1 1度结点数度结点数2 2度结点数度结点数) ) 除根结点外，每个结点均对应一

19、个进入它的分支：除根结点外，每个结点均对应一个进入它的分支： n=B+1 二叉树中的分支都是由度为二叉树中的分支都是由度为1和度为和度为2的结点发出的结点发出 B=n1+2n2( ( 总分支数根结点总分支数根结点 ) )(1(1度结点必有度结点必有1 1个直接后继，个直接后继，2 2度结点必有度结点必有2 2个个直接后继直接后继) )26l满二叉树满二叉树： 深度为深度为k且有且有2k-1个结点的二叉树。在满二叉树中，个结点的二叉树。在满二叉树中，每层结点都是满的，即每层结点都具有最大结点数。每层结点都是满的，即每层结点都具有最大结点数。 满二叉树的顺序表示，即从二叉树的根开始，满二叉树的顺序

20、表示，即从二叉树的根开始， 层间层间从上到下，从上到下， 层内从左到右，逐层进行编号（层内从左到右，逐层进行编号（1， 2， ， n）。）。12345678910111213141527l完全二叉树完全二叉树： 深度为深度为k，结点数为，结点数为n的二叉树，的二叉树，如果其结点如果其结点1n的的位置序号分别与满二叉树的结点位置序号分别与满二叉树的结点1n的位置序号一一对的位置序号一一对应，则为完全二叉树，应，则为完全二叉树， 满二叉树必为完全二叉树，满二叉树必为完全二叉树， 而完全二叉树不一定而完全二叉树不一定是满二叉树。是满二叉树。 12345678910111213141528l 性质性质

21、4：具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1或或 log2(n+1) 。 证明：设证明：设n个结点的完全二叉树的深度为个结点的完全二叉树的深度为k，根据，根据性质性质2有有 2k-1-1n 2k-1 可得可得 2k-1n 2k， 即即 k-1log2n k 因为因为k是整数，所以是整数，所以k-1= log2n ，k= log2n +1,故结论成立。故结论成立。 又或者：又或者：2k-1n +12k k-1 log2(n+1) k k= log2(n+1) 123456789101112131415 3.23.2 =3; =3; 3.23.2 =4=4

22、29l性质性质5:对完全二叉树中编号为对完全二叉树中编号为i的结点的结点(1in,n1,n为为结点数结点数)有：有：(1)(1)若若i=1,i=1,则结点则结点i i是二叉树的根，无双亲。是二叉树的根，无双亲。 若若i1,i1,则它的双亲结点的编号为则它的双亲结点的编号为 i/2i/2 。当当i i为偶数为偶数时时, ,其双亲结点的编号为其双亲结点的编号为i/2,i/2,它是双亲结点的左孩子结它是双亲结点的左孩子结点点, ,当当i i为奇数时为奇数时, ,其双亲结点的编号为其双亲结点的编号为(i-1)/2,(i-1)/2,它是双它是双亲结点的右孩子结点。亲结点的右孩子结点。 A B C D E

23、 H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完完 全全 二二 叉叉 树树 30(2)若编号为若编号为i的结点有左孩子结点的结点有左孩子结点,则其左孩子结点则其左孩子结点的编号为的编号为2i；若编号为；若编号为i的结点有右孩子结点的结点有右孩子结点,则其则其右孩子结点的编号为右孩子结点的编号为(2i+1)。当当2in，则结点，则结点i无左孩子，无左孩子则结点无左孩子，无左孩子则结点i为叶为叶子结点；当子结点；当2i+1n，则结点无右孩子。，则结点无右孩子。 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 1 0 11 完完 全全 二二

24、 叉叉 树树 L L121231(3)(3)若若n n为奇数为奇数, ,则每个分支结点都既有左孩子结点则每个分支结点都既有左孩子结点, ,也有右孩子结点；也有右孩子结点；若若n n为偶数为偶数, ,则编号最大的分支结则编号最大的分支结点点( (编号为编号为n/2)n/2)只有左孩子结点只有左孩子结点, ,没有右孩子结点没有右孩子结点, ,其余分支结点都有左、右孩子结点。其余分支结点都有左、右孩子结点。 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 1 0 11 完完 全全 二二 叉叉 树树 L L121232讨论：讨论：满二叉树和完全二叉树有什么区别？满二叉树

25、和完全二叉树有什么区别？答：满二叉树是叶子一个也不少的树，而完全二叉树答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前虽然前k-1k-1层是满的，但最底层却允许在右边缺少连层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。续若干个结点。满二叉树是完全二叉树的一个特例。为何要研究这两为何要研究这两种特殊形式？种特殊形式？333. 3. 深度为深度为9 9的二叉树中至少有的二叉树中至少有 个结点。个结点。 ) )9 9 ) )8 8 ) ) ) )9 91 12.2.深度为的二叉树的结点总数，最多为深度为的二叉树的结点总数，最多为 个。个。 ) )k-1k-1

26、) log) log2 2k k ) ) k k ) )k k1. 1. 树中各结点的度的最大值称为树的树中各结点的度的最大值称为树的 。 ) ) 高度高度 ) ) 层次层次 ) ) 深度深度 ) ) 度度DCC课堂练习：课堂练习：34 一棵完全二叉树有一棵完全二叉树有1000个结点，则它必有个结点，则它必有 个个叶子结点，有叶子结点，有 个度为个度为2的结点，有的结点，有 个结点只个结点只有非空左子树，有有非空左子树，有 个结点只有非空右子树。个结点只有非空右子树。例：例：0 0分析题意：已知分析题意：已知n=1000,n=1000,求求n n0 0和和n n2 2, ,还要判断末叶子是还要

27、判断末叶子是挂在左边还是右边？挂在左边还是右边？答案：答案：因为最后一个结点编号因为最后一个结点编号10001000是偶数，所以它必为编号为是偶数，所以它必为编号为500500的的节点的左子树。因此，度为节点的左子树。因此，度为1 1的节点数为的节点数为1 1个，即个，即n1=1n1=1，有，有1 1个个结点只有非空左子树结点只有非空左子树全部叶子数全部叶子数n n0 0 , ,则根据性质则根据性质3 3，度为，度为2 2的结点数的结点数n n2 2n n0 01 1。由：由：1000=n1000=n0 0+n+n2 2+1 +1 故：故：n n0 0=500, n=500, n2 2=499

28、.=499.请注意：请注意：叶子结点总数叶子结点总数末层叶子数！末层叶子数！50049935三、三、 二叉树的存储结构二叉树的存储结构1 1、顺序存储、顺序存储对完全二叉树的结点对完全二叉树的结点按按“自上而下、从左自上而下、从左至右至右”编号，用一组编号，用一组连续的存储单元存储。连续的存储单元存储。将编号为将编号为i i的结点存储的结点存储在在i-1i-1号单元中。号单元中。012345678#define MAX_TREE_SIZE 100 #define MAX_TREE_SIZE 100 / / 二叉树的最大结点数二叉树的最大结点数typedeftypedef TElemTypeTE

29、lemType SqBiTreeMAX_TREE_SIZESqBiTreeMAX_TREE_SIZE; ; / 0/ 0号单元存储根结点号单元存储根结点SqBiTreeSqBiTree btbt; ;79563412836讨论：讨论：不是完全二叉树怎么办？不是完全二叉树怎么办？答：答：一律转为完全二叉树！一律转为完全二叉树！方法很简单，将各层空缺处统统补上方法很简单，将各层空缺处统统补上“虚结点虚结点”，其，其内容为空。内容为空。01234567815ABECD缺点缺点：浪费空间；浪费空间； 插入、删除不便插入、删除不便 37ABCD(a) 单支二叉树ABCD(b) 顺 序 存 储 结 构13715 A B C D E H I J K F G