资源描述：
《第六章树和二叉树ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第六章树和二叉树ZhejiangUniversityofTechnology26.1树的类型定义6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5树和森林的表示方法6.6树和森林的遍历6.7哈夫曼树与哈夫曼编码ZhejiangUniversityofTechnology36.1树的类型定义ZhejiangUniversityofTechnology4数据对象D：D是具有相同特性的数据元素的集合。若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n>1时
2、，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。数据关系R：ZhejiangUniversityofTechnology5ABCDEFGHIJMKLA(B(E,F(K,L)),C(G),D(H,I,J(M)))T1T3T2树根例如:ZhejiangUniversityofTechnology6基本操作：查找类插入类删除类ZhejiangUniversityofTechnology7Root(T)//求树的根结点查找类：Va
3、lue(T,cur_e)//求当前结点的元素值Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历ZhejiangUniversityofTechnology8InitTree(&T)//初始化空树插入类：CreateTree(&T,definit
4、ion)//按定义构造树Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树ZhejiangUniversityofTechnology9ClearTree(&T)//将树清空删除类：DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树ZhejiangUniversityofTechnology10ABCDEFGHIJMKLA(B(E,F(K,L)),C
5、(G),D(H,I,J(M)))T1T3T2树根例如:ZhejiangUniversityofTechnology11树形图表示的例子ABKELFDHMJICG嵌套集合表示法ABCDEKLFGHIJM凹入表示法（A(B(E(K,L),F),C(G),D(H(M),I,J)))广义表表示法ABCDEFGHIJMKLZhejiangUniversityofTechnology12基本术语ZhejiangUniversityofTechnology13结点:结点的度:树的度:叶子结点:分支结点:数据元素+若干指
6、向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJMZhejiangUniversityofTechnology14孩子、双亲兄弟、堂兄弟祖先、子孙结点的层次:树的深度：ABCDEFGHIJMKL根结点的层次为1，第l层结点的子树根结点的层次为l+1树中叶子结点所在的最大层次ZhejiangUniversityofTechnology15有序树：子树之间存在确定的次序关系。无序树：子树之间不存在确定的次序关系。ZhejiangUniversityofTechnology16任
7、何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点F被称为子树森林森林：是m（m≥0）棵互不相交的树的集合ArootBCDEFGHIJMKLFZhejiangUniversityofTechnology17对比树型结构和线性结构的结构特点ZhejiangUniversityofTechnology18~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个
8、前驱、一个后继)其它数据元素(一个前驱、多个后继)ZhejiangUniversityofTechnology196.2二叉树的类型定义ZhejiangUniversityofTechnology20二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。ABCDEFGHK根结点左子树右子树ZhejiangUniversityofTechnology21二叉树的五种基本形态：N空树只含根结点NNN
