资源描述：
《数据结构第六章树和二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第六章树和二叉树第一节树的类型定义A为“根”T1、T2和T3都是一棵树，称为A的子树。称根和子树根之间的连线为“分支”结点分支的个数定义为“结点的度”，如结点B的度为2，D的度为3。树中所有结点度的最大值定义为“树的度”。称度为零的结点为“叶子”或“终端结点”所有度不为零的结点被称作"分支结点"基本定义森林为m(m≥0)棵互不相交的树的集合。树的深度定义为树中叶子结点所在最大层次数。称根结点为子树根的"双亲"。称子树根为根结点的"孩子“根的所有子树根互为“兄弟”。有序树、无序树如果树中每棵子树从左向右的排列拥有一定的顺序，不得互
2、换，则称为有序树，否则称为无序树。树的抽象数据类型：ADTTree{数据对象：D是具有相同特性的数据元素的集合。数据关系： 若D为空集，则称为空树； 若D中仅含一个数据元素，则关系R为空集； 否则R={H}，(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)当n>1时，其余数据元素可分为m(m>0)个互不相交的(非空)有限集T1,T2,…,Tm,其中每一个子集本身又是一棵符合本定义的树，称为根root的子树，每一棵子树的根xi都是根root的后继，即H,i=1,2,…,m。基
3、本操作：{结构初始化}InitTree(&T);操作结果：构造空树T。CreateTree(&T,definition);初始条件：definition给出树T的定义。 操作结果：按definition构造树T。{销毁结构}DestroyTree(&T);初始条件：树T存在。 操作结果：销毁树T。{引用型操作}TreeEmpty(T);初始条件：树T存在。 操作结果：若T为空树，则返回TRUE，否则返回FALSE。TreeDepth(T);初始条件：树T存在。 操作结果：返回T的深度。Root(T);初始
4、条件：树T存在。 操作结果：返回T的根。Value(T,cur_e);初始条件：树T存在，cur_e是T中某个结点。 操作结果：返回cur_e的值。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);初始条件：
5、树T存在，cur_e是T中某个结点。 操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则返回"空"。TraverseTree(T,visit());初始条件：树T存在，visit是对结点操作的应用函数。 操作结果：按某种次序对T的每个结点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败。{加工型操作}Assign(T,cur_e,value);初始条件：树T存在，cur_e是T中某个结点。 操作结果：结点cur_e赋值为value。ClearTree(&T);初始条件：树T存在。
6、操作结果：将树T清为空树。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棵子树。}ADTTree树和线性结构对照：第二节二叉树类型定义：二叉树是另一种树形结构。它与树形结构的区别是：（1）每个结点最多有两棵子树；（2）子树有左右之分。二叉树也可以
7、用递归的形式定义。即：二叉树是n（n≥0）个结点的有限集合。当n=0时，称为空二叉树；当n>0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。二叉树的5种形态：ø(a)(b)(c)(d)(e)6.2.1二叉树的类型定义ADTBinaryTree{数据对象：D是具有相同特性的数据元素的集合。数据关系： 若D为空集，称BinaryTree为空二叉树； 否则关系R={H}：(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)
8、D中其余元素必可分为两个互不相交的子集L和R，每一个子集都是一棵符合本定义的二叉树，并分别为root的左子树和右子树。如果左子树L不空，则必存在一个根结点，它是root的"左后继"(∈H)，如果右子树R不空，则必存在一个根结点为root的"右后继"
