资源描述：
《数据结构课件(树和二叉树)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构第六章树和二叉树8/28/2021ABCDEFGHIJKLM树6.1树的类型定义数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树；否则:（1）在D中存在唯一的称为根的数据元素root,（2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。基本操作：查找：Root(T);Value(T,cur_e);Parent(T,cur_e);LeftChild(T,cur_e);TreeEmpty(T);TreeDepth(T);TraverseTree(T
2、,Visit());6.1树的类型定义插入：InitTree(&T);CreateTree(&T,definition);Assign(T,cur_e,value);InsertChild(&T,&p,i,c);删除：ClearTree(&T);DestroyTree(&T);DeleteChild(&T,&p,i);DestroyTree(&T);6.1树的类型定义和线性结构的比较线性结构 树结构第一个数据元素(无前驱)； 根结点(无前驱)；最后一个数据元素(无后继)；多个叶子结点(无后继)；其它数据元素 树中其它结点(一个
3、前驱、一个后继)。(一个前驱、多个后继)。ABCDEFGHIJKLM树形表示A(B(E(K,L),F),C(G),D(H(M),I,J))嵌套括号表示法树的表示方法：IJFKLGMCCDBEA文氏图凹入表ABFEKLCDHIGMJ基本术语结点:数据元素+若干指向子树的分支。结点的度:分支的个数。树的度:树中所有结点的度的最大值。叶子结点:度为零的结点。分支结点:度大于零的结点；路径和路径长度。孩子结点、双亲结点、兄弟结点、堂兄弟、祖先结点、子孙结点。边：双亲节点x到子结点y的有序对(x，y)。结点的层次:假设根结点的层次为1，第i层的结点的子树根结点的层次为i+1。规定根的层数
4、为0。树的深度：树中叶子结点所在的最大层次。森林：是m（m≥0）棵互不相交的树的集合任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点，F被称为子树森林。6.2二叉树的类型定义二叉树的定义定义：二叉树是由n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。与树的关系：这也是一个递归定义。区别：二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。(a)空二叉树A(b)根和空的左右子树AB(c)根和左子树二叉树的5种基本形态A(d)根和右子
5、树BA(e)根和左右子树BC二叉树的主要基本操作：查找：Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());插入：InitBiTree(&T);Assig
6、n(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);删除：ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);性质1：在二叉树的第i层上至多有2i-1个结点(i>=1)。证明：采用归纳法证明此性质。当i=1时，只有一个根结点，2i-1=20=1,命题成立。现在假定第i－1层上命题成立，则第i－1层上至多有2i-2个结点。由于二叉树每个结点的度最大为2，故在第i层上最大结点数为第i－1层上最大结点数的二倍，即2×2i-2＝2i-1。命题得到证明。二叉
7、树的重要特性：性质2：深度为k的二叉树至多有2k－1个结点（k>=1).证明：深度为k的二叉树的最大的结点时为二叉树中每层上的最大结点数之和，由性质1得到每层上的最大结点数2i-1（第i层上的最大结点数）二叉树的重要特性：二叉树的重要特性：性质3：对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0＝n2＋1。证明：设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，所以有：N＝n0＋n1＋n2（——1）再看二叉树中的分支数，除根结点外
