树的定义和基本术语

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第六章 树和二叉树,树型结构是一类重要的非线性数据结构。,其中以树和二叉树最为常用。,直观来说，树是以分支关系定义的层次结构。,树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。,树在计算机领域中也得到广泛应用，如在编译程序中，可用树来表示源程序的语法结构。,又如在数据库系统中，树形结构也是信息的重要组织形式之一。,6.1 树的定义和基本术语,6.2 二叉树,6.3 遍历二叉树和线索二叉树,6.4 树和森林,哈夫曼树及其应用,6.1 树的定义和基本术语,（1）定义,树（Tree）,：是n（n,0）个结点的有限集。,定义一：（递归定义）：,在任意一棵非空树中，有且仅有一个特定的称为根（root）,的结点；,当n1时，其余结点可分为m（m0）个互不相交的有限集,T,1, T,2, , T,m,，其中每一个集合本身又是一棵树。并且,T,1, T,2, , T,m,，称为根的,子树（SubTree）,。,定义二：（形式定义）,任何一棵树是一个二元组Tree = (root, F)。,其中：root是数据元素，称做树的根结点；F是m（m,0）棵树的森林，,F（T,1, T,2, , T,m,），其中T,i,= (r,i, F,i,)称做根root的第i棵子树；当m,0,时，在树根和其子树森林之间存在下列关系：,RF = | i = 1, 2, ,m; m 0,（2）表示形式,该树有13个结点。其中，A是树根，其余结点分成3个互不相交的子集：,T,1,=B, E, F, K, L，T,2,=C, G，T,3,=D, H, I, J, M; T,1,、T,2,和T,3,都是A的子树，,其本身也是一棵树。,层次,A 1,B C D 2,E F G H I J 3,K L M 4,图6.1一般的树,A,该树又可表示为如下三种形式：,(a) 嵌套集合表示,(c) 凹入表示法,(A(B(E(K, L), F), C(G), D(H(M), I, J),(b) 广义表表示,A,B,C,D,E,F,G,H,I,J,K,L,M,A,B,C,D,E,F,G,H,I,J,K,L,M,图6.2树的其他3种表示法,（3）树的抽象数据类型定义,ADT Tree,数据对象D：D是具有相同特性的数据元素的集合。,数据关系R：若D为空集，则称为空树；,若D仅含一个数据元素，则R为空集，否则R=H,H是如下二元关系：,（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；,（2）若Droot,，则存在Droot的一个划分D,1,D,2,D,m,(m0),对任意j,k(1,j,k,m)有D,j,D,k,，且对任意的,i(1,i,m)，唯,一存在数据元素x,i,D,i,，有,H；,（3）对应于Droot的划分，H, , 有唯一,的一个划分H,1, H,2, , H,m,(m0)，对任意j,k (1,j,k,m)有,H,j,H,k,，且对任意,i(1,i,m)，H,i,是D,i,上的二元关系，,(D,i, H,i,)是一棵符合本定义的树，称为根root的子树。,基本操作：,InitTree (,操作结果：构造空树T。,DestroyTree (,初始条件：树T存在。,操作结果：销毁树T。,CreateTree (,初始条件：definition给出树T的定义。,操作结果：按definition构造树T。,ClearTree (,初始条件：树T存在。,操作结果：将树T清为空树。,TreeEmpty(T);,初始条件：树T存在。,操作结果：若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中某个结点。,操作结果：结点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);,初始条件：树T存在，cur_e是T中某个结点。,操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则函数值为“空”。,InsertChild(,初始条件：树T存在，p指向T中某个结点，1ip所指结点的度1，,非空,树,c与T不相交。,操作结果：插入c为T中p指结点的第i棵子树。,DeleteChild(,初始条件：树T存在，p指向T中某个结点，1ip指结点的度。,操作结果：删除T中p所指结点的第i棵子树。,TraverseTree(T, visit();,初始条件：树T存在，visit是对结点操作的应用函数。,操作结果：按某种次序对T的每个结点调用函数visit()一次且至多一次。,一旦visit()失败，则操作失败。,ADT Tree,6.1.2 基本术语,结点：,包含一个数据元素及若干指向其子树的分支。在树的,图形表示中为一个圆圈。,结点,的度（Degree）,：结点拥有的子树数。,叶子（或终端结点）（Leaf）,：度为0的结点。即没有子树,的结点。,分支结点（或非终端结点）,：度不为0的结点。,内部结点,：除根结点之外的分支结点。,树,的度,：树内各结点的度的最大值。,孩子（Child）,：结点的子树的根，称为该结点的孩子。,双亲（Parent）,：结点的子树的根，称为该结点的孩子，该,结点称为孩子的双亲。,兄弟（Sibling）,：同一个双亲的孩子之间互称为兄弟。,子孙,：以某结点为根的子树中的任一结点都称为该结点的子孙。,祖先,：从根到某结点所经分支上的所有结点，称为该结点的祖先。,森林（Forest）,：是m（m0）棵互不相交的树的集合。对树中,每个结点而言，其子树的集合即为森林。,层次（Level）,：从根开始定义起，根为第一层，根的孩子为第二,层。若某结点在第k层，则其子树的根就在第k1层。,堂兄弟,：其双亲在同一层的结点互为堂兄弟。,深度（高度）（Depth）,：树中结点的最大层次。,有序树,：若将树中结点的各子树看成从左至右是有次序的（即不能,互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子,树的根称为第一个孩子，最右边的称为最后一个孩子。,结点:,包含一个数据元素,及,若干指向其子树的分支,结点的度:,结点拥有的子树数称为结点的度,A,B,C,D,E,F,G,H,I,J,M,K,L,如图：,A的度为3，,C的度为1，,E的度为0。,树的度:,叶子（或终端）结点:,分支（或非终端）结点:,树中所有结点的度的最大值。,度为零的结点,度大于零的结点,除根结点外，分支结点也称为内部结点。,A,B,C,D,E,F,G,H,I,J,M,K,L,如图所示的树的度为3。,结点的子树的根称为该结点的孩子（child)，相应的，该结点的称为孩子的双亲（parent）。,A,B,C,D,E,F,G,H,I,J,M,K,L,如图所示中，D为A的子树T3的根，则D是A的孩子，而A则是D的双亲。,同一个双亲的孩子之间互称兄弟（sibling）。,A,B,C,D,E,F,G,H,I,J,M,K,L,如图所示中，H、I、J互称为兄弟。,将这些关系进一步推广，可认为D是M的祖父。结点的祖先是从根到该结点所经分支的所有结点。,如图所示中，M的祖先为A、D和J。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。如B的子孙为E、F、K、L。,结点的层次:,树的深度：,A,B,C,D,E,F,G,H,I,J,M,K,L,结点的层次从根开始定义起，根为第一层，根的孩子为第二层。假设根结点的层次为1,第,l,层的结点的子树根结点的层次为,l+1。,树中叶子结点所在的最大层次。图示的树的深度为4。,结点双亲在同一层的结点互为堂兄弟。例如，结点G与E、F、H、I、J互为堂兄弟。,有序树：,子树之间存在确定的次序关系。,树中结点的各子树从左到右是有次序的（即不能互换）。,在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。,无序树：,子树之间不存在确定的次序关系。,森林：,是 m（m,0）棵互,不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。由此，也可以森林和树相互递归的定义来描述树。,A,root,B,E,F,K,L,C,G,D,H,I,J,M,F,就逻辑结构而言，任何一棵非空树是一个二元组,Tree = （root，F）,其中：,root 是数据元素，被称为根结点，,F是m(m=0)棵树的森林，被称为子树森林，F=（T1，T2,Tm),其中T,i,=(r,i,F,i,)称做根为root的第i棵子树；当m0时，在树根和其子树森林之间存在下列关系：,RF=|i=1,2,m, m0,这个定义将有助于得到森林和树与二叉树之间转换的递归定义。,对比树型结构和线性结构的结构特点,线性结构,树型结构,第一个数据元素,(无前驱),根结点,(无前驱),最后一个数据元素,(无后继),多个叶子结点,(无后继),其它数据元素,(一个前驱、,一个后继),其它数据元素,(一个前驱、,多个后继),