资源描述：
《树的定义和基本术语》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第六章树和二叉树树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常用。直观来说，树是以分支关系定义的层次结构。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。树在计算机领域中也得到广泛应用，如在编译程序中，可用树来表示源程序的语法结构。又如在数据库系统中，树形结构也是信息的重要组织形式之一。6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.6哈夫曼树及其应用6.1树的定义和基本术语（1）定义树（Tree）：是n（n≥0）个结点的有限集。定义一：（递归定义）：①在任意一棵非空树中，
2、有且仅有一个特定的称为根（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={
3、i=1,2,…,m;m>0}（2）表示形式该树有
4、13个结点。其中，A是树根，其余结点分成3个互不相交的子集：T1={B,E,F,K,L}，T2={C,G}，T3={D,H,I,J,M};T1、T2和T3都是A的子树，其本身也是一棵树。层次A1BCD2EFGHIJ3KLM4图6.1一般的树A该树又可表示为如下三种形式：(a)嵌套集合表示(c)凹入表示法(A(B(E(K,L),F),C(G),D(H(M),I,J)))(b)广义表表示ABCDEFGHIJKLMABCDEFGHIJKLM图6.2树的其他3种表示法（3）树的抽象数据类型定义ADTTree{数据对象D：D是具有相同特性的数据元素的集合。数据关
5、系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，有∈H；（3）对应于D－{root}的划分，H－{,…,}有唯一的一个划分H1,H2,…,Hm(m>0)，对任意j≠k(1≤j,k≤m)有H
6、j∩Hk＝Ф，且对任意i(1≤i≤m)，Hi是Di上的二元关系，(Di,{Hi})是一棵符合本定义的树，称为根root的子树。基本操作：InitTree(&T);操作结果：构造空树T。DestroyTree(&T);初始条件：树T存在。操作结果：销毁树T。CreateTree(&T,definition);初始条件：definition给出树T的定义。操作结果：按definition构造树T。ClearTree(&T);初始条件：树T存在。操作结果：将树T清为空树。TreeEmpty(T);初始条件：树T存在。操作结果：若T为空树，则返回TRUE，否则
7、返回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,
8、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
9、≤i≤p指结点的度。操作结果：删除T中p所指结点的第i棵子树。TraverseTree(T,v
