《树的定义和基本术语.ppt》由会员分享，可在线阅读，更多相关《树的定义和基本术语.ppt（21页珍藏版）》请在金锄头文库上搜索。
1、第六章第六章 树和二叉树树和二叉树 树树型型结构是一类重要的非线性数结构是一类重要的非线性数据结构。据结构。 其中以树和二叉树最为常用。其中以树和二叉树最为常用。 直观来说，树是以分支关系定义直观来说，树是以分支关系定义的层次结构。的层次结构。 树结构在客观世界中广泛存树结构在客观世界中广泛存在，如人类社会的族谱和各种社在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。会组织机构都可用树来形象表示。 树在计算机领域中也得到广树在计算机领域中也得到广泛应用，如在编译程序中，可用泛应用，如在编译程序中，可用树来表示源程序的语法结构。树来表示源程序的语法结构。 又如在数据库系统中，树形又如在
2、数据库系统中，树形结构也是信息的重要组织形式之结构也是信息的重要组织形式之一。一。6.1 6.1 树的定义和基本术语树的定义和基本术语6.2 6.2 二叉树二叉树6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 6.4 树和森林树和森林6.66.6 哈夫曼树及哈夫曼树及其应用其应用6.1 6.1 树的定义和基本术语树的定义和基本术语（1）定）定义 树（Tree）：是：是n（n0）个）个结点的有限集。点的有限集。 定定义一：（一：（递归定定义）：）： 在任意一棵非空在任意一棵非空树中，有且中，有且仅有一个特定的称有一个特定的称为根（根（root） 的的结点；点； 当当n1时，其
3、余，其余结点可分点可分为m（m0）个互不相交的有限集）个互不相交的有限集 T1, T2, , Tm，其中每一个集合本身又是一棵，其中每一个集合本身又是一棵树。并且。并且 T1, T2, , Tm，称，称为根的根的子子树（SubTree）。 定定义二：（形式定二：（形式定义）任何一棵任何一棵树是一个二元是一个二元组Tree = (root, F)。 其中：其中：root是数据元素，称做是数据元素，称做树的根的根结点；点；F是是m（m0）棵）棵树的森林，的森林， F（T1, T2, , Tm），其中），其中Ti = (ri, Fi)称做根称做根root的第的第i棵子棵子树；当；当m0 时，在，在树
4、根和其子根和其子树森林之森林之间存在下列关系：存在下列关系： RF = | i = 1, 2, ,m; m 0（2）表示形式）表示形式 该树有有13个个结点。其中，点。其中，A是是树根，其余根，其余结点分成点分成3个互不相交的子集：个互不相交的子集：T1=B, E, F, K, L，T2=C, G，T3=D, H, I, J, M; T1、T2和和T3都是都是A的子的子树，其本身也是一棵其本身也是一棵树。层次次A 1B C D 2E F G H I J 3K L M 4 图图6.1一般的树一般的树A该树又可表示为如下三种形式：该树又可表示为如下三种形式：(a) 嵌套集合表示嵌套集合表示 (c)
5、 凹入表示法凹入表示法 (A(B(E(K, L), F), C(G), D(H(M), I, J) (b) 广义表表示广义表表示 ABCDEFGHIJKLMABCDEFGHIJKLM图图6.2树的其他树的其他3种表示法种表示法 （3）树的抽象数据类型定义）树的抽象数据类型定义 ADT Tree数据数据对象象D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。数据关系数据关系R：若：若D为空集，空集，则称称为空空树； 若若D仅含一个数据元素，含一个数据元素，则R为空集，否空集，否则R=H,H是如下二元关系：是如下二元关系： （1）在）在D中存在唯一的称中存在唯一的称为根的数据元
6、素根的数据元素root，它在关系，它在关系H下无前下无前驱； （2）若）若Droot，则存在存在Droot的一个划分的一个划分D1,D2,Dm(m0), 对任意任意jk(1j,km)有有DjDk，且，且对任意的任意的i(1im)，唯，唯 一存在数据元素一存在数据元素xiDi，有，有H； （3）对应于于Droot的划分，的划分，H, , 有唯一有唯一 的一个划分的一个划分H1, H2, , Hm(m0)，对任意任意jk (1j,km)有有 HjHk，且，且对任意任意i(1im)，Hi是是Di上的二元关系，上的二元关系， (Di, Hi)是一棵符合本定是一棵符合本定义的的树，称，称为根根root的
7、子的子树。基本操作：基本操作： InitTree (&T); 操作结果：构造空树操作结果：构造空树T。 DestroyTree (&T);初始条件：树初始条件：树T存在。存在。操作结果：销毁树操作结果：销毁树T。 CreateTree (&T, definition);初始条件：初始条件：definition给出树给出树T的定义。的定义。操作结果：按操作结果：按definition构造树构造树T。 ClearTree (&T);初始条件：树初始条件：树T存在。存在。操作结果：将树操作结果：将树T清为空树。清为空树。 TreeEmpty(T);初始条件：树初始条件：树T存在。存在。操作结果：若操
8、作结果：若T为空树，则返回为空树，则返回TRUE，否则返回，否则返回FALSE。 TreeDepth(T);初始条件：树初始条件：树T存在。存在。操作结果：返回操作结果：返回T的深度。的深度。 Root(T);初始条件：树初始条件：树T存在。存在。操作结果：返回操作结果：返回T的根。的根。 Value(T, cur_e);初始条件：树初始条件：树T存在，存在，cur_e是是T中某个结点。中某个结点。操作结果：返回操作结果：返回cur_e的值。的值。 Assign(T, cur_e, value);初始条件：树初始条件：树T存在，存在，cur_e是是T中某个结点。中某个结点。操作结果：结点操作结
9、果：结点cur_e赋值为赋值为value。 Parent(T, cur_e);初始条件：树初始条件：树T存在，存在，cur_e是是T中某个结点。中某个结点。操作结果：若操作结果：若cur_e是是T的非根结点，则返回它的双亲，否则函数值为的非根结点，则返回它的双亲，否则函数值为“空空”。 LeftChild(T, cur_e);初始条件：树初始条件：树T存在，存在，cur_e是是T中某个结点。中某个结点。操作结果：若操作结果：若cur_e是是T的非叶子结点，则返回它的最左孩子，否则返回的非叶子结点，则返回它的最左孩子，否则返回“空空”。 RightSibling(T, cur_e);初始条件：树
10、初始条件：树T存在，存在，cur_e是是T中某个结点。中某个结点。操作结果：若操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则函数值为有右兄弟，则返回它的右兄弟，否则函数值为“空空”。 InsertChild(&T, &P, i, c);初始条件：树初始条件：树T存在，存在，p指向指向T中某个结点，中某个结点，1ip所指结点的度所指结点的度1，非空非空 树树c与与T不相交。不相交。操作结果：插入操作结果：插入c为为T中中p指结点的第指结点的第i棵子树。棵子树。 DeleteChild(&T, &P, i);初始条件：树初始条件：树T存在，存在，p指向指向T中某个结点，中某个结点，1ip指
11、结点的度。指结点的度。操作结果：删除操作结果：删除T中中p所指结点的第所指结点的第i棵子树。棵子树。 TraverseTree(T, visit();初始条件：树初始条件：树T存在，存在，visit是对结点操作的应用函数。是对结点操作的应用函数。操作结果：按某种次序对操作结果：按某种次序对T的每个结点调用函数的每个结点调用函数visit()一次且至多一次。一次且至多一次。 一旦一旦visit()失败，则操作失败。失败，则操作失败。ADT Tree6.1.2 基本术语基本术语 结点：结点：包含一个数据元素及若干指向其子树的分支。在树的包含一个数据元素及若干指向其子树的分支。在树的图形表示中为一个
12、圆圈。图形表示中为一个圆圈。 结点的度（的度（Degree）：结点拥有的子树数。：结点拥有的子树数。 叶子（或终端结点）（叶子（或终端结点）（Leaf）：度为：度为0的结点。即没有子树的结点。即没有子树的结点。的结点。分支结点（或非终端结点）分支结点（或非终端结点）：度不为：度不为0的结点。的结点。内部结点内部结点：除根结点之外的分支结点。：除根结点之外的分支结点。树的度的度：树内各结点的度的最大值。：树内各结点的度的最大值。孩子（孩子（Child）：结点的子树的根，称为该结点的孩子。：结点的子树的根，称为该结点的孩子。 双亲（双亲（Parent）：结点的子树的根，称为该结点的孩子，该：结点的
13、子树的根，称为该结点的孩子，该结点称为孩子的双亲。结点称为孩子的双亲。兄弟（兄弟（Sibling）：同一个双亲的孩子之间互称为兄弟。：同一个双亲的孩子之间互称为兄弟。子孙子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。：以某结点为根的子树中的任一结点都称为该结点的子孙。祖先祖先：从根到某结点所经分支上的所有结点，称为该结点的祖先。：从根到某结点所经分支上的所有结点，称为该结点的祖先。 森林（森林（Forest）：是：是m（m0）棵互不相交的树的集合。对树中）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。每个结点而言，其子树的集合即为森林。 层次（层次（Level）：从
14、根开始定义起，根为第一层，根的孩子为第二：从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第层。若某结点在第k层，则其子树的根就在第层，则其子树的根就在第k1层。层。堂兄弟堂兄弟：其双亲在同一层的结点互为堂兄弟。：其双亲在同一层的结点互为堂兄弟。深度（高度）（深度（高度）（Depth）：树中结点的最大层次。：树中结点的最大层次。 有序树有序树：若将树中结点的各子树看成从左至右是有次序的（即不能：若将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子
15、，最右边的称为最后一个孩子。树的根称为第一个孩子，最右边的称为最后一个孩子。结点结点: :包含一个数据元素及及若干指向其子树的分支结点的度结点的度: : 结点拥有的子树数称为结点的度ABCDEFGHIJMKL如图：A的度为3，C的度为1，E的度为0。树的度树的度: :叶子（或终端）结点叶子（或终端）结点: :分支（或非终端）结点分支（或非终端）结点: :树中所有结点的度的最大值。度为零的结点度大于零的结点除根结点外，分支结点也称为内部结点。ABCDEFGHIJMKL如图所示的树的度为3。结点的子树的根称结点的子树的根称为该结点的孩子为该结点的孩子（child)child)，相应的，相应的，该结
16、点的称为孩子该结点的称为孩子的双亲（的双亲（parentparent）。）。ABCDEFGHIJMKL 如图所示中，D为A的子树T3的根，则D是A的孩子，而A则是D的双亲。同一个双亲的孩子同一个双亲的孩子之间互称兄弟之间互称兄弟（siblingsibling）。）。ABCDEFGHIJMKL如图所示中，H、I、J互称为兄弟。将将这些关系进一步推广，可认为这些关系进一步推广，可认为D D是是M M的祖的祖父。结点的祖先是从根到该结点所经分支父。结点的祖先是从根到该结点所经分支的所有结点。的所有结点。如图所示中，M的祖先为A、D和J。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。如B的子
17、孙为E、F、K、L。结点的层次结点的层次: :树的深度：树的深度：ABCDEFGHIJMKL结点的层次从根开始定义起，根为第一层，根的孩子为第二层。假设根结点的层次为1,第l 层的结点的子树根结点的层次为l+1。树中叶子结点所在的最大层次。图示的树的深度为4。结点双亲在同一层的结点互为堂兄弟。例如，结点G与E、F、H、I、J互为堂兄弟。有序树：有序树：子树之间存在确定的次序关系。 树中结点的各子树从左到右是有次序的（即不能互换）。 在有序树中最左边的子树的根称为第一个孩子，最在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。右边的称为最后一个孩子。无序树：无序树：子树之间不存
18、在确定的次序关系。森林：森林：是 m（m0）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。由此，也可以森林和树相互递归的定义来描述树。ArootBEFKLCGDHIJMF就逻辑结构而言，任何一棵非空树是一个二元组Tree = （root，F）其中：其中：root 是数据元素，被称为根结点，F是m(m=0)棵树的森林，被称为子树森林，F=（T1，T2,Tm),其中Ti=(ri,Fi)称做根为root的第i棵子树；当m0时，在树根和其子树森林之间存在下列关系：RF=|i=1,2,m, m0这个定义将有助于得到森林和树与二叉树之间转换的递归定义。对比树型结构和线性结构对比树型结构和线性结构的结构特点的结构特点线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 ( (无前驱无前驱) ) 根结点根结点 ( (无前驱无前驱) )最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 一个后继一个后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 多个后继多个后继) )
