数据结构PPT(第6章 树和二叉树)

《数据结构PPT(第6章 树和二叉树)》由会员分享，可在线阅读，更多相关《数据结构PPT(第6章 树和二叉树)（102页珍藏版）》请在金锄头文库上搜索。

1、第6章 树和二叉树,树型结构是一类重要的非线性结构。它的特点是结点之间有分支，并具有明显的层次关系的结构。树在计算机领域中有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。 本章重点讨论二叉树的存储表示及其各种运算，并研究一般树和森林与二叉树的转换关系，最后介绍树的应用实例。,本章学习导读,6.1 树的定义和基本术语,什么是树？树是由 n (n 0) 个结点的有限集合。如果 n = 0，称为空树；如果 n 0，则 有且仅有一个特定的称之为根(Root)的结点，它只有直接后继，但没有直接前驱； 当n 1，除

2、根以外的其它结点划分为 m (m 0) 个互不相交的有限集 T1, T2 , Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。,T = A，B，C，D，E，F，G，H，I，J，K，L，M A是根，其余结点可以划分为3个互不相交的集合： T1= B，E，F，K，L T2 = C，G T3 = D，H，I，J，M 这些集合中的每一集合都本身又是一棵树，它们是A的子树。 对于T1，B是根，其余结点可以划分为2个互不相交的集合： T11 = E，K，L T12 = F T11，T12是B的子树。,树的示例,1. 树中只有根结点没有前趋；2. 除根外，其余结点都有且仅一个前趋； 3

3、. 树的结点，可以有零个或多个后继；4. 除根外的其它结点，都存在唯一条从 根到该结点的路径； 5. 树是一种分支结构。,树的逻辑结构特点,树可表示具有分支结构关系的对象 例1. 家族族谱 设某家庭有13个成员A、B、C、D、E、F、G、H、I、J、K、L、M，他们之间的关系可如图所示的树表示。 例2. 单位行政机构的组织关系,树的应用,树是常用的数据组织形式 有些应用中数据元素之间并不存在分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。例3. 计算机的文件系统 不论是DOS文件系统还是window文件系统，所有的文件是用树的形式来组织的。,文件夹1,文件夹2,文件1,文件2

4、,文件夹11,文件夹11,文件11,文件12,C,树的应用,树的结点：包含一个数据元素的 内容及若干指向子树的分支。 孩子结点：结点的子树的根称为 该结点的孩子；如E是B的孩子。 双亲结点：B结点是A结点的孩子， 则A结点是B结点的双亲；如B是E的双亲。 兄弟结点：同一双亲的孩子结点；如H、I、J互为兄弟。 堂兄结点：同一层上结点；如G与E、F、H、I、J互为堂兄。 祖先结点：结点的祖先是从根到该结点所经分支上的所有结点； 如H的祖先为A、D。 子孙结点：以某结点为根的子树中的任一结点称为该结点的子孙；如A的子孙为B、C、D、E、F、G、H、I、J、K、L、M。,基本术语,结点的度：结点子树的

5、个数； 如D的度为3。 叶子结点：也叫终端结点，是 度为0的结点；如K、L、F、G 、M、I、J。 分支结点：度不为0的结点；如A、B、C、D 结点层次：根结点的层定义为1，根的孩子为第二层结点，依此类推。 树的高度：树中结点的最大层次；如图所示树的高度为4。 树的度： 树中各结点的度的最大值；如图所示树的度为3。 森林：m(m=0)棵互不相交的树的集合；,基本术语,线性结构 第一个数据元素 （无前驱）； 最后一个数据元素（无后继）； 其它数据元素（一个前驱、一个后继）。 树型结构 根结点（无前驱）； 多个叶子结点 （无后继）； 其它数据元素（一个前驱、多个后继）。,树型结构和线性结构的结构特

6、点对比,6.2.1 二叉树的定义 或为空树，或由根及至多两棵互不相交的左子树、右子树构成(即不存在度大于2的结点)，并且左、右子树本身也是二叉树。 说明： 1. 二叉树中每个结点最多有两棵子 树，二叉树每个结点度小于等于2； 2. 左、右子树不能颠倒有序树； 3. 二叉树是递归结构，在二叉树的定 义中又用到了二叉树的概念。,6.2 二叉树,(a) (b) (c) (d) (e) (a) 空树 (b) 只含根结点 (c) 右子树为空树 (d) 左右子树均不为空树 (e) 左子树为空树,L,L,R,R,二叉树的形态,性质1 在二叉树的第 i 层上至多有 2i - 1个结点。(i 1) 证明用归纳法

7、 证明：当i=1时，只有根结点，2 i-1=2 0=1。 假设对所有j， 1ji，命题成立，即第j层上至多有2 j-1 个结点。 由归纳假设第i-1 层上至多有 2i -2个结点。 由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即22i -2= 2 i-1。,6.2.2 二叉树的性质,性质2 深度为 k 的二叉树至多有 2 k-1个结点(k 1)。 证明：由性质1可见，深度为k的二叉树的最大结点数为,6.2.2 二叉树的性质,性质3 对任何一棵二叉树T，如果其叶结点数为 n0，度为2的结点数为 n2，则n0n21。 证明：设二叉树中度为1的结点数为

8、n1，二叉树中总结点数为： nn0n1n2 二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数， 则有：nB1。 由于这些分支都是由度为1和2的结点射出的，所以有： Bn1+2 n2 ; nB1n12n21 得到：n0n21,6.2.2 二叉树的性质,满二叉树：深度为k的二叉树，有2k-1个结点则称为满二叉树； 完全二叉树：如果深度为k、由n个结点的二叉树中个结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，则称为完全二叉树。 完全二叉树的特点是： 1. 所有的叶结点都出现在第k层或k1层。 2. 对任一结点，如果其右子树的最大层次为l ，则其左子树

9、的最大层次为 l 或 l 1。,两种特殊的二叉树,非完全二叉树,完全二叉树,满 二 叉 树,两种特殊的二叉树,性质 4 ：具有 n 个结点的完全二叉树的深度为 log2n +1。 证明：设完全二叉树的深度为 k，则根据性质2和完全二叉树的定义有 2k-1 - 1 n 2k- 1或 2k-1 n 2k 取对数 k-1 log2n k，又k是整数， 因此有 k = log2n 1,6.2.2 二叉树的性质,性质5： 如果对一棵有n个结点的完全二叉树的结点按层序编号(从第1层到第 log2n +1层，每层从左到右)，则对任一结点i(1 i n)，有： 1. 如果i1，则结点i无双亲，是二叉树的根；如

10、果i1，则其双亲是结点 i/2 。 2. 如果2in，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。 3. 如果2i1n，则结点i无右孩子；否则，其右孩子是结点2i1。,6.2.2 二叉树的性质,证明：此性质可采用数学归纳法证明。因为1与2、3是相对应的，所以只需证明2和3。 当 i=1时 ，根据结点编号方法可知，根的左、右孩子编号分别是2和3，结论成立。 假定i-1时结论成立，即结点i-1的左右孩子编号满足： LCHILD(i-1)=2(i-1)； RCHILD(i-1)=2(i-1)+1 通过完全二叉树可知，结点 i 或者与结点i-1同层且紧靠其右，或者结点i-1在某层最右端，而

11、结点i在其下一层最左端。但是，无论如何，结点i的左孩子的编号都是紧接着结点i-1的右孩子的编号，故： LCHILD(i)=RCHILD(i-1)+1=2i； RCHILD(i)=LCHILD(i)+1=2i+1 命题成立。,6.2.2 二叉树的性质,分析：根据完全二叉树的结构和编号规则，在i的左孩子前面的两个结点是结点i-1的左、右孩子，由归纳假设有：结点i-1的左孩子为2(i-1)，右孩子为2(i-1)+1。,.,.,i与i+1同层,.,.,i-1,2(i-1),2(i-1)+1,i,2i,2i+1,.,.,.,.,i与i+1不同层,6.2.2 二叉树的性质,i,2i,2i+1,i-1,2i

12、-2,2i-1,最后证明结论1。 当i=1时，显然根结点无双亲；当i1时，结点i可能是其双亲x的左孩子，也可能是右孩子，若是左孩子，由结论2知，x的左孩子应为2x，即2x=i，x=i/2；若是右孩子，由结论3知，x的右孩子应为2x+1，即2x+1=i，x=(i-1)/2。 故 i的双亲为i/2 证毕。,6.2.2 二叉树的性质,顺序存储结构 所谓顺序存储结构，就是用一组连续的存储单元存储二叉树的数据元素，结点在这个序列中的相互位置能反映出结点之间的逻辑关系。 二叉树中结点之间的关系就是双亲结点与左右孩子结点间的关系。因此，必须把二叉树的所有结点安排成为一个恰当的序列。具体定义如下： #defi

13、ne MAX-TREE-SIZE 100 TElemType SqBiTreeMAX-TREE-SIZE;,6.2.3 二叉树的存储结构,通常是按照二叉树结点从上至下、从左到右的顺序存储，但这样结点在存储位置上的前驱后继关系并不一定就是它们在逻辑上的邻接关系。依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。,二叉树的顺序存储结构,例如： bt3的双亲为3/2=1，即在bt1中； 其左孩子在bt2i=bt6中； 其右孩子在bt2i

14、+1=bt7中。,完全二叉树的顺序表示,一般二叉树也按完全二叉树形式存储，只有增添一些并不存在的空结点(用表示， 表示该处没有元素存在，仅仅为了好理解)，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。,例如对于B结点而言： bt2的双亲为1/2=1，即在bt1中(为A)； 其左孩子在bt2i=bt4中(为D)； 其右孩子在bt2i+1=bt5中(为 )。,一般二叉树的顺序表示,这种存储结构适合于完全二叉树，既不浪费存储空间，又能很快确定结点的存放位置、以及结点的双亲和左右孩子的存放位置，但对一般二叉树，可能造成存储空间的浪费。 例如，深度为k，且只有k个结 点的右单支树(每个非叶结点

15、只 有右孩子)，也需2k-1个单元， 即有(2k-1)- k个单元被浪费。,顺序存储的优缺点,所谓链式存储是指，用链表来表示一棵二叉树，即用链来指示着元素的逻辑关系。通常采用二叉链表来存储。 链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左右孩子所在的结点的存储地址。其定义如下： typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode,*BiTree;,链式存储结构,B ,T,lchild,data,rchild,结点结构,二叉链表,A,B,D,G,三叉链表图示

16、,三叉链表,6.3 遍历二叉树和线索二叉树,6.3.1 遍历二叉树 定义：所谓遍历二叉树，就是遵从某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。 这里所提的“访问”的含义很广，可以是查询、修改、输出某元素的值，以及对元素作某种运算等等。但要求这种访问不破坏它原来的数据结构。遍历一个线性结构很简单，只须从开始结点出发，顺序扫描每个结点即可。但对二叉树这样的非线性结构，每个结点可能有两个后继结点，因此需要寻找一种规律来系统访问树中的各结点。,由于二叉树的定义是递归的，它是由三个基本单元组成，即根结点、左子树和右子树。因此，遍历一棵非空二叉树的问题可以分解为三个子问题：访问根结点、遍历左子树、遍历右子树，只要依次遍历这三部分，就可以遍历整个二叉树。