數(shù)據(jù)結構31-樹、二叉樹定義及術語

數(shù)據(jù)結構

第二十二課樹、二叉樹定義及術語第二十二課樹、二叉樹定義及術語本課主題：樹、二叉樹定義及術語教學目的：掌握樹、二叉樹的基本概念和術語，二叉樹的性質(zhì)教學重點：二叉樹的定義、二叉樹的性質(zhì)教學難點：二叉樹的性質(zhì)授課內(nèi)容：一、樹的定義和基本術語1、樹的定義(1)樹是n(n≥0)個結點的有限集。在任意一棵非空樹中：(1)有且僅有一個特定的稱為根的結點；(2)當n>1時,其余結點可分為m(m>0)個互不相交的有限集T1,T2,...Tm,其中每一個集合本身又是一棵樹,并且稱為根的子樹.樹的例子：家族，機構等1、樹的定義(2)樹是包含n個結點的有限集合(n≥0)Tree=(D,R)其中，D是具有相同性質(zhì)的數(shù)據(jù)元素的集合，R是如下描述的二元關系：在D中存在唯一一個稱為根的元素r0,它在關系R下無前驅；除結點r0外,K中每個結點對于關系R來說，都有且只有一個前驅。結點r0外的任何結點r∈R，都存在一個結點序列r0,r1,…,rs,<ri-1,ri>∈R(1<=i<=s),這樣一個結點序列稱為根到結點r的路徑。2﹑樹的抽象數(shù)據(jù)類型的定義ADTTree數(shù)據(jù)對象D：數(shù)據(jù)關系R：基本操作P：InitTree(&T);DestroyTree(&T);CreateTree(&T,definition);ClearTree(&T);……3﹑樹的表示方法樹形表示法：自然界倒長的樹（Knuth開初用正長的樹表示）文氏表示法：用集合表示凹入表示法：類似書目嵌套括號表示法：廣義表表示法表示的多樣性說明了樹的應用的廣泛性。4、樹的基本概念(1)樹的結點包含一個數(shù)據(jù)元素及若干指向其子樹的分支。結點擁有的子樹數(shù)稱為結點的度。度為0的結點稱為葉子或終端結點。度不為0的結點稱為非終端結點或分支結點。4、樹的基本概念(2)4、樹的基本概念(3)樹的度是樹內(nèi)各結點的度的最大值。結點的子樹的根稱為該結點的孩子，相應地，該結點稱為孩子的雙親。同一個雙親的孩子之間互稱兄弟。結點的祖先是從根到該結點所經(jīng)分支上的所有結點。以某結點為根的子樹中的任一結點都稱為該結點的子孫。4、樹的基本概念(4)結點的層次從根開始定義起，根為第一層，根的孩子為第二層。其雙親在同一層的結點互為堂兄弟。樹中結點的最大層次稱為樹的深度，或高度。如果將樹中結點的各子樹看成從左至右是有次序的，則稱該樹為有序樹，否則稱為無序樹。森林是m(m>=0)棵互不相交的樹的集合。4、樹的基本概念(5)二、二叉樹的定義1﹑二叉樹是另一種樹型結構它的特點是每個結點至多只有二棵子樹（即二叉樹中不存在度大于2的結點),并且,二叉樹的子樹有左右之分,其次序不能任意顛倒。左子樹和右子樹也是如上定義的二叉樹。二叉樹不是樹的特例。2﹑二叉樹的5種形態(tài)空（二叉樹）；只有根結點；根結點和左子樹；根結點和右子樹；根結點和左右子樹。3﹑一棵深度為k且有2(k)-1個結點的二叉樹稱為滿二叉樹，如果有深度為k的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應時，稱之為完全二叉樹。4﹑抽象數(shù)據(jù)類型二叉樹的定義

(1)ADTBinaryTree{數(shù)據(jù)對象D:D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關系R:基本操作P:InitBiTree(&T);DestroyBiTree(&T);CreateBiTree(&T,definition);ClearBiTree(&T);4﹑抽象數(shù)據(jù)類型二叉樹的定義

(2)BiTreeEmpty(T);BiTreeDepth(T);Root(T);Value(T,e);Assign(T,&e,value);Parent(T,e);LeftChild(T,e);RightChild(T,e);4﹑抽象數(shù)據(jù)類型二叉樹的定義(3)LeftSibling(T,e);RightSibling(T,e);InsertChild(T,p,LR,c);DeleteChild(T,p,LR);PreOrderTraverse(T,visit());InOrderTraverse(T,visit());Post