树的ADT.

1树数据结构与算法2引言前述我们所研究的数据结构线性表是线性结构。本章将研究的树型结构是一种动态的，非线性的，可描述结构层次特性的数据结构。这种结构是按分枝关系把信息联系起来的数据组织形式。在日常生活中这种结构是不少见的，如：3家谱图(谱系图)ChangChang父祖父祖母Chang母外祖父外祖母4行政机构图中央人民政府湖南省湖北省……上海市长沙………全省各地市………各市、县、区5UNIX文件目录6XML文件结构7树型的网络拓扑结构8编译程序中使用语法树9树型结构小节•客观世界中广泛存在树结构•树结构也在计算科学领域中被广泛的（创造和）应用以上各例的数据(信息)组织形式，均称为树型结构。当然它与植物树有所不同，(它的根在上，枝在下)10树的定义和基本术语11树的定义•一棵树(tree)T是由一个或一个以上结点组成的有限集–其中有一个特定的结点R称为T的根结点。–集合(T－{R})中的其余结点可被划分为n≥0个互不相交的子集T1，T2，…,Tn，其中每个子集本身又是一棵树，并且其相应的根结点R1，R2，…,Rn是R的子结点•子集Ti(1≤i≤n)称为树T的子树(subtree)。–子树可如下排序：Ti排在Tj之前，当且仅当ij–为方便起见,子树从左到右排列,其中T1被称为R的最左子树,R1被称为R的最左子结点12ABCDEFGHIJMKLA(B(E,F(K,L)),C(G),D(H,I,J(M)))T1T3T2树根例如:13结点:结点的度:树的度:叶子结点:分支结点:数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM14(从根到结点的)路径：孩子结点、双亲结点兄弟结点、堂兄弟祖先结点、子孙结点结点的层次:树的深度：由从根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1，第l层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次15任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点F被称为子树森林森林：是m（m≥0）棵互不相交的树的集合ArootBCDEFGHIJMKLF16对比树型结构和线性结构的结构特点17线性结构树型结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)18树的ADT19数据对象D：D是具有相同特性的数据元素的集合。若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。数据关系R：20基本操作：查找类插入类删除类24树结点的ADT//GeneraltreenodeADTtemplateclassElemclassGTNode{public:GTNode(constElem&);//Constructor~GTNode();//DestructorElemvalue();//ReturnvalueboolisLeaf();//TRUEifisaleafGTNode*parent();//ReturnparentGTNode*leftmost_child();//FirstchildGTNode*right_sibling();//RightsiblingvoidsetValue(Elem&);//Setvaluevoidinsert_first(GTNodeElem*n);voidinsert_next(GTNodeElem*n);voidremove_first();//Removefirstchildvoidremove_next();//Removesibling};25树的ADT//GeneraltreenodeADTtemplateclassElemclassGenTree{private：voidprinthelp(GTNode*);//printhelperfunctionpublic:GenTree();//constructor~GenTree();//Destructorvoidclear();//SendnodestofreestoreGTNode*root();//Returntheroot//CombinetwosubtreeVoidnewroot(Elem&,GTNodeElem*,GTNodeElem*);Voidprint();//Printatree};26二叉树的定义和性质27二叉树BinaryTrees二叉树(binarytree)是结点(node)的有限集合，这个集合或者为空(empty)，或者由一个根结点(root)以及两棵二叉树组成,这两棵二叉树分别称作这个根的左子树(leftsubtree)和右子树(rightsubtree),这两棵二叉树分别与根结点相连且彼此不相交.29二叉树的五种基本形态N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树30二叉树的特性(性质1)特性一：在二叉树中，第i层上的结点数最多为2i1(i≥1);证明(归纳法)：当i=1时，只有一个结点，2i1=20=1(归纳基础)归纳假设：假定对所有的j,1≤ji命题成立，即第j层上结点总数最多为2j1个结点。那么，可以证明j=i时命题成立。31归纳步骤：由归纳假设可知，i1层上的结点总数最多为2i2。由于二叉树每个结点的度最大为2，所以第i层上的结点最大数为第i1层上结点最大数的2倍，即22i2，从而得证，i层上最大结点数为2i1.32特性二：深度为k的二叉树至多有2k1个结点.(k≥1)证明：深度为k的二叉树结点最大数为每一层结点最大数之和。由特性一得：122)(111kkiikii层上结点最大数第二叉树的特性(性质2)33特性三：对任一棵二叉树，若叶结点数为n0,度为2的结点数为n2，则有n0=n2+1成立证明：设度为1的结点数为n1，则二叉树的结点总数为：n=n0+n1+n2…………(1)二叉树的特性(性质3)34设二叉树的分支总数为B，除根结点外，每一个结点都有一个分支进入，则B=n1又因为度为1的结点发出一个分支，度为2的结点发出2个分支所以：B=n1+2n2从而得n=n1+2n2+1…………(2)由(1),(2)式得n0=n2+1成立.35FullandCompleteBinaryTrees满二叉树(fullbinarytree)的每一个结点或者是一个分支结点，并恰有两个非空子结点；或者是叶结点.完全二叉树(completebinarytree)从根结点起每一层的结点从左到右连续填充,除了最下面一层以外其余各层都是满的,并且最下面一层的结点都集中在该层的最左边.36特性四：具有n个结点的完全二叉树，其深度为：k=log2n+1证：根据性质2和完全二叉树的定义，设完全二叉树的深度为k，则2k11n≤2k1深度为k1的完全二叉树的最大结点数深度为k的完全二叉树的最大结点数即2k1≤n2k于是有k1≤log2nkk为整数k=log2n+1得证完全二叉树的特性(性质4)37特性五：如果对一棵有n个结点的完全二叉树(其深度为log2n+1)的结点按层次自上而下，从左至右编号，则对任一编号为i的结点(1≤i≤n)有2)若2i≤n则结点i的左孩子是编号为2i的结点;否则结点i无左孩子（结点i为叶子结点）。1)若i=1,则该结点为根结点，无双亲，若i1,则结点i的双亲是编号为i/2的结点。记为parent(i)=i/2完全二叉树的特性(性质5)3)若2i+1≤n则结点i的右孩子是结点2i+1;否则结点i无右孩子。3848925106371结点3×2＋110,所以结点3的左孩子序号为3*2=6，右孩子结点序号为3×2＋1＝7。结点10的双亲结点序号为10/2＝5例子39满二叉树定理Theorem:非空满二叉树的叶结点数等于其分支结点数加1.40满二叉树定理证明1Theorem:非空满二叉树的叶结点数等于其分支结点数加1.证明(byMathematicalInduction数学归纳法):初始情况:没有分支结点的非空二叉树有一个叶结点。有一个分支结点的满二叉树有两个叶结点，即当n=0及n=1时定理成立.归纳假设:设任意一棵有n-1个分支结点的满二叉树T有n个叶结点.41满二叉树定理证明1(续)归纳步骤:假设树T有n个分支结点，取一个左右子结点均为叶结点的分支结点I。去掉I的两个子结点，则I成为叶结点，把新树记为T'，T'有n-1个分支结点.根据归纳假设，T‘有n个叶结点的满二叉树.现在把两个叶结点归还给I,我们又得到树T,它有n个分支结点。但原先的叶结点I现在变成了分支结点，所以叶结点只增加了一个,于是，树T有n个分支结点和n+1个叶结点.因此，根据归纳原理，定理对任意的n≥0成立。42满二叉树定理证明2•Theorem:非空满二叉树的叶结点数等于其分支结点数加1.•证明2:设分支结点数为n,根据满二叉树的定义,每一个分支结点都有两个非空子结点,所以共有2n个非空子结点,加上根结点,该二叉树总共有2n+1个结点,除去n个分支结点,剩下n+1个叶结点43满二叉树定理的推论Theorem:一棵非空二叉树空子树的数目等于其结点数目加1.Proof:Replaceallnullpointerswithapointertoanemptyleafnode.Thisisafullbinarytree.44满二叉树定理的推论的证明1证明1：设二叉树T，将其所有空子树换成叶结点，把新的二叉树记为T‘。所有原来树T的结点现在是树T’的分支结点。由于树T中的分支结点要么有两个非空子结点,要么有一个非空子结点和一个空子树,而这个空子树在T‘中已换成了非空子结点;并且树T中的每个叶结点都有两个空子树,在树T’中都换成了两个非空子结点,所以树T‘中的每个分支结点都有两个非空子结点,所以树T’是满二叉树。根据满二叉树定理，新添加的叶结点数目等于树T的结点数目加1，而每个新添加的叶结点对应树T的一棵空子树，因此树T中空子树的数目等于树T中结点数目加1。45满二叉树定理的推论的证明2Theorem:一棵非空二叉树空子树的数目等于其结点数目加1.证明2：假设树T有n个结点,其中有一个是根结点，其余n-1个都是非空子结点。如果把空子树也算作子结点的话，那么每个结点都有两个子结点,n个结点就有2n个子结点。既然非空子结点数目为n-1，所以必有有n+1个子结点为空。46二叉树的ADT47数据对象D：D是具有相同特性的数据元素的集合。若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n1时，其余结点可分为不相交的有限集Tl、Tr，其中每一个子集本身又是一棵符合本定义的二叉树，称为根root的子树。数据关系R：48二叉树结点的ADT//BinarytreenodeabstractclasstemplateclassElemclassBinNode{public:virtualElem&val()=0;//Returnthenode'selementvirtualvoidsetVal(constElem&)=0;//Setthenode'selementvirtualBinNode*left()const=0;//Returnthenode'sleftchildvirtualvoidsetLeft(BinNode*)=0;//Setthenode'sleftchildvirtualBinNode*right()const=0;//Returnthenode'srightchildvirtualvoidsetRight(BinNode*)=0;//Setthenode'sright