第六章树和二叉树第六章树和二叉树树的结构特点树的结构特点树型结构是以分支关系定义的层次结构，任意一棵非空树中：（1）有且仅有一个特定的称为根的结点；（2）当n>1时，其余结点为分为m个互不相交的有限集T1,T2,,,Tm,每一个子集本身也是一棵树。树型结构在编译程序中，可用来表示源程序的语法结构。在数据库系统中，树型结构也是信息的重要组织形式之一。是一类重要的非线性结非线性结构构,是以分支关系分支关系定义的层次结层次结构构。ABCDEFGHIJA(a)(b)(c)树的例子:树型结构树型结构现实世界：现实世界：如家谱、行政组织机构等。计算机领域：计算机领域：编译程序、数据库系统等。树树(Tree)(Tree)的定义的定义：n个结点组成的有限集合。满足如下两个条件（非空树）：ABCDEFGHIJ6.1树的定义和基本术语(2)当n>1时，根结点以外的其它结点可分m(m>0)个互不相交的有限集合T1,T2,…Tm。其中Ti称为子树子树。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。(1)有且仅有一个特定的根根(Root)(Root)结点结点；(A(B(E(K,L),F),C(G),D(H(M),I,J))嵌套括号表示法IJFKLGMCCDBEA嵌套集合凹入表树形表示ABCDEFGHIJKLM树的表示方法1.1.结点结点2.2.结点的度结点的度3.3.叶子叶子((终端结点终端结点))4.4.分枝结点分枝结点((非终端结点非终端结点))5.5.树的度树的度6.6.孩子结点孩子结点双亲结点双亲结点7.7.兄弟结点祖先结点兄弟结点祖先结点子孙结点子孙结点8.8.层次层次树的高度树的高度((深度深度))9.9.有序树无序树有序树无序树10.10.森林森林((树林树林))ABCDEFGHIJKLM基本术语基本术语InitTree(&T)InitTree(&T)构造空树T。Root(T)Root(T)求树T的根结点。Parent(T,x)Parent(T,x)求树T中值为x的结点的双亲。Child(T,x,i)Child(T,x,i)求树T中值为x的结点的第i个孩子。AddChild(T,y,i,x)AddChild(T,y,i,x)树T中将值为x的结点作为值y的结点的第i个孩子插入到树中。DelChild(T,x,i)DelChild(T,x,i)删除值为x的结点的第i个孩子。Traverse(T)Traverse(T)遍历或访问树T。树的基本运算树的基本运算二叉树的定义二叉树的定义每个结点至多只有两棵子树，并且，6.26.2二叉二叉树树二叉树的子树有左右之分，其次序不能任意颠倒。二叉树的5种形式(a)空二叉树(b)仅有根结点的二叉树(c)右子树为空的二叉树(e)左子树为空的二叉树(d)根和左右子树AABABACB二叉树的性质二叉树的性质性质1：第i层上至多有2i-1个结点(i≥1)。性质2：深度为k的二叉树至多有2k－1个结点性质3：对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0＝n2+1.性质4：具有n个结点的完全二叉树的深度为└log2n┘＋1。二叉树的性质（续）二叉树的性质（续）性质5：n个结点的完全二叉树的结点按层序编号,则对任一结点i(1≤i≤n)，有：(1)如果i＝1，则结点i无双亲，是二叉树的根；果i>1，则其双亲是结点└i/2┘。(2)如果2i>n，则结点i为叶子结点，无左孩子；否则(即：2i≤n)，其左孩子是结点2i;(3)如果2i＋1>n，则结点i无右孩子；否则(即：2i+1≤n)，其右孩子是结点2i＋1。(a)满二叉树2453671(b)完全二叉树245361(c)非完全二叉树245371(d)非完全二叉树23671特殊形态的二叉树二叉树的抽象定义二叉树的抽象定义ADTBinaryTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D=空集，R为空集，称为空二叉树；若D为非空，R为二元关系。基本操作P：……}ADTBinaryTreeInitBiTree(&T)InitBiTree(&T)构造空二叉树T。DestroyBiTree(&T)DestroyBiTree(&T)销毁二叉树T。Root(T)Root(T)求T的根结点。Parent(T,e)Parent(T,e)求T中值为e的结点的双亲。LChild(T,e)/RChild(T,e)LChild(T,e)/RChild(T,e)求T中值为e的结点的左/右孩子。LBrother(T,e)/RBrother(T,e)LBrother(T,e)/RBrother(T,e)求T中值为e的结点的左/右兄弟。二叉树的基本操作二叉树的基本操作二叉树的基本操作（续）二叉树的基本操作（续）Traverse(T)Traverse(T)遍历二叉树T。AddLChild(&T,x,y)/AddRChild(&T,x,y)AddLChild(&T,x,y)/AddRChild(&T,x,y)在T中，将值为y的结点作为值为x的结点的左/右孩子插入。DelLChild(&T,x)/DelRChild(&...
