树的定义和基本术语

树的定义和基本术语第1页，共21页，2023年，2月20日，星期六树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。树在计算机领域中也得到广泛应用，如在编译程序中，可用树来表示源程序的语法结构。又如在数据库系统中，树形结构也是信息的重要组织形式之一。第2页，共21页，2023年，2月20日，星期六6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.6哈夫曼树及其应用第3页，共21页，2023年，2月20日，星期六6.1树的定义和基本术语（1）定义树（Tree）：是n（n≥0）个结点的有限集。定义一：（递归定义）：①在任意一棵非空树中，有且仅有一个特定的称为根（root）的结点；②当n>1时，其余结点可分为m（m>0）个互不相交的有限集

T1,T2,…,Tm，其中每一个集合本身又是一棵树。并且

T1,T2,…,Tm，称为根的子树（SubTree）。定义二：（形式定义） 任何一棵树是一个二元组Tree=(root,F)。其中：root是数据元素，称做树的根结点；F是m（m≥0）棵树的森林，

F＝（T1,T2,…,Tm），其中Ti=(ri,Fi)称做根root的第i棵子树；当m≠0

时，在树根和其子树森林之间存在下列关系：

RF={<root,ri>|i=1,2,…,m;m>0}第4页，共21页，2023年，2月20日，星期六（2）表示形式该树有13个结点。其中，A是树根，其余结点分成3个互不相交的子集：T1={B,E,F,K,L}，T2={C,G}，T3={D,H,I,J,M};T1、T2和T3都是A的子树，其本身也是一棵树。层次A1BCD 2EFGHIJ3KLM4图6.1 一般的树A第5页，共21页，2023年，2月20日，星期六该树又可表示为如下三种形式：(a)嵌套集合表示(c)凹入表示法(A(B(E(K,L),F),C(G),D(H(M),I,J)))(b)广义表表示ABCDEFGHIJKLMABCDEFGHIJKLM图6.2 树的其他3种表示法第6页，共21页，2023年，2月20日，星期六（3）树的抽象数据类型定义ADTTree{

数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空树； 若D仅含一个数据元素，则R为空集，否则R={H},H是如下二元关系： （1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； （2）若D－{root}≠Ф，则存在D－{root}的一个划分D1,D2,…,Dm(m>0),

对任意j≠k(1≤j,k≤m)有Dj∩Dk＝Ф，且对任意的i(1≤i≤m)，唯一存在数据元素xi∈Di，有<root,xi>∈H； （3）对应于D－{root}的划分，H－{<root,xi>,…,<root,xm>}有唯一的一个划分H1,H2,…,Hm(m>0)，对任意j≠k(1≤j,k≤m)有

Hj∩Hk＝Ф，且对任意i(1≤i≤m)，Hi是Di上的二元关系，

(Di,{Hi})是一棵符合本定义的树，称为根root的子树。 基本操作：

InitTree(&T);

操作结果：构造空树T。

DestroyTree(&T);

初始条件：树T存在。 操作结果：销毁树T。第7页，共21页，2023年，2月20日，星期六

CreateTree(&T,definition);

初始条件：definition给出树T的定义。 操作结果：按definition构造树T。

ClearTree(&T);

初始条件：树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。第8页，共21页，2023年，2月20日，星期六

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,i,c);

初始条件：树T存在，p指向T中某个结点，1≤i≤p所指结点的度＋1，非空树c与T不相交。 操作结果：插入c为T中p指结点的第i棵子树。

DeleteChild(&T,&P,i);

初始条件：树T存在，p指向T中某个结点，1≤i≤p指结点的度。 操作结果：删除T中p所指结点的第i棵子树。

TraverseTree(T,visit());

初始条件：树T存在，visit是对结点操作的应用函数。 操作结果：按某种次序对T的每个结点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败。}ADTTree第9页，共21页，2023年，2月20日，星期六￡6.1.2基本术语

结点：包含一个数据元素及若干指向其子树的分支。在树的图形表示中为一个圆圈。结点的度（Degree）：结点拥有的子树数。叶子（或终端结点）（Leaf）：度为0的结点。即没有子树的结点。分支结点（或非终端结点）：度不为0的结点。内部结点：除根结点之外的分支结点。树的度：树内各结点的度的最大值。孩子（Child）：结点的子树的根，称为该结点的孩子。

双亲（Parent）：结点的子树的根，称为该结点的孩子，该结点称为孩子的双亲。兄弟（Sibling）：同一个双亲的孩子之间互称为兄弟。第10页，共21页，2023年，2月20日，星期六子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。祖先：从根到某结点所经分支上的所有结点，称为该结点的祖先。

森林（Forest）：是m（m≥0）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。层次（Level）：从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第k层，则其子树的根就在第k＋1层。堂兄弟：其双亲在同一层的结点互为堂兄弟。深度（高度）（Depth）：树中结点的最大层次。

有序树：若将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。第11页，共21页，2023年，2月20日，星期六结点:包含一个数据元素及若干指向其子树的分支结点的度:结点拥有的子树数称为结点的度ABCDEFGHIJMKL如图：A的度为3，C的度为1，E的度为0。第12页，共21页，2023年，2月20日，星期六树的度:叶子（或终端）结点:分支（或非终端）结点:树中所有结点的度的最大值。度为零的结点度大于零的结点除根结点外，分支结点也称为内部结点。ABCDEFGHIJMKL如图所示的树的度为3。第13页，共21页，2023年，2月20日，星期六结点的子树的根称为该结点的孩子（child)，相应的，该结点的称为孩子的双亲（parent）。ABCDEFGHIJMKL如图所示中，D为A的子树T3的根，则D是A的孩子，而A则是D的双亲。第14页，共21页，2023年，2月20日，星期六同一个双亲的孩子之间互称兄弟（sibling）。ABCDEFGHIJMKL如图所示中，H、I、J互称为兄弟。将这些关系进一步推广，可认为D是M的祖父。结点的祖先是从根到该结点所经分支的所有结点。如图所示中，M的祖先为A、D和J。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。如B的子孙为E、F、K、L。第15页，共21页，2023年，2月20日，星期六结点的层次:树的深度：ABCDEFGHIJMKL结点的层次从根开始定义起，根为第一层，根的孩子为第二层。假设根结点的层次为1,第l层的结点的子树根结点的层次为l+1。树中叶子结点所在的最大层次。图示的树的深度为4。结点双亲在同一层的结点互为堂兄弟。例如，结点G与E、F、H、I、J互为堂兄弟。第16页，共21页，2023年，2月20日，星期六有序树：子树之间存在确定的次序关系。树中结点的各子树从左到右是有次序的（即不能互换）。

在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。无序树：子树之间不存在确定的次序关系。第17页，共21页，2023年，2月20日，星期六森林：是m（m≥0）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。由此，也可以森林和