数据结构 第六 章树.ppt

《数据结构 第六 章树.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第六章树和二叉树6.1树的类型定义6.2二叉树6.3遍历和线索二叉树6.4树和森林6.5树与等价问题6.6哈夫曼树及其应用6.1树的类型定义数据对象D：D是具有相同特性的数据元素的集合。若D为空集，则称为空树；否则:(1)在D中存在唯一的称为根的数据元素root,(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。数据关系R：ABCDEFGHIJMKLA()T1T3T2树根例如:B(E,F(K,L)),C(G),D(H,I,J(M))树具有下面两个特点：（1）树的

2、根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。（2）树中所有结点可以有零个或多个后继结点。(１)有确定的根；(２)树根和子树根之间为有向关系。有向树：有序树：子树之间存在确定的次序关系。无序树：子树之间不存在确定的次序关系。基本术语结点(node)结点的度(degree)分支(branch)结点叶(leaf)结点孩子(child)结点双亲(parent)结点兄弟(sibling)结点祖先(ancestor)结点子孙(descendant)结点结点所处层次(level)树的高度(depth)树的度(degree)(从根到结点的)路径：结点的层

3、次:树的深度：由从根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1,第l层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点，F被称为子树森林森林：是m（m≥0）棵互不相交的树的集合ArootBEFKLCGDHIJMF对比树型结构和线性结构的结构特点~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它

4、数据元素(一个前驱、多个后继)6.2二叉树的类型定义二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。ABCDEFGHK根结点左子树右子树EF二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树二叉树的重要特性性质1：在二叉树的第i层上至多有2i-1个结点。(i≥1)用归纳法证明：归纳基：归纳假设：归纳证明：i=1层时，只有一个根结点，2i-1=20=1；假设对所有的j，1≤ji，命题成立;二叉树上每个结点至多有两棵子树，则第i层的结点数=2i-22=2i-1。性质2：深度为

5、k的二叉树上至多含2k-1个结点（k≥1）证明：基于上一条性质，深度为k的二叉树上的结点数至多为20+21++2k-1=2k-1性质3：对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1证明：设二叉树上结点总数n=n0+n1+n2又二叉树上分支总数b=n1+2n2而b=n-1=n0+n1+n2-1由此，n0=n2+1两类特殊的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。123456789101112131415abcd

6、efghij性质4：具有n个结点的完全二叉树的深度为log2n+1证明：设完全二叉树的深度为k则根据第二条性质得2k-1≤n<2k即k-1≤log2nn，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点；(3)若2i+1>n，则该结点无右孩子结点，否则，编号为2i+1的结点为其右孩子结

7、点。6.2.4二叉树的存储二、二叉树的链式存储表示一、二叉树的顺序存储表示一、二叉树的顺序存储表示二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。例如:ABDCEF012345678910111213ABCDEF1401326#defineMAXNODE30/*二叉树的最大结点数*/typedefELEMTYPESqBiTree[MAXNODE];/*0号单元存放根结点*/SqBiTreebt;即将bt定义为含有MAXNODE个elemtype类型元素的一维数组。完全二叉树和满二叉树适合顺序存储

8、二、二叉树的链式存储表示1.二叉链表2．三叉链表3．