数据结构第五章树和二叉树-严军勇.ppt

第5章 树和二叉树,,● 本章要点 ● 树的定义及相关术语 ● 二叉树的定义、存储结构和基本运算的实现 ● 二叉树的遍历、二叉树与树和森林的相互转换 ● 哈夫曼树及应用 ● 本章难点 ● 二叉树的定义、存储结构和基本运算的实现 ● 哈夫曼树及应用,1．领会树和二叉树的类型定义，理解树和二叉树的结构差别 2．熟记二叉树的主要特性，并了解它们的证明方法 3．熟练掌握二叉树的各种遍历算法，并能灵活运用遍历算法实现二叉树的其它操作 4．理解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法 5．熟练掌握二叉树和树的各种存储结构及其建立的算法 6．学会编写实现树的各种操作的算法 7．了解最优树的特性，掌握建立最优树和赫夫曼编码的方法● 学习目标,● 5.1 树的定义和基本操作,● 5.1.1 树的定义 前面章节讨论的数据结构主要是线性结构 树型结构是一类重要的非线性结构 非线性结构 结构中存在一个数据元素有两个或两个以上的直接前驱（或直接后继）元素 树型结构广泛用于描述家族谱系以及其它社会组织结构在计算机领域中，如操作系统的文件目录结构、编译程序中的语法结构和数据库中的信息组织也都需要借用树来描述。

本章将讨论树和二叉树两种树型结构⒈树的定义 树是n(n≥0)个具有相同特性的数据元素的结点的有限集合当n=0时，称为空树（用Φ 表示） 有且仅有一个称为根(root)结点的数据元素，根结点没有前驱结点  当n1时，其余结点可分为 m(m0) 个互不相交的(非空)有限集 T1,T2,…,Tm, 其中每一个子集本身又是一棵符合本定义的树，称为根 root 的子树 树的定义是一个递归定义，它反映了树的固有特性，一棵树是由根和它的子树构成，而子树又由子树的根和更小的子树构成● 5.1.1 树的定义,● 5.1.1 树的定义,Φ,(a)空树,(b)只有根结点的树,(d)非树结构,(c) 一般的树,(a)空树 (b)只有根结点的树 (c)有11个结点的树 Ａ是根结点，其余结点分成三个不相交的子集 T1={B} T2={C,E,F,G,H,I,J,K} T21={E,I,J} T22={F} T23={G,K} T24={H} T3={D} (d)非树结构● 5.1.1 树的定义,(c) 一般的树,⒉ 树的特性 树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点 树中所有结点可以有零个或多个后继结点。

● 5.1.1 树的定义,● 5.1.1 树的常用术语,⑴ 结点的度 结点拥有的子树的个数 ⑵ 叶子结点（终端结点） 度为0的结点 ⑶ 分支结点（非终端结点） 度不为0的结点 ⑷ 树的度 树内各结点的度的最大值 ⑸ 双亲结点 结点的直接前驱结点c)一般的树,⑹ 孩子结点 一个结点的直接后继结点 ⑺ 兄弟结点 同一双亲结点的孩子结点之间互称兄弟结点 ⑻ 祖先结点 从根结点到该结点所经分支上的所有结点 ⑼ 子孙结点 以某结点为根的子树中的任一结点都称为该结点的子孙结点 ⑽ 结点的层次 根为第一层，根的直接后继为第二层，依次类推● 5.1.1 树的常用术语,(c)一般的树,⑾ 树的深度（高度） 结点的层次从根结点开始，根为第一层，根的孩子为第二层，树中结点的最大层次称为树的深度或高度 ⑿ 有序树、无序树 如果一棵树中的结点的各子树从左到右是有次序的，即若交换了某结点各子树的相对位置，则构成不同的树，称这棵树为有序树；反之，则称为无序树 ⒀ 森林 m棵互不相交的树的集合一棵树可以看成是由根结点和根结点下的森林构成的● 5.1.1 树的常用术语,(c)一般的树,⑴ 直观表示法 ⑵ 嵌套集合表示法,● 5.1.3 树的表示方法,⑴ 直观表示法,⑵ 嵌套集合表示法,⑶括号形式表示法 (A((B),C((E((I),(J))),(F),(G(K)),(H)),(D))) ⑷凹入表示法,,,,,,,,,,,,A,B,C,E,I,J,F,G,K,H,D,● 5.1.3 树的表示方法,就结构中数据元素之间存在的关系可将树和线性结构作如下对照：,将树和线性结构数据元素之间存在的关系作如下对照：,可见，由于线性结构是一个“序列”，元素之间存在的是“一对一”的关系，而树是一个层次结构，元素之间存在的是“一对多”的关系。

● 5.1.3 树的表示方法,二叉树是另一种基本的树型结构用二叉树来研究树的问题是表示和处理树型结构的基本方法 5.2.1 二叉树的定义 二叉树是有限个元素的集合，该集合或者为空，或者由一个称为根的元素及两个互不相交的，被分别称为左子树和右子树的二叉树组成当集合为空时，称该二叉树为空二叉树 约定： 二叉树的每个结点至多只有二棵子树，即二叉树中不存在度大于2的结点 二叉树是有序的，如果将左右子树颠倒，就成为另一棵二叉树● 5.2 二叉树,,● 5.2.1 二叉树的定义,二叉树具有以下5种基本形态Φ,⑴ 空二叉树,⑵ 仅有根的二叉树,⑶ 仅有左子树的二叉树,⑷ 仅有右子树的二叉树,⑸ 左、右子树均非空的二叉树,二叉树并非是树的特殊情形，在二叉树中，即使是一个孩子，也有左右之分具有2个结点的二叉树有2种形态，具有3个结点的二叉树有5种形态 2种特殊的二叉树 ⑴ 满二叉树 如果二叉树中所有的分支结点的度数都为2，且叶子结点都在同一层次上，则称这类二叉树为满二叉树 对满二叉树从上到下从左到右进行从1开始的编号（如图所示），则深度为k的满二叉树有且必有2k-1个结点这种二叉树的特点是每一层上的结点数都是最大的结点数。

● 5.2.1 二叉树的定义,满二叉树,非满二叉树,● 5.2.1 二叉树的定义,● 5.2.1 二叉树的定义,⑵ 完全二叉树 如果一棵包含 n 个结点的二叉树中每个结点都可以和满二叉树中编号为1至 n 的结点一一对应，则称这类二叉树为完全二叉树完全二叉树,非完全二叉树,,● 5.2.2 二叉树的性质,性质1：一棵非空二叉树的第i层上至多有 2i-1 个结点(i≥1) 性质2：深度为k的二叉树中至多含有 2k-1 个结点，(k≥1) 性质3：对任何一棵二叉树 T，如果叶子结点数为n0 ，度为2的结点数为 n2，则n0 =n2 +1 性质4：具有n个结点的完全二叉树的深度为 log2n +1性质5：如果具有 n 个结点的完全二叉树（其深度为 log2n +1）的结点按自上而下和从左到右的顺序对每个结点从1起开始顺序编号，则对任一编号为 j 的结点(1≤j≤n)，有 ⑴ 若j=1，则结点j是二叉树的根，无双亲，否则其双亲结点 parent(j) 是 j/2 ⑵ 若 2j≤n，则结点j 的左孩子结点是 2j，否则无左孩子，即编号为j且满足2jn的结点为叶子结点。

⑶ 若2j+1 ≤ n，则结点为j的右孩子结点是2j+1，否则无右孩子 ⑷ 若结点j序号为奇数且不等于1，则它的左兄弟为j-1 ⑸ 若结点j序号为偶数且不等于n，它的右兄弟为j+1● 5.2.2 二叉树的性质,● 5.2.2 二叉树的性质,例 已知一棵完全二叉树共有892个结点，求 ⑴ 树的高度 ⑵ 叶子结点数 ⑶ 单支结点数 ⑷ 最后一个非终端结点的序号 答 ⑴ 已知深度为k的二叉树最多有2k-1个结点(K≥1)， 29-1892 210-1，故树的高度为10 ⑵ 对于完全二叉树来说，度为1的结点只能是0或1 因为n=n0+n1+n2和n0=n2+1 得：设n1=0，892=n0+0+n2=2n2+1 得n2不为整数出错 设n1=1，892=n0+1+n2=2n2+2 得n2 =445→ n0=n2+1=446 叶子结点数为446● 5.2.2 二叉树的性质,答 ⑶ 由⑵得单支结点数为1 ⑷ 对于n个结点的完全二叉树，最后一个树叶结点，即序号为n的叶结点其双亲结点 即为最后一个非终端结点， 序号为892/2=446● 5.2.3 二叉树的存储结构,⒈ 顺序存储结构 用一组地址连续的存储单元存储二叉树中的数据元素。

二叉树的顺序存储结构的定义如下： #define MAX 100 /* 暂定二叉树中结点数的最大值为100*/ typedef struct { Elemtype a[MAX]; int count; /*二叉树中结点数*/ } BTree; /* 二叉树的顺序存储结构*/ typedef BTree bt;,按照数据结构的“顺序存储映象”的定义，在顺序存储结构中没有附加信息，因此对二叉树的顺序存储结构，也只是以一组地址连续的存储空间存放二叉树中的数据元素只是不能以“存储位置相邻”来表示 “后继”关系 在二叉树的这种表示方式下，各结点之间的逻辑关系是隐含表示的完全二叉树中，除最下面一层外，各层都充满结点除最底层外，每一层的结点个数恰好是上一层结点数的2倍故从一个结点的编号可推出其双亲、左右孩子和兄弟等结点的编号 完全二叉树中结点的层次关系可反映结点之间的逻辑关系● 5.2.3 二叉树的存储结构,为了能在存储结构中反映出结点之间的逻辑关系，必须将二叉树中结点依照一定规律安排在这组存储单元中 对于完全二叉树，只要从根起按层序存储即可 根据上一节所述完全二叉树的特性，将完全二叉树上编号为 i 的结点元素存储在一维数组中下标为 i-1 的分量中，如前例含12个结点的完全二叉树的顺序存储结构如下所示。

● 5.2.3 二叉树的存储结构,,根据上节所述二叉树的性质5，可推出顺序存储结构中“双亲”和“孩子”的关系： 假设 bt.a[i] 是完全二叉树上的一个结点，若 2i+1bt.count，则 bt.a[2i+1] 是它的左孩子，否则它的左子树为空树；若 2i+2bt.count，则 bt.a[2i+2]是它的右孩子，否则它的右子树为空树 在二叉树表示方法下，各结点间的逻辑关系是隐含的完全二叉树中，除最底层外，各层都充满结点；除最底层外，每一层结点数恰好是上一层结点数的2倍，故从一个结点的编号就可推得其双亲、左右孩子和兄弟结点的编号数组下标,● 5.2.3 二叉树的存储结构,● 5.2.3 二叉树的存储结构,对于结点i ⑴ 仅当i=1时，结点i为根结点 ⑵ 当i1时，结点i的双亲结点为 ⑶ 结点i的左孩子结点2i ⑷ 结点i的右孩子结点2i+1 ⑸ 当i为奇数且不为1时，结点i的左兄弟为i-1 ⑹ 当i为偶数且小于n时，结点i的右兄弟为i+1 完全二叉树中结点的层次关系反映了结点间的逻辑关系，对于完全二叉树，顺序存储既方便又节省存储空间● 5.2.3 二叉树的存储结构,对于一般的二叉树，采用顺序存储时，为了用结点在数组中的位置表示结点之间的逻辑关系，也必须按完全二叉树的形式来存储树中的结点。

在最坏情况，一个只有k个结点的右单支树却需要2k-1个结点的存储空间右单支二叉树,对应的完全二叉树,10,13,● 5.2.3 二叉树的存储结构,顺序存储对于完全二叉树来说非常方便 对于一般的二叉树，可对照完全二叉树的编号进行相应的存储，但在没有结点的分量中需填充空白字符显然，这种存储表示方法只适合于完全二叉树，对于一般的二叉树将造成存储空间的很大浪费因此二叉树的常用存储结构是链表● 5.2.3 二叉树的存储结构,,,,,,,,,,,,,1,2,3,4,5,6,1,7,8,9,10,11,12,数组下标,对应的完全二叉树,一般二叉树,序号,,,,,,,,1,,,,,,,12,⒉ 链式存储结构 二叉树的链式存储结构指的是用链表来存储二叉树，即用结点结构中的指针域来表达数据元素之间的关系 二叉树的二叉链表存储结点结构 typedef struct node { Elemtype data; struct node *LChild, *。