数据结构第六章 树和二叉树.ppt

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

1、数据结构第6章树和二叉树引言你见过家族谱系图吗？试以图形表示从你的祖父起的家族成员关系。你一定可以画出如下类似的图形或者用如右下的图形表明你的祖先。主要内容6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.5赫夫曼树及其应用6.1树的定义和基本术语树的定义树是一类重要的非线性数据结构，是以分支关系定义的层次结构。树的定义如下：树(Tree)是n(n≥0)个结点的有限集T，如果n=0，称为空树；否则：有且仅有一个称为树的根(root)的结点。其余结点可分为m(m>0)个互不相交的有限集T1,T2,

2、……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)。ABCDEFGHIJKLM6.1树的定义和基本术语树的表示形式-一颗倒立的树T1T2T3只含有根结点的树含有子树T1、T2和T3的树对于非空树，其特点：树中至少有一个结点——根树中各子树是互不相交的集合6.1树的定义和基本术语树的其他表示形式凹入表示嵌套集合广义表6.1树的定义和基本术语树的基本术语结点(node)—表示树中的元素，包括数据项及若干指向其子树的分支结点的度—结点拥有的子树个数叶子—度为0的结点树的度—一棵树中最大的结点度数(子树数）孩子—结

3、点的子树的根称为该结点的孩子（结点）双亲—孩子结点的上一层结点叫该结点的(父结点)兄弟——同一双亲的孩子互称兄弟（结点）结点的层次——从根结点算起，根为第一层，它的孩子为第二层……ABCDEFGHIJKLM树的示意图6.1树的定义和基本术语树的基本术语树的深度（树高）—树中结点的最大层次数堂兄弟—其双亲在同一层的结点互称为堂兄弟。结点的祖先—从根结点到该结点所经分支上的所有结点结点的子孙—以某结点为根的子树中的任一结点都称之为该结点的子孙有序树和无序树：树中各结点的子树从左到右有次序（不能互换），称该树为有序树，否则为无序树。

4、（有序树：第一个孩子、第二个孩子…）森林—m(m0)棵互不相交的树构成的集合ABCDEFGHIJKLM树的示意图6.1树的定义和基本术语树的基本术语就逻辑结构而言，可以森林和树相互递归的定义来描述树：任何一棵非空树是一个二元组:Tree=（root，F）其中：root被称为根结点,F被称为子树森林森林:是m（m≥0）棵互不相交的树的集合ArootBCDEFGHIJMKLF6.1树的定义和基本术语树的基本术语(从根结点到结点的)路径：结点的层次:树的深度：由从根结点到该结点所经分支和结点构成。ABCDEFGHIJMKL假设根结

5、点的层次为1，第l层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次注意：树的叶子结点不一定都在树的最大层次上6.1树的定义和基本术语树的基本术语~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构（1:1）树型结构（1:n）第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、一个或多个后继)对比线性结构和树型结构的结构特点(a1,a2,a3,…an-2,an-1,an)ABCDEFGHIJMKL6.1树的定

6、义和基本术语树的抽象数据定义数据对象D：D是具有相同特性的数据元素的集合。若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。数据关系R：ADTTree{基本操作：……}ADTTree6.1树的定义和基本术语树的基本操作查找类插入类删除类6.1树的定义和基本术语树的基本操作Root(T)//求树的根结点查找类：Value(T,cur_e)//求当前结点的元

7、素值Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历6.1树的定义和基本术语树的基本操作InitTree(&T)//初始化置空树插入类：CreateTree(&T,definition)//按定义构造树Assign(T,cur_e,value)//给当前结点赋值In

8、sertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树6.1树的定义和基本术语树的基本操作ClearTree(&T)//将树清空删除类：DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树