资源描述：
《《叉树与森林》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构(A)(课程号:80L129Q)王志海办公室:第9教学楼北502室北京交通大学计算机与信息技术学院DataStructure&Algorithm(CourseNo.:80L129Q)Dr.ZhihaiWANG(Prof.)Email:zhhwang@bjtu.edu.cnTelephone:86-10-51683859Office:North502,Building9SchoolofComputer&InformationTechnology,BeijingJiaotongUnivers
2、ity,Beijing,100044,China第6章树型结构及其算法王志海办公室:第9教学楼北502室北京交通大学计算机与信息技术学院教学大纲：教学内容树的基本概念；二叉树的性质和存储结构；遍历二叉树；线索二叉树;树的存储结构和遍历；哈夫曼树及其应用。4©ZhihaiWANG,2015教学大纲：教学重点二叉树的结构特点，二叉树各种存储结构的特点及适用范围；按各种次序遍历二叉树的递归和非递归算法；（难点）二叉树的线索化，在中序线索树上找给定结点的前驱和后继的方法；树的各种存储结构及其特点；编写树
3、的各种运算的算法；建立最优二叉树和哈夫曼编码的方法。5©ZhihaiWANG,2015本章主要内容树的类型定义二叉树的类型定义二叉树的性质二叉树的存储结构二叉树的遍历线索二叉树树和森林树和森林的遍历哈夫曼树与哈夫曼编码6©ZhihaiWANG,2015本章主要内容树的类型定义二叉树的类型定义二叉树的性质二叉树的存储结构二叉树的遍历线索二叉树树和森林树和森林的遍历哈夫曼树与哈夫曼编码7©ZhihaiWANG,2015树的定义树(tree)是n(n≥0)个结点的有限集。当n=0时称为空树；在任意一棵
4、非空树中，有且仅有一个结点称为根(root)结点，其余的结点可分为m(m≥0)个互不相交的有限集T1,T2,…,Tm,其中每一个集合又称为一棵树，并且称为根的子树(subtree)。同理，每一棵子树又可以分为若干个互不相交的有限集。8©ZhihaiWANG,2015抽象数据类型树的定义ADTTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树；否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集
5、T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。基本操作：基本类，查找类，插入类，删除类等。}ADTTree9©ZhihaiWANG,2015与查找有关的基本操作Root(T)//求树的根结点Value(T,cur_e)//求当前结点的元素值Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的右兄弟TreeEmpty(T)//判定树是否为空
6、树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历10©ZhihaiWANG,2015与插入有关的基本操作InitTree(&T)//初始化置空树CreateTree(&T,definition)//按定义构造树Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树11©ZhihaiWANG,2015与删除有关的基本操作ClearTree(&T)//将树清空De
7、stroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树12©ZhihaiWANG,2015例如:ABCDEFGHIJMKLA(B(E,F(K,L)),C(G),D(H,I,J(M)))T1T3T2树根13©ZhihaiWANG,2015几种类型的树有向树：有确定的根；树根和子树根之间为有向关系。有序树：子树之间存在确定的次序关系。无序树：子树之间不存在确定的次序关系。DHIJM14©ZhihaiWANG,2015树型结构vs.线性结构线性结构
8、树型结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)15©ZhihaiWANG,2015树的基本术语(6-1)树的结点：包含一个数据元素及若干个指向其子树的分支；结点的度：一个结点拥有的子树数目(分支数)；DHIJM树的度：一棵树上所有结点度的最大值；叶子结点(终端结点):度为零的结点；分支结点(非终端结点):度大于零的结点；16©ZhihaiWANG,2015树的基本术语(6-2)(
