数据结构课件 第6章 树和二叉树

第六章树和二叉树6.1树的类型定义树（Tree）是n（n≥0）个结点的有限集。在任意一棵非空树当中：（1）有且仅有一个特定的结点称为根结点（Root）（2）当n〉1时，其余结点可分为m（m〉0）个互不相交的有限集T1T2…Tm，其中每一个集合本身又是一棵树，并且称为根的子树（subtree）树结构中的基本术语：结点：包含一个数据元素及若干指向其子树的分支。结点的度：结点拥有的子树的个数。终端结点（叶子）：度为0的结点非终端结点（分支）：度不为0的结点树的度：树内各结点的度的最大值。孩子：结点子树的根结点。双亲：结点本身成为其孩子的双亲（父）结点。兄弟：同一个双亲结点的孩子之间互称为兄弟。祖先：是从根到该节点所经分支上的所有结点。子孙：以某结点为根的子树中的任意结点。结点的层次：从根开始定义为第1层，根的孩子为第二层……堂兄弟：其双亲在同一层的结点。树的深度（高度）：树中结点的最大层数。有序树：树中结点的子树看成从左到右有序的（不能互换），则称概树为有序树，否则称为无序树。森林（forest）：是m（m≥0）棵互不相交的树的集合。树的抽象数据类型的定义如下：ADTTree{数据对象：D是具有相同特性的数据元素的集合。数据关系：若D为空集，则称为空树；若D中仅含一个数据元素，则关系R为空集；否则R={H}，(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)当n1时，其余数据元素可分为m(m0)个互不相交的(非空)有限集T1,T2,…,Tm,其中每一个子集本身又是一棵符合本定义的树，称为根root的子树，每一棵子树的根xi都是根root的后继，即root,xiH,i=1,2,…,m。基本操作：{结构初始化}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);初始条件：树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);初始条件：树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存在。操作结果：将树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可从另一个角度来定义树。定义森林为m(m≥0)棵互不相交的树的集合。则可定义树是一个二元组Tree=(root,F)其中，root是数据元素，称作树的根，F是子树森林，记作F=(T1,T2,…,Tm),其中Ti=(ri,Fi)为根root的第i棵(符合本定义的)子树，当m≠0是，在树根和其子树森林之间存在下列关系：RF={root,ri|i=1,2,…,m,m0}树和线性结构作如下对照：线性结构树结构存在唯一的没有前驱的首元素存在唯一的没有前驱的根结点存在唯一的没有后继的尾元素存在多个没有后继的叶子其余元素均存在唯一的前驱元素和唯一的后继元素其余结点均存在唯一的前驱(双亲)结点和多个后继(孩子)结点6.2二叉树类型6.2.1二叉树的类型定义二叉树的抽象数据类型定义如下:ADTBinaryTree{数据对象：D是具有相同特性的数据元素的集合。数据关系：若D为空集，称BinaryTree为空二叉树；否则关系R={H}：(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)D中其余元素必可分为两个互不相交的子集L和R，每一个子集都是一棵符合本定义的二叉树，并分别为root的左子树和右子树。如果左子树L不空，则必存在一个根结点XL，它是root的“左后继”(root,XL∈H)如果右子树R不空，则必存在一个根结点XR，为root的右后继(root,XR∈H)。基本操作：{结构初始化}InitBiTree(&T);操作结果：构造空二叉树T。CreateBiTree(&T,definition);初始条件：definition给出二叉树T的定义。操作结果：按definition构造二叉树T。{销毁结构}DestroyBiTree(&T);初始条件：二叉树T存在。操作结果：销毁二叉树T。{引用型操作}BiTreeEmpty(T);初始条件：二叉树T存在。操作结果：若T为空二叉树，则返回TRUE，否则返回FALSE。BiTreeDepth(T);初始条件：二叉树T存在。操作结果：返回T的深度。Root(T);初始条件：二叉树T存在。操作结果：返回T的根。Value(T,e);初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的值。Parent(T,e);初始条件：二叉树T存在，e是T中某个结点。操作结果：若e是T的非根结点，则返回它的双亲，否则返回“空”。LeftChild(T,e);初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的左孩子。若e无左孩子，则返回空。RightChild(T,e);初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的右孩子。若e无右孩子，则返回“空”。LeftSibling(T,e);初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的左兄弟。若e是其双亲的左孩子或无左兄弟，则返回“空”。RightSibling(T,e);初始条件：二叉树T存在，e是T的结点。操作结果：返回e的右兄弟。若e是其双亲的右孩子或无右兄弟，则返回空。PreOrderTraverse(T,visit());初始条件：二叉树T存在，visit是对结点操作的应用函数。操作结果：先序遍历T，对每个结点调用函数visit一次且仅一次。一旦visit()失败，则操作失败。InOrderTraverse(T,vsit());初始条件：二叉树T存在，visit是对结点操作的应用函数。操作结果：中序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。PostOrderTraverse(T,visit());初始条件：二叉树T存在，visit是对结点操作的应用函数。操作结果：后序遍历T，对每个结点调用函数visit一次且仅一次。一旦visit()失败，则操作失败。LevelOrderTraverse(T,visit());初始条件：二叉树T存在，visit是对结点操作的应用函数。操作结果：层序遍历T，对每个结点调用函数visit一次且仅一次。一旦visit()失败，则操作失败。{加工型操作}ClearBiTree(&T);初始条件：二叉树T存在。操作结果：将二叉树T清为空树。Assign(&T,&e,value);初始条件：二叉树T存在，e是T中某个结点。操作结果：结点e赋值为value。InsertChild(&T,p,LR,c);初始条件：二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c与T不相交且右子树为空。操作结果：根据LR为0或1，插入c为T中p所指结点的左或右子树。p所指结点原有左或右子树成为c的右子树。DeleteChild(&T,p,LR);初始条件：二叉树T存在，p指向T中某个结点，LR为0或1。操作结果：根据LR为0或1，删除T中p所指结点的左或右子树。}ADTBinaryTree6.2.2二叉树的几个特性一、在二叉树的第i层上至多有2i-1个结点(i≥1)。利用归纳法容易证得此结论。证明：归纳基：i=1时，只有一个根结点。显然2i-1=20=1是对的。归纳假设：设对所有的j(1≤ji)，命题成立，即第j层上至多有2j-1个结点。归纳证明：由归纳假设“第i-1层上至多有2i-2个结点”，又二叉树的每个结点的度至多为2，则第i层上的最大结点数为第i-1层上最大结点数的2倍，即2×2i-2=2i-1。证毕。二、深度为k的二叉树中至多含有2k-1个结点，(k≥1)。证明：由特性一可推出，深度为k的二叉树上最大结点数为三、对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1证明：由于二叉树中只有三种结点，假设n1为二叉树T中度为1的结点数，则二叉树中结点总数为n=n0+n1+n2①再看二叉树中的分支数目。除了根结点外，其余结点都有一个分支进入，假设B为分支数，则n=B+1。从另一角度看，这些分支是由度为1或2的结点射出的，所以又有B=n1+2n2即n=n1+2n2+1②综合以上①和②两个等式便可得到n0=n2+1有两种特殊形态的二叉树满二叉树:若二叉树中所有的分支结点的度数都为2，且叶子结点都在同一层次上，则称这类二叉树为满二叉树。对满二叉树从上到下从左到右进行从1开始的编号（如图所示），则任意一棵二叉树都可以和同深度的满二叉树相对比。完全二叉树:假如一棵包含n个结点的二叉树中每个结点都可以和满二叉树中编号为1至n的结点一、一对应，则称这类二叉树为完全二叉树。显然一棵深度为h的完全二叉树中，前h-1层中的结点都是满的，且第h层的结点都集中在左边。显然，满二叉树本身也是完全二叉树。四、具有n个结点的完全二叉树的深度为log2n+1。假设该完全二叉树的深度为k，则根据特性二和完全二叉树的定义2k-1-1n≤2k-1或2k-1≤n2k对后者取对数便得k-1≤log2nk因为k是整数，所以k=[log2n]+1。五、如果对一棵有n个结点的完全二叉树（其深度为log2n+1）的结点按层序（从第1层到第log2n+1层，每层从左到右）从1起开始编号，则对任一编号为i的结点(1≤i≤n)，有(1)如果i=1，则编号为i的结点是二叉树的根，无双亲；如果i1，则其双亲结点parent(i)的编号是i/2。(2)如果2in，则编号为i的结点无左孩子（编号为i的结点为叶子结点）；否则其左孩子结点lChild(i)的编号是2i。(3)如果2i+1n，则编号为i的结点无右孩子；否则其右孩子结点rChild(i)的编号是结点2i+1。6.3二叉树的存储表示用一组地址连续的存储单元存储二叉树中的数据元素。二叉树的顺序存储结构的定义如下：constMAXSIZE=100;//定二叉树中结点数的max为100typedefstruct{ElemTypedata[MAXSIZE];//存储空间基址(初始化时分配空间)intnodeNum;//二叉树中结点数}SqBiTree;//二叉树的顺序存储结构6.3.1顺序存储结构对于完全二叉树，只要从根起按层