《树和二叉树》PPT课件.ppt

1、数据结构第六章树和二叉树,本章内容 6.1 树的概念与基本术语 6.2 二叉树 6.3 遍历二叉树 6.4 线索二叉树 6.5 树与森林 6.6 赫夫曼树,6-3,6 树,【学习指南】 本章是整个课程的学习重点，也是整个课程中的一大难点。 这一章中我们从顺序式的数据结构，转向层次式的数据结构。考研的角度上： 要掌握树、二叉树的各种性质； 树和二叉树的不同存储结构； 森林、树和二叉树之间的转换； 线索化二叉树、二叉树的应用(二叉排序树、平衡二叉树和Huffman树)； 重点要熟练掌握的，是森林、树以及二叉树的前中后三种遍历方式，要能进行相应的算法设计。 这一部分是数据结构考题历来的重点和难点，复

2、习时要特别关注。,6-4,树（tree）是树型结构的简称，是一类重要的非线性结构，其中以树和二叉树最为常用。,6 树,线性结构：一个挨着一个顺序排列 实际问题：族谱 丁一 丁二 丁五 丁三 丁六 丁四 丁七 丁八 丁九 丁十 丁十一 线性结构存储：一二三四五六七八九十十一,双亲？几代？孩子？（后代）,6-5,树型结构 丁一层次结构 丁二 丁三 丁四 丁五 丁六 丁七 丁八 丁九 丁十 丁十一,应用广泛： 人类社会：族谱、行政管理 计算机领域： 编译程序中源程序的语法结构 层次关系（DB中） 目录结构,6 树,6-6,树的应用举例目录结构,6 树,6-7,6.1 树的概念与基本术语,树的定义(T

3、ree) 树是有n(n0)个结点的有限集合。 如果 n=0，称为空树； 如果 n0,称为非空树,对于非空树,有且仅有一个特定的称为根(Root)的节点(无直接前驱) 如果 n1，则除根以外的其它结点划分为 m (m0)个互不相交的有限集 T1, T2 , Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。 每个结点都有唯一的直接前驱，但可能有多个后继 树的举例 其中：A是根；其余结点分成三个互不相交的子集， T1=B,E,F,K,L； T2=C,G； T3=D,H,I,J,M, T1,T2,T3都是根A的子树，且本身也是一棵树,1) 树的定义 定义：树是由n (n 0) 个

4、结点组成的有限集合。 其中当n 0时 n=0时，为空树。 特点：,有且仅有一个特定的称之为根(root)的结点； n 1时, 除根外的其余结点被划分为 m (m 0) 个互不相交的有限集合T1, T2, , Tm，每个集合本身又是一棵树，称之为根的子树(subTree)。,非空树中至少有一个结点根 树中各子树是互不相交的集合,6.1 树的概念与基本术语,6-9,某结点不能同时属于两个子集,两个子集的结点之间不能有关系,子树“互不相交”的含义,6-10,n=1,n1,6.1 树的概念与基本术语,A是根，其余结点可以划分为3个互不相交的集合： T1=B, E, F，K，L T2=C, G T3=D

5、, H, I, J，M,6-11,从逻辑结构看：1）树中只有根结点没有前趋；2）除根外，其余结点都有且仅一个前趋； 3）树的结点，可以有零个或多个后继；4）除根外的其他结点，都存在唯一条从根到该结点的路径； 5）树是一种分枝结构 （除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。,6.1 树的概念与基本术语,结点(node):表示树中的元素及若干指向其子树的分支 结点的度(degree)：一个结点拥有子树的个数 树的度(degree)：一棵树中所有结点的最大度数 叶子(leaf)结点：度为0的结点 分支(branch)结点：度不为0的结点 孩子/子女(chi

6、ld)结点：某结点子树的根 双亲(parent)结点:某结点是其子树根的双亲,6.1 树的概念与基本术语,兄弟(sibling)结点：具有同一双亲的所有结点 祖先(ancestor)结点：从根到该结点所经分支上的所有结点 子孙(descendant)结点：以某个结点为根的子树中的任一结点 结点的层数(level)：规定根结点层数为1，其余结点层数等于其双亲结点层数加1 树的高度/深度(depth)：树中叶子结点所在的最大层次 有序树：树中每个结点的各个子树从左到右是有次序的（不能互换） 无序树：子树的次序可以互换 路径：若树中存在一个结点序列k1,k2kj,使得ki是ki+1(1ij)的双亲，

7、则称该序列是k1到kj的路径 森林：是m(m 0)棵互不相交的树的集合。,6.1 树的概念与基本术语,结点A的度：3 结点B的度：2 结点M的度：0,叶子：K，L，F，G，M，I，J,结点A的孩子：B，C，D 结点B的孩子：E，F,结点H 的双亲：D 结点L的双亲：E,结点B，C，D为兄弟 结点K，L为兄弟,树的度：3,结点A的层次：1 结点M的层次：4,树的深度：4,结点 F,G为堂兄弟 结点A是结点F，G的祖先,6.1 树的概念与基本术语,6.1 树的抽象数据类型,ADT Tree 数据对象D：具有相同特性的数据元素的集合。 数据关系R： 若D为空集，则称为空树；否则： (1) 当n=1在

8、D中存在唯一的称为根的数据元素root； (2)当n1时，其余结点可分为m(m0)个互不相交的有限集合T1,T2,.,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。(递归定义) 基本操作P： 查找 插入 删除,6-15,6.1 树的抽象数据类型,查找： Root(T); Value(T,cur_e); Parent(T,cur_e); LeftChild(T,cur_e); RightSibling(T,cur_e); TreeEmpty(T); TreeDepth(T); TraverseTree(T,Visit();,6-16,6.1 树的抽象数据类型,插入 Ini

9、tTree(,6-17,6.1 树的抽象数据类型,删除 ClearTree(,6-18,线性结构和树型结构的比较,6-19,6.2 二叉树,定义：是n(n 0)个结点的有限集合，该集合或者为空，或者是由一个根结点加上两棵互不相交的左子树和右子树组成。,每个结点至多有二棵子树 二叉树的子树有左、右之分 其次序不能任意颠倒,6.2 二叉树,(a),(b),(c),(d),(e),6-22,(a)、(b)是不同的二叉树， (a)的左子树有四个结点，(b)的左子树有两个结点，,(a),(b),例如：,6.2 二叉树,6-23,6.2 二叉树,二叉树性质：在二叉树的第i层上至多有2i-1个结点(i1)

10、证明： i=1, 只有一个根节点，因此2i-1=20=1 设第i-1层上，以上性质成立，即第i-1层至多有2(i-1)-1结点。 由二叉树的定义可知，任何结点的度小于2，因此，第i层上的结点数最多为第i-1层上的两倍，即2*2i-2=2i-1 证毕,6-24,6.2 二叉树,二叉树性质：深度为k的二叉树至多有2k-1个结点 证明： 由性质，已知第i层上结点数最多为2i-1 k 2i-1 = 2k-1 i=1 证毕,6-25,6.2 二叉树,二叉树性质：如果二叉树终端结点数为n0，度为2的结点数为n2，则n0=n2+1 证明： 设n1是度为1的结点，则总结点数n= n0+n1+n2 设B为二叉树

11、的分支数，除根结点外，每个结点有且只有一个分支，因此n=B+1 每个分支皆由度为1或2的结点发出，B=n1+2n2 n=B+1=(n1+2n2)+1 = n0+n1+n2，因此 n0=n2+1 证毕,6-26,6.2 二叉树,满二叉树： 一个深度为k且有2k-1个结点的二叉树 每层上的结点数都是最大数 可以自上而下、自左至右连续编号,6-27,6.2 二叉树,完全二叉树： 当且仅当每一个结点都与深度相同的满二叉树中编号从1到n的结点一一对应的二叉树 叶子结点只在最大两层上出现 左子树深度与右子树深度相等或大,判断下列树是否为完全二叉树,6-28,6-29,6.2 二叉树,完全二叉树(性质)：具

12、有n个结点的完全二叉树,其深度为 log2n +1 证明：设k为深度，由二叉树性质，已知 2k-1-1 n 2k-1 即 2k-1 n 2k 即 k = log2n +1,6-30,完全二叉树(性质)： 在完全二叉树中，结点i的双亲为 i/2 结点i的左孩子LCHILD(i)=2i 结点i的右孩子RCHILD(i)=2i+1,6.2 二叉树,6.2 二叉树的存储结构,6-31,顺序存储结构 用一组地址连续的存储单元存储二叉树中的数据元素。,完全二叉树，只要从根起按层序存储即可。将完全二叉树上编号为i的结点元素存储在一维数组中下标为i-1的分量中。,一般二叉树，可对照完全二叉树的编号进行相应的存

13、储，但在没有结点的分量中需填充空白字符（例如填0）。,6-32,深度为4，有12个结点的完全二叉树的顺序存储,没有浪费,6.2 二叉树的存储结构,6-33,深度为4，有7个结点的一般二叉树的顺序存储,6.2 二叉树的存储结构,浪费4个,6.2 二叉树的存储结构,6-34,深度为4，只有4个右孩子的二叉树的顺序存储,浪费11个,6-35,6.2 二叉树的存储结构,顺序存储结构适用于满二叉树和完全二叉树的存储 对于非完全二叉树，采用链式存储结构更合适,6-36,6.2 二叉树,二叉链表 结点结构: 通常每个结点中设置三个域,即值域、左指针域和右指针域，其结点结构如下： 其中data表示值域，lch

14、ild和rchild分别表示左指针域和右指针域，用以分别存储指向左儿子结点和右儿子结点的指针。 TElemType可以是任何相应的数据类型如int、float或char等。,typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BITree;,6-37,6.2 二叉树,6-38,6.2 二叉树,三叉链表 通常每个结点中设置四个域,即值域、左指针域、右指针域和双亲指针域，其结点结构如下： 其中data表示值域，用于存储放入结点的数据，lchild和rchild分别表示左指针域和右指针域，

15、用以分别存储指向左儿子结点和右儿子结点的指针,parent指向双亲结点。,6-39,6.3 遍历二叉树,遍历二叉树 定义：二叉树的遍历(Traverse)是指按一定的规律访问二叉树的每个结点，且每个结点只被访问一次的过程。 对二叉树的遍历过程实际上是将非线性结构的二叉树中的结点排列成一个线性序列的过程。 本节仅讨论二叉链表的遍历过程。设访问根结点用D表示，遍历左、右子树用L、R表示 遍历方式 按层次访问； 按根、左子树、右子树三个部分进行访问；,6.3 遍历二叉树,6-40,2. 按根、左子树、右子树三个部分进行访问,设D表示根结点，L表示左子树，R表示右子树，则对这三个部分进行访问的组合共有

16、6种：,DLR DRL LDR LRD RDL RLD,若限定先左后右，则只有DLR，LDR，LRD三种，分别成为先序遍历，中序遍历和后序遍历。,6-41,若二叉树为空，则空操作；否则 访问根结点； 先序遍历左子树； 先序遍历右子树。,1）先序遍历算法描述：,6.3 遍历二叉树,1） 先序遍历（DLR）,6.3 遍历二叉树,D L R,先序遍历序列：A B D C,6-43,6.3 遍历二叉树,二叉树遍历的实现 template void PreOrder(BiTreeNode *t, void Visit(T item) /使用Visit(item)函数前序遍历二叉树t if(t != NU

17、LL) Visit(t-data); PreOrder(t-Left(), Visit); PreOrder(t-Right(), Visit); 为了通用性，把访问操作设计成前序遍历二叉树函数的一个函数虚参 Visit()。,输出结果：ABDEGCF (第一个输出节点必为根节点),6.3 遍历二叉树,6-44,6.3 遍历二叉树,6-45,若二叉树为空，则空操作；否则 中序遍历左子树； 访问根结点； 中序遍历右子树。,2）中序遍历算法描述：,6.3 遍历二叉树,6-46,L D R,中序遍历序列：B D A C,中序遍历:,6-47,6.3 遍历二叉树,template void InOrd

18、er(BiTreeNode *t, void Visit(T item) /使用Visit(item)函数中序遍历二叉树t if(t != NULL) InOrder(t-Left(), Visit); Visit(t-data); InOrder(t-Right(), Visit); ,输出结果：DBGEAFC （先于根节点A输出的节点为左子树的节点 后于根节点A输出的节点为右子树的节点）,6.3 遍历二叉树,6-48,6.3 遍历二叉树,6-49,若二叉树为空，则空操作；否则 后序遍历左子树； 后序遍历右子树； 访问根结点 。,3）后序遍历算法描述：,6.3 遍历二叉树,6-50,L R

19、D,后序遍历序列： D B C A,后序遍历:,6-51,6.3 遍历二叉树,template void PostOrder(BiTreeNode *t, void Visit(T item) /使用Visit(item)函数后序遍历二叉树t if(t != NULL) PostOrder(t-Left(), Visit); PostOrder(t-Right(), Visit); Visit(t-data); ,输出结果：DGEBFCA (最后一个输出节点必为根节点),6.3 遍历二叉树,6-52,6.3 遍历二叉树,6-53,6-54,6.3 遍历二叉树,遍历二叉树应用 利用后序求结点个数

20、或树的高度 利用前序实现二叉树复制 判断两棵树是否相等 Return 1+Size (t-lchild) + Size (t-rchild); temp-data=progmpde -data; temp -lchile =copy(orignode-lchild); temp -rchile =copy(orignode-rchild); If (a!=NULL & b!=NULL & a-data=b-data & equal(a-lchild=b- lchild) & equal(a-rchild=b- rchild),6-55,6.3 遍历二叉树,根据先、中序遍历求序列二叉树：如果已知

21、一棵二叉树的先序遍历和中序遍历序列，则可以惟一确定这棵二叉树 算法： 1.在先序遍历序列中，第一个节点为根节点D 2.在中序遍历序列中，根节点D左边的节点归为左子树，根节点D右边的节点归为右子树 3.对每个子树反复使用1,2两步，直到确定二叉树,6-56,6.3 遍历二叉树,示例：已知一棵二叉树的 先序遍历序列为：ABDEGCF， 中序遍历序列为：DBGEAFC， 请画出这棵二叉树 解：根据先序遍历序列，可知根节点为A；再根据中序遍历序列可知，左子树由DBGE组成，右子树由FC组成。 重复上述步骤，分别求出左子树和 右子树的细节。,6-57,6.3 遍历二叉树,根据后、中序遍历求序列二叉树：如

22、果已知一棵二叉树的后序遍历和中序遍历序列，则可以惟一确定这棵二叉树 算法： 1.在后序遍历序列中，最后一个节点为根节点D 2.在中序遍历序列中，根节点D左边的节点归为左子树，根节点D右边的节点归为右子树 3.对每个子树反复使用1,2两步，直到确定二叉树,6-58,6.3 遍历二叉树,示例：已知一棵二叉树的 后序遍历序列为：DGEBFCA ， 中序遍历序列为：DBGEAFC， 请画出这棵二叉树 解：根据后序遍历序列，可知根节点为A；再根据中序遍历序列可知，左子树由DBGE组成，右子树由FC组成。 重复上述步骤，分别求出左子树和 右子树的细节。,6-59,6.4 线索二叉树,二叉树以二叉链表存储结

23、构不足 所有叶子结点与无子结点的结点指针位置，存储结构都是空的； 同时只能找到结点的左右孩子的信息,而不能在结点的任一序列的前驱与后继信息,这种信息只有在遍历的动态过程中才能得到。 解决办法 利用二叉树中得空位置，建立遍历指针，达到在遍历中不再使用堆栈的目的。遍历指针被称为：线索。带有线索的二叉树被称为：线索二叉树,6-60,6.4 线索二叉树,在中序遍历过程中，遇到空指针时，需要决定遍历的后续结点的位置，所以： 空的右指针指向遍历后继 空的左指针指向遍历前趋,6-61,6.4 线索二叉树,线索二叉树中，只有两个空的指针分析中序的遍历过程 从左指针为空的结点开始遍历 到右指针为空的结点结束遍历

24、 建立二叉树的线索：在遍历过程中建立。 遍历时，记录当前结点的前趋和后继，在遇到空指针时，建立相应的连接。,6-62,6.5 树与森林,树的存储结构 1.双亲表示法 采用一组连续的存储空间 由于每个结点只有一个双亲，只需要一个指针,6-63,6.5 树与森林,2.孩子表示法多重链表 可以采用多重链表，即每个结点有多个指针 最大缺点是空链域太多 (d-1)n+1个,6-64,6.5 树与森林,3.孩子表示法单链表 将每个结点的孩子排列起来，用单链表表示 将每个结点排列成一个线性表,6-65,6.5 树与森林,4.孩子兄弟表示法 采用二叉链表 左边指针指向第一个孩子，右边指针指向兄弟,6-66,6

25、.5 树与森林,树与二叉树的对应关系 树与二叉树都可以采用二叉链表作存储结构 任意给定一棵树，可以找到一个唯一的二叉树(没有右子树) 树转换为二叉树的方法 树中所有相邻兄弟之间加一条连线。 对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线。 以树的根结点为轴心，将整棵树顺时针转动450，使之结构层次分明。,6-67,树转换成二叉树的过程举例,6.5 树与森林,6-68,6.5 树与森林,森林与二叉树的对应关系 如果把森林中的第二棵树的根结点看作是第一棵树的根结点的兄弟，则可找到一个唯一的二叉树与之对应。 森林转换成二叉树 如果F=T1,T2, , Tm是森林

26、，按如下规则可转换成一棵二叉树B=(root,LB,RB)。 （1）若F为空，则B为空； （2）若F非空，则森林中第一棵树T1的根结点为二叉树B的根结点，B的左子树LB由树T1根结点下的子树森林转换而成。右子树RB是由森林F中除树T1外余下部分转换而成。,6-69,6.5 树与森林,树的遍历 对树的遍历主要有两种：先根（次序）遍历、后根（次序）遍历 先根（次序）遍历：当树非空时 访问根结点 依次先根遍历根的各棵子树 输出结果：ABEFCDG 后根（次序）遍历：当树非空时 依次后根遍历根的各棵子树 访问根结点 输出结果：EFBCGDA,6-70,6.5 树与森林,与二叉树遍历的关系 当采用孩子兄

27、弟表示法表示树时： 树的先根遍历，与树对应的二叉树的先根遍历完全相同 树的后根遍历，与树对应的二叉树的中根遍历完全相同,6-71,6.6 赫夫曼树及其应用,赫夫曼树 赫夫曼树（Huffman）树也称最优二叉树，是一类带权路径长度最短的树，在判定、查找及数据压缩技术中有着广泛的应用。 基本术语 路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径 路径长度：路径上的分支数目 树的路径长度：从树根到每个结点的路径长度之和 带权路径长度：从结点到树根之间的路径长度与结点权的乘积 树的带权路径长度(WPL)：树中所有叶结点的带权路径长度之和 最优二叉树：假设二叉树有n个叶子，其每个叶子结

28、点权为wi，则带权路径长度WPL最小的二叉树称为最优二叉树。赫夫曼(Huffman)树就是一棵最优二叉树,6-72,6.6 赫夫曼树及其应用,例：下图所示的树路径长度为：2*1+3*2+1*3=11 下图所示的树的带权路径长度 WPL = 2*5+3*3+2*4=27,6-73,6.6 赫夫曼树及其应用,构造Huffman树 在Huffman树中，权值最大的结点离根最近 权值最小的结点离根最远 Huffman树算法 根据给定的n个权值(w1, w2, , wn)构成n棵二叉树的集合F=T1, T2, , Tn，其中每棵二叉树Ti中只有一个带树为Ti的根结点 在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置其根结点的权值为其左右子树权值之和 在F中删除这两棵树，同时将新得到的二叉树加入F中 重复2, 3，直到F只含一棵树为止,6-74,6.6 赫夫曼树及其应用,构造Huffman树示例,6.6 赫夫曼树及其应用,6-75,例子：w=5，29，7，8，14，23，3，11，构造哈夫曼树。,6-76,6.6 赫夫曼树及其应用,Huffman编码 目前，远距离通信的主要手段是电报，即将需传送的文字转换成二进制的字符组成的字符串。 编码时需要遵循以下原则： 解码结果唯一； 发送的二进制编码尽可能的短。,两类二进制编码,等