第6章树和二叉树part1课件.ppt

1、 第6章 树和二叉树 v树型结构是一类重要的树型结构是一类重要的非线性非线性数据结构。数据结构。v现实生活中有着广泛存在。现实生活中有着广泛存在。如：家谱，组如：家谱，组织机构关系等。织机构关系等。v在计算机领域中树在编译程序和数据库系在计算机领域中树在编译程序和数据库系统中也得到了广泛的应用。直观来看树是统中也得到了广泛的应用。直观来看树是以分支关系来定义的层次结构，其中以树以分支关系来定义的层次结构，其中以树和二叉树最为常用。和二叉树最为常用。第6章 树和二叉树v6.1 树的类型定义树的类型定义v6.2 二叉树的类型定义二叉树的类型定义v6.3 二叉树的存储结构二叉树的存储结构v6.4 二

2、叉树的遍历二叉树的遍历v6.5 线索二叉树线索二叉树v6.6 树和森林的表示方法树和森林的表示方法v6.7 树和森林的遍历树和森林的遍历v6.8 哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码树的类型定义v数据对象数据对象D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。v数据关系：数据关系：若若D为空集，则称为为空集，则称为空树空树；否则否则:(1)在在D中存在唯一的称为中存在唯一的称为根根的数据元素的数据元素root；(2)当当n1时，其余结点可分为时，其余结点可分为m(m0)个互不相交的有个互不相交的有限集限集T1,T2,Tm，其中每一棵子集本身又是一棵符合，其中每一棵子集

3、本身又是一棵符合本定义的树，称为根本定义的树，称为根root的的子树子树。举例：举例：树的类型定义v基本操作：基本操作：查找类查找类 插入类插入类 删除类删除类 Root(T)/求树的根结点求树的根结点 v查找类：查找类：Value(T,cur_e)/求当前结点的元素值求当前结点的元素值 Parent(T,cur_e)/求当前结点的双亲结点求当前结点的双亲结点LeftChild(T,cur_e)/求当前结点的最左孩子求当前结点的最左孩子 RightSibling(T,cur_e)/求当前结点的右兄弟求当前结点的右兄弟TreeEmpty(T)/判定树是否为空树判定树是否为空树 TreeDepth

4、(T)/求树的深度求树的深度TraverseTree(T,Visit()/遍历遍历InitTree(&T)/初始化置空树初始化置空树 v插入类：插入类：CreateTree(&T,definition)/按定义构造树按定义构造树Assign(T,cur_e,value)/给当前结点赋值给当前结点赋值InsertChild(&T,&p,i,c)/将以将以c为根的树插入为结点为根的树插入为结点p的第的第i棵子树棵子树 ClearTree(&T)/将树清空将树清空 v删除类：删除类：DestroyTree(&T)/销毁树的结构销毁树的结构DeleteChild(&T,&p,i)/删除结点删除结点p的

5、第的第i棵子树棵子树树的逻辑表示法树的逻辑表示法v(1)树型表示法。树型表示法。这是树的最基本的表示这是树的最基本的表示,使用一使用一棵倒置的树表示树结构棵倒置的树表示树结构,非常直观和形象。非常直观和形象。A C G J B E D F I H M K L 树形表示法树形表示法 树的逻辑表示法树的逻辑表示法v(2)文氏图表示法。文氏图表示法。使用集合以及集合的包含关使用集合以及集合的包含关系描述树结构。系描述树结构。H L D K I M C G J E B F 文氏图表示法文氏图表示法 A A C G J B E D F I H M K L 树形表示法树形表示法 树的逻辑表示法树的逻辑表示

6、法v(3)凹入表示法。凹入表示法。使用线段的伸缩描述树结使用线段的伸缩描述树结构。构。A C G J B E D F I H M K L 树形表示法树形表示法 树的逻辑表示法树的逻辑表示法v(4)括号表示法括号表示法(广义表表示法广义表表示法)。将树的根结点写在将树的根结点写在括号的左边括号的左边,除根结点之外的其余结点写在括号中除根结点之外的其余结点写在括号中并用逗号间隔来描述树结构。并用逗号间隔来描述树结构。括号表示法括号表示法 A(B(E,F),C(G(J),D(H,I(K,L,M)A C G J B E D F I H M K L 树形表示法树形表示法 树的分类v有向树：有向树：()有

7、确定的根；()树根和子树根之间为有向关系。v有序树：有序树：子树之间存在确定的次序关系。v无序树：无序树：子树之间不存在确定的次序关系。对比树型结构和线性结构的结构特点线性结构线性结构v第一个数据元素第一个数据元素(无前无前驱驱)v最后一个数据元素最后一个数据元素(无无后继后继)v其它数据元素其它数据元素(一个前一个前驱、一个后继驱、一个后继)树型结构树型结构v根结点根结点(无前驱无前驱)v多个叶子结点多个叶子结点(无后继无后继)v其它数据元素其它数据元素(一个前一个前驱、多个后继驱、多个后继)树的基本术语v结点：结点：包含一个数据元素及若干指向其子树的分包含一个数据元素及若干指向其子树的分支

8、。支。v结点的度结点的度(degree)：结点拥有的子树个数。结点拥有的子树个数。v树的度：树的度：树内各结点的度的最大值。树内各结点的度的最大值。v叶子叶子(leaf)：度为度为0的结点，也称为的结点，也称为终端结点终端结点。v分支结点：分支结点：度不为度不为0的结点，也称为的结点，也称为非终端结点非终端结点。除根结点外，分支结点也称为除根结点外，分支结点也称为内部结点内部结点。树的基本术语v(从根到结点的)路径：路径：由从根根到该结点所经分支和结点构成。v孩子、双亲、兄弟、堂兄弟：孩子、双亲、兄弟、堂兄弟：结点的子树的根称为该结点结点的子树的根称为该结点的的孩子孩子。相应地，该结点称。相应

9、地，该结点称为孩子的为孩子的双亲双亲。同一双亲的。同一双亲的孩子之间互称孩子之间互称兄弟兄弟。其双亲。其双亲在同一层的结点互为在同一层的结点互为堂兄弟堂兄弟。B、C、D是是A的孩子。的孩子。A 是是B、C、D的双亲。的双亲。结点结点H、I、J互为兄弟结点。互为兄弟结点。EFBAGKLMHIJCD树的基本术语v路径与路径长度：路径与路径长度：对于任意两个结点对于任意两个结点ki和和kj,若树中若树中存在一个结点序列存在一个结点序列ki,ki1,ki2,kin,kj,使得序列中除使得序列中除ki外的任一结点都是其在序列中的前一个结点的后外的任一结点都是其在序列中的前一个结点的后继继,则则称该结点序

10、列为由称该结点序列为由ki到到kj的一条路径的一条路径。用路径。用路径所通过的结点序列所通过的结点序列(ki,ki1,ki2,kj)表示这条路径。表示这条路径。路径的长度等于路径所通过的结点数目减路径的长度等于路径所通过的结点数目减1(即路径即路径上分支数目上分支数目)。可见。可见,路径就是从路径就是从ki出发出发“自上而下自上而下”到达到达kj所通过的树中结点序列。所通过的树中结点序列。显然显然,从树的根结点从树的根结点到树中其余结点均存在一条路径。到树中其余结点均存在一条路径。树的基本术语v结点的祖先：结点的祖先：从根结点到该结点的路径上的所有从根结点到该结点的路径上的所有结点。结点。v结

11、点的子孙：结点的子孙：以某结点为根的子树中的任一结点以某结点为根的子树中的任一结点都称为该结点的子孙。都称为该结点的子孙。EFBAGKLMHIJCD1234v结点的层次：结点的层次：假设根结点的假设根结点的层次为层次为1，第，第l 层的结点的子层的结点的子树根结点的层次为树根结点的层次为l+1v树的高度树的高度(深度深度)：树中结点树中结点的最大层次。的最大层次。树的基本术语v森林：森林：m（m0）棵互不相交的树的集合。将一棵）棵互不相交的树的集合。将一棵非空树的根结点删去，树就变成一个森林；反之，非空树的根结点删去，树就变成一个森林；反之，给给m棵独立的树增加一个根结点，并把这棵独立的树增加一个根结点，并把这m棵树作棵树作为该结点的子树，森林就变成一棵树。为该结点的子树，森林就变成一棵树。任何一棵非空树是一个二元组 Tree=（root，F）其中：root 被称为根结点 F 被称为子树森林rootABCDEFGHIJMKLF