数据结构：第6章树A

1、1数据结构数据结构课程课程2第第1章章 绪论绪论第第2章章 线性表线性表第第3章章 栈和队列栈和队列 第第4章章 串串第第5章章 数组和广义表数组和广义表第第6 6章章 树和二叉树树和二叉树 第第7章章 图图第第9章章 查找查找第第10章章 排序排序目目 录录3第第6 6章章 树和二叉树树和二叉树（Tree & Binary Tree）6.1 树的基本概念树的基本概念6.2 二叉树二叉树6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 树和森林树和森林6.5 赫夫曼树及其应用赫夫曼树及其应用特点：特点：非线性结构，一个直接前驱，但可能有多个非线性结构，一个直接前驱，但可能有多

2、个直接后继。直接后继。（一对多，或称（一对多，或称1:n1:n）46.16.1 树的基本概念6.1.1 树的定义树的定义6.1.2 若干术语若干术语6.1.3 逻辑结构逻辑结构6.1.4 存储结构存储结构6.1.5 树的运算树的运算5注注1 1：过去许多书籍中都定义树为过去许多书籍中都定义树为n1，曾经有，曾经有“空树不是空树不是树树”的说法，但现在树的定义已修改。的说法，但现在树的定义已修改。注注2：树的定义具有树的定义具有递归性递归性，即，即“树中还有树树中还有树”。由一个或多个由一个或多个( (n0n0) )结点组成的有限集合结点组成的有限集合T T，有且仅有，有且仅有一一个结点称为根个

3、结点称为根（rootroot），），当当n1n1时，其余的结点分为时，其余的结点分为m m(m0)(m0)个个互不相交的互不相交的有限集合有限集合T1,T2T1,T2，TmTm。每个集合本身又是棵树，。每个集合本身又是棵树，被称作这个根的被称作这个根的子树子树 。6即上层的那个结点即上层的那个结点(直接前驱直接前驱)即下层结点的子树的根即下层结点的子树的根(直接后继直接后继)同一双亲下的同层结点（孩子之间互称兄弟）同一双亲下的同层结点（孩子之间互称兄弟）即双亲位于同一层的结点（但并非同一双亲）即双亲位于同一层的结点（但并非同一双亲）即从根到该结点所经分支的所有结点即从根到该结点所经分支的所有结

4、点即该结点下层子树中的任一结点即该结点下层子树中的任一结点ABCGEIDHFJFLK 根根 叶子叶子 森林森林有序树有序树无序树无序树即根结点即根结点(没有前驱没有前驱)即终端结点即终端结点(没有后继没有后继)指指m棵不相交的树的集棵不相交的树的集合合(例如删除例如删除A后的子树个数后的子树个数)双亲双亲孩子孩子兄弟兄弟堂兄弟堂兄弟祖先祖先子孙子孙结点各子树从左至右有序，不能互换（左为第一）结点各子树从左至右有序，不能互换（左为第一）结点各子树可互换位置。结点各子树可互换位置。7即树的数据元素即树的数据元素结点挂接的子树数结点挂接的子树数结点结点结点的度结点的度结点的层次结点的层次终端结点终端

5、结点分支结点分支结点树的度树的度树的深度树的深度(或高度或高度)ABCGEIDHFJFLK从根到该结点的层数（根结点算第一层）从根到该结点的层数（根结点算第一层）即度为即度为0的结点，即叶子的结点，即叶子即度不为即度不为0的结点（也称为内部结点）的结点（也称为内部结点）所有结点度中的最大值（所有结点度中的最大值（Max各结点的度各结点的度）指所有结点中最大的层数（指所有结点中最大的层数（Max各结点的层次各结点的层次）问：问：右上图中的结点数右上图中的结点数 ；树的度；树的度 ；树的深度；树的深度13133 34 4（有几个直接后继就是几度，亦称（有几个直接后继就是几度，亦称“次数次数”）8树

6、的抽象数据类型定义树的抽象数据类型定义（见教材（见教材P118-119P118-119）ADT TreeADT Tree数据对象数据对象D:D:数据关系数据关系R:R:基本操作基本操作 P P：ADT TreeADT TreeD是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。若若D为空集，则称为空树；为空集，则称为空树；/允许允许n=0若若D中仅含一个数据元素，则中仅含一个数据元素，则R为空集；为空集；其他情况下的其他情况下的R存在二元关系：存在二元关系： root 唯一唯一 /关于根的说明关于根的说明 DjDk= /关于子树不相交的说明关于子树不相交的说明 /关于数据元素的说

7、明关于数据元素的说明 /至少有至少有15个，如求树深，求某结点的双亲个，如求树深，求某结点的双亲9一对多（一对多（1:n1:n），），有多个直接后继（如家谱有多个直接后继（如家谱树、目录树等等），但只有一个根结点，树、目录树等等），但只有一个根结点，且且子树之间互不相交。子树之间互不相交。 讨论讨论1：树是非线性结构，该怎样存储？树是非线性结构，该怎样存储？特点：特点：仍然有顺序存储、链式存储等方式。仍然有顺序存储、链式存储等方式。 10讨论讨论3：树的链式存储方案应该怎样制定？树的链式存储方案应该怎样制定？复原困难复原困难可用多重链表：可用多重链表：一个前趋指针，一个前趋指针，n n个后继指

8、针。个后继指针。 细节问题：细节问题： 树中结点的结构类型样式该如何设计？树中结点的结构类型样式该如何设计？ 即应该设计成即应该设计成“等长等长”还是还是“不等长不等长”？ 缺点：缺点： 等长结构太浪费（每个结点的度不一定相同）；等长结构太浪费（每个结点的度不一定相同）； 不等长结构太复杂（要定义好多种结构类型）。不等长结构太复杂（要定义好多种结构类型）。可否规定为：可否规定为： 从上至下、从左至右将树的结点依次存入内存。从上至下、从左至右将树的结点依次存入内存。有重大缺陷：有重大缺陷：不能唯一复原就没有实用价值！不能唯一复原就没有实用价值！讨论讨论2：树的顺序存储方案应该怎样制定？树的顺序存

9、储方案应该怎样制定？datalink 1 link 2 .link n.困惑困惑：到底到底应当开多少个链域应当开多少个链域? ?补充：树的补充：树的5种表示法：种表示法：v 图形表示法图形表示法v 嵌套集合表示法嵌套集合表示法v 广义表表示法广义表表示法v 凹入表示法凹入表示法v 左孩子右兄弟表示法左孩子右兄弟表示法意义：把一般的树转化为最简单、最有规律意义：把一般的树转化为最简单、最有规律的二叉树再研究，然后设法从二叉树再转回的二叉树再研究，然后设法从二叉树再转回多叉树。多叉树。12教师教师学生学生其他人员其他人员20052005级级20062006级级20072007级级20082008级

10、级华中科技大学华中科技大学计算机系计算机系电信系电信系控制系控制系叶子叶子根根子树子树1314( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) 约定：约定：根根作为由子树森林组成的作为由子树森林组成的表的名字写在表的左边表的名字写在表的左边15又称目录表示法又称目录表示法16data左孩子左孩子 右兄弟右兄弟意义：多叉树转为二叉树！意义：多叉树转为二叉树！17方法：方法：加线加线抹线抹线旋转旋转 abeidfhgc树转二叉树举例：树转二叉树举例：abeidfhgc兄弟相连兄弟相连长兄为父长兄为父孩子靠左孩子靠左18讨论讨论：二叉

11、树怎样还原为树？二叉树怎样还原为树？abeidfhgc要点：要点：逆操作，把逆操作，把所有右孩子变为兄弟所有右孩子变为兄弟！ abdefhgic19要明确：要明确：1. 普通树（即多叉树）若不转化为二叉树，则运算很难实现。普通树（即多叉树）若不转化为二叉树，则运算很难实现。2. 二叉树的运算仍然是插入、删除、修改、查找、排序等，但二叉树的运算仍然是插入、删除、修改、查找、排序等，但这些操作必须建立在这些操作必须建立在对树结点能够对树结点能够“遍历遍历”的基础上！的基础上！本章重点：本章重点：二叉树的表示和实现二叉树的表示和实现206.2 二叉树二叉树为何要重点研究每结点最多只有两个为何要重点研

12、究每结点最多只有两个 “叉叉” 的树？的树？二叉树的结构最简单，规律性最强；二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，可以证明，所有树都能转为唯一对应的二叉树，不失一般性。不失一般性。6.2.1 二叉树的定义二叉树的定义6.2.2 二叉树的性质二叉树的性质6.2.3 二叉树的存储结构二叉树的存储结构注：二叉树最重要的运算是：遍历！注：二叉树最重要的运算是：遍历！21定义：定义：是是n（n0）个结点的有限集合，由一个根结点以及两）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为棵互不相交的、分别称为左子树和右子树左子树和右子树的二叉树组成的二叉树组成 。

13、逻辑结构：逻辑结构： 一对二（一对二（1:2） 基本特征基本特征: 每个结点最多只有两棵子树（不存在度大于每个结点最多只有两棵子树（不存在度大于2 2的结点）；的结点）； 左子树和右子树左子树和右子树次序不能颠倒次序不能颠倒。 基本形态：基本形态：一般的树一般的树有几种？有几种？22二叉树的抽象数据类型定义二叉树的抽象数据类型定义（见教材（见教材P P121-122121-122）ADT BinaryTree数据对象数据对象D:数据关系数据关系R:基本操作基本操作 P：ADT BinaryTreeD是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。若若D=，则，则R= ；若若D，

14、则，则R= H；存在二元关系：；存在二元关系： root 唯一唯一 /关于根的说明关于根的说明 DjDk= /关于子树不相交的说明关于子树不相交的说明 /关于数据元素的说明关于数据元素的说明 /关于左子树和右子树的说明关于左子树和右子树的说明 /至少有至少有20个，如返回某结点的左孩子，个，如返回某结点的左孩子，或中序遍历，等等或中序遍历，等等23讨论讨论1 1：第第i i层的结点数最多是多少？层的结点数最多是多少？ （利用二进制性质可轻松求出）（利用二进制性质可轻松求出） 性质性质1:1: 性质性质2:2: 再提问：再提问：第第i i层上至少有层上至少有 个结点？个结点？1 1讨论讨论2 2

15、：深度为深度为k k的二叉树，最多有多少个结点？的二叉树，最多有多少个结点？ （利用二进制性质可轻松求出）（利用二进制性质可轻松求出）243. 3. 深度为深度为9 9的二叉树中至少有的二叉树中至少有 个结点。个结点。 ) )9 9 ) )8 8 ) ) ) )9 91 12.2.深度为的二叉树的结点总数，最多为深度为的二叉树的结点总数，最多为 个。个。 ) )k-1k-1 ) log) log2 2k k ) ) k k ) )k k1. 1. 树中各结点的度的最大值称为树的树中各结点的度的最大值称为树的 。 ) ) 高度高度 ) ) 层次层次 ) ) 深度深度 ) ) 度度DCC课堂练习：

16、课堂练习：25性质性质3: 3: 对于任何一棵二叉树，若对于任何一棵二叉树，若2 2度的结点数有度的结点数有n n2 2个，个，则叶子数（则叶子数（n n0 0）必定为必定为n n2 21 1 （即（即n0=n2+1）二叉树中全部结点数二叉树中全部结点数nn0+n1+n2( (叶子数叶子数1 1度结点数度结点数2 2度结点数度结点数) )二叉树中全部结点数二叉树中全部结点数nB+1 ( ( 总分支数根结点总分支数根结点 ) ) （除根结点外，每个结点必有一个直接前趋，即一个分支）（除根结点外，每个结点必有一个直接前趋，即一个分支）总分支数总分支数B= n1+2n2 (1(1度结点必有度结点必有

17、1 1个直接后继，个直接后继，2 2度结点必有度结点必有2 2个个) )n0+n1+n2= n1+2n2 +1, 即即n0=n2+1讨论：二叉树的叶子数和度为讨论：二叉树的叶子数和度为2 2的结点数之间有关系吗？的结点数之间有关系吗？26完全二叉树：完全二叉树：深度为深度为k 的的、有有n个结点个结点的二叉树，当且仅当其每一个结点都与的二叉树，当且仅当其每一个结点都与深度为深度为k 的满二叉树中编号从的满二叉树中编号从1至至n的结的结点一一对应。点一一对应。AOBCGEKDJFIHNML深度为深度为4 4的满二叉树的满二叉树完全二叉树完全二叉树ABCGEIDHFJ为何要研究为何要研究这两种特殊

18、这两种特殊形式？形式？讨论：满二叉树：讨论：满二叉树：一棵深度为一棵深度为k 且有且有2k -1个结点的二叉树。个结点的二叉树。 （特点：每层都（特点：每层都“充满充满”了结点）了结点）刘解释：完全二叉树的特点是只有最后一层叶子不满，刘解释：完全二叉树的特点是只有最后一层叶子不满，且全部集中在左边。但这其实是且全部集中在左边。但这其实是顺序二叉树顺序二叉树的含义。而的含义。而图论图论中的中的“完全二叉树完全二叉树”是指是指n1=0的情况。的情况。满二叉树和完全二叉树有什么区别？满二叉树和完全二叉树有什么区别？答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前答：满二叉树是叶子一个也不少的树，

19、而完全二叉树虽然前k-k-1 1层是满的，但最底层却允许在右边缺少连续若干个结点。满层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。二叉树是完全二叉树的一个特例。27证明：证明：根据性质根据性质2 2，深度为深度为k k的二叉树最多只有的二叉树最多只有2 2k k-1-1个结点，且个结点，且完全二叉树的定义是与同深度的满二叉树前面编号相同，即它完全二叉树的定义是与同深度的满二叉树前面编号相同，即它的总结点数的总结点数n n位于位于k k层和层和k-1k-1层满二叉树容量之间，层满二叉树容量之间，即即 2 2k-1k-1-1n2-1n2k k-1 -1 或或2

20、2k-1k-1n2n2k k三边同时取对数，于是有：三边同时取对数，于是有：k-1logk-1log2 2nk nlchild); printf(“%d”,root-data); LDR(root-rchild); return(0);LRD (node *root)if(root !=NULL) LRD(root-lchild); LRD(root-rchild); printf(“%d”,root-data); return(0);typedef struct nodeint data; struct node *lchild,*rchild； node;node *root; A B C

21、D EDLR( node *root )if (root !=NULL) /非空二叉树非空二叉树 printf(“%d”,root-data); /访问访问D DDLR(root-lchild); /递归遍历左子树递归遍历左子树DLR(root-rchild); /递归遍历右子树递归遍历右子树 return(0); 39对遍历的分析：对遍历的分析：1. 从前面的三种遍历算法可以知道：如果将从前面的三种遍历算法可以知道：如果将print语句抹去，语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的遍历算法的访问路径是相同的，

22、只是访问结点的时机不同。访问路径是相同的，只是访问结点的时机不同。从虚线的出发点到终点的路径从虚线的出发点到终点的路径上，每个结点经过上，每个结点经过3次次。AFEDCBG第第1次次经过时访问，是经过时访问，是先序先序遍历遍历第第2次次经过时访问，是经过时访问，是中序中序遍历遍历第第3次次经过时访问，是经过时访问，是后序后序遍历遍历2. 2. 二叉树遍历的时间效率和空间效率二叉树遍历的时间效率和空间效率时间效率时间效率: : /每个结点只访问一次每个结点只访问一次空间效率空间效率: : /栈占用的最大辅助空间栈占用的最大辅助空间精确值：树深为精确值：树深为k k的递归遍历需要的递归遍历需要k+

23、1k+1个辅助单元个辅助单元40例：例：【严题集严题集6.426.42】编写递归算法，计算二叉树编写递归算法，计算二叉树中叶子结点的数目。中叶子结点的数目。 思路：思路：叶子的特点？左右指针均空！叶子的特点？左右指针均空！ 可选用任何一种遍历算法查找叶子，将其统计并打印出来。可选用任何一种遍历算法查找叶子，将其统计并打印出来。 DLR(node *root) /采用先序遍历的递归算法采用先序遍历的递归算法 if ( root!=NULL ) /非空二叉树条件，等效于非空二叉树条件，等效于 if(rootif(root) ) if(!root-lchild&!root-rchild) /

24、是叶子结点则统计并打印是叶子结点则统计并打印 sum+; printf(%dn,root-data); DLR(root-lchild); /递归遍历左子树，直到叶子处；递归遍历左子树，直到叶子处； DLR(root-rchild); / /递归遍历右子树，直到叶子处；递归遍历右子树，直到叶子处； return(0); 41用空格字符表示用空格字符表示无孩子无孩子或指针或指针为空为空如何如何把二叉树存入电脑内？把二叉树存入电脑内？怎样建树？见教材怎样建树？见教材P131P131例例例：将下面的二叉树以二叉链表形式存入计算机内。例：将下面的二叉树以二叉链表形式存入计算机内。考虑考虑1 1：输入结

25、点时怎样表示：输入结点时怎样表示“无孩子无孩子”？考虑考虑2 2：以何种遍历方式来输入和建树？：以何种遍历方式来输入和建树？将二叉树将二叉树按先序遍历按先序遍历次序输入：次序输入：A B C D E G F (/n)以先序遍历最为合以先序遍历最为合适，让每个结点都适，让每个结点都能及时被连接到位。能及时被连接到位。字符串输完后字符串输完后应当再应当再加一特殊的结束符号加一特殊的结束符号(如如$)，因为，因为 无无法惟一表示结束。法惟一表示结束。42建树算法：建树算法：Status CreateBiTree( BiTree &T ) /构造二叉树构造二叉树T T scanf(“%c”,&ch); if(ch= )T=NULL; /立即结束立即结束 else if(!(T=( BiTNode*)malloc(sizeof(BiTNode)exit(overflow); T-data=ch; /生成根结点生成根结点 CreateBiTree(T-lchild); /构造左子树构造左子树 CreateBiTree(T-rchild); /构造右子树构造右子树 ret