1、數據結構講義 樹的定義和性質l樹是一類重要的非線性數據結構，是以分支關系定義的層次結構。l定義定義：樹(tree)是n(n0)個結點的有限集T，其中：l有且僅有一個特定的結點，稱為樹的根(root)l當n1時，其余結點可分為m(m0)個互不相交的有限集T1,T2,Tm，其中每一個集合本身又是一棵樹，稱為根的子樹(subtree)特點：l樹中至少有一個結點根l樹中各子樹是互不相交的集合A只有根結點的樹ABCDEFGHIJKLM有子樹的樹根子樹l基本術語結點(node)表示樹中的元素，包括數據項及若干指向其子樹的分支結點的度(degree)結點擁有的子樹數葉子(leaf)度為0的結點孩子(chil

2、d)結點子樹的根稱為該結點的孩子雙親(parents)孩子結點的上層結點叫該結點的兄弟(sibling)同一雙親的孩子樹的度一棵樹中最大的結點度數結點的層次(level)從根結點算起，根為第一層，它的孩子為第二層深度(depth)樹中結點的最大層次數森林(forest)m(m0)棵互不相交的樹的集合ABCDEFGHIJKLM結點A的度：3結點B的度：2結點M的度：0葉子：K，L，F，G，M，I，J結點A的孩子：B，C，D結點B的孩子：E，F結點I的雙親：D結點L的雙親：E結點B，C，D為兄弟結點K，L為兄弟樹的度：3結點A的層次：1結點M的層次：4樹的深度：4結點F，G為堂兄弟結點A是結點F，

3、G的祖先bacghdefijl樹形表示教師教師學生學生其他人員其他人員99級級 2000級級 2001級級 2002級級華中科技大學華中科技大學計算機系計算機系電信系電信系自控系自控系葉子葉子根根子樹子樹abdeijfcghijdfghabcea ( b ( d, e ( i, j ), c ( g, h ) ) )l定義定義：二叉樹是n(n0)個結點的有限集，它或為空樹(n=0)，或由一個根結點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構成。特點l每個結點至多有二棵子樹(即不存在度大于2的結點)l二叉樹的子樹有左、右之分，且其次序不能任意顛倒基本形態A只有根結點的二叉樹空二叉樹AB右子樹

4、為空AB左子樹為空ABC左、右子樹均非空l二叉樹性質性質1：) 1(21iii個結點層上至多有在二叉樹的第證明：用歸納法證明之 i=1時，只有一個根結點， 是對的 假設對所有j(1j1，則其雙親是i/2l如果2in，則結點i無左孩子；如果2in，則其左孩子是2il如果2i+1n，則結點i無右孩子；如果2i+1n，則其右孩子是2i+11log2nn深度為個結點的完全二叉樹的具有l二叉樹的存儲結構順序存儲結構l實現：按滿二叉樹的結點層次編號，依次存放二叉樹中的數據元素l特點： 結點間關系蘊含在其存儲位置中 浪費空間，適于存滿二叉樹和完全二叉樹abcdefga b c d e 0 0 0 0 f g

5、 1 2 3 4 5 6 7 8 9 10 11l鏈式存儲結構二叉鏈表typedef struct node datatype data; struct node *lchild, *rchild;JD;lchild data rchild ABCDEFG在n個結點的二叉鏈表中，有n+1個空指針域 AB C D E F G空指針個數：2*n0+1*n1+0*n2=2n0+n1=n0+n1+n0=n0+n1+n2+1=n+1l三叉鏈表typedef struct node datatype data; struct node *lchild, *rchild, *parent;JD;lchild

6、 data parent rchildABCDEFG A B C D E F Gl一、下面是有關二叉樹的敘述，請判斷正誤。一、下面是有關二叉樹的敘述，請判斷正誤。l（ ）1. 1. 若二叉樹用二叉鏈表作存貯結構，則在若二叉樹用二叉鏈表作存貯結構，則在n n個結點的二叉樹鏈表個結點的二叉樹鏈表中只有中只有n n1 1個非空指針域。個非空指針域。l（ ）2.2.二叉樹中每個結點的兩棵子樹的高度差等于二叉樹中每個結點的兩棵子樹的高度差等于1 1。 l（ ）3.3.二叉樹中每個結點的兩棵子樹是有序的。二叉樹中每個結點的兩棵子樹是有序的。 l（ ）4.4.二叉樹中每個結點有兩棵非空子樹或有兩棵空子樹。二

7、叉樹中每個結點有兩棵非空子樹或有兩棵空子樹。 l（ ）5.5.二叉樹中每個結點的關鍵字值大于其左非空子樹（若存在的話）二叉樹中每個結點的關鍵字值大于其左非空子樹（若存在的話）所有結點的關鍵字值，且小于其右非空子樹（若存在的話）所有結點的所有結點的關鍵字值，且小于其右非空子樹（若存在的話）所有結點的關鍵字值。關鍵字值。 l（ ）6.6.二叉樹中所有結點個數是二叉樹中所有結點個數是2 2k-1k-1-1-1，其中，其中k k是樹的深度。是樹的深度。 l（ ）7.7.二叉樹中所有結點，如果不存在非空左子樹，則不存在非空右二叉樹中所有結點，如果不存在非空左子樹，則不存在非空右子樹。子樹。 l（ ）8.

8、8.對于一棵非空二叉樹，它的根結點作為第一層，則它的第對于一棵非空二叉樹，它的根結點作為第一層，則它的第i i層層上最多能有上最多能有2 2i i1 1個結點。個結點。 l（ ）9.9.用二叉鏈表法（用二叉鏈表法（link-rlinklink-rlink）存儲包含）存儲包含n n個結點的二叉樹，結個結點的二叉樹，結點的點的2n2n個指針區域中有個指針區域中有n+1n+1個為空指針。個為空指針。l（ ）10. 10. 具有具有1212個結點的完全二叉樹有個結點的完全二叉樹有5 5個度為個度為2 2的結點。的結點。 l二、填空。二、填空。l1 1 由個結點所構成的二叉樹有由個結點所構成的二叉樹有 種形態。種形態。 l2. 2. 一棵深度為一棵深度為6 6的滿二叉樹有的滿二叉樹有 個分個分支結點和支結點和 個葉子。個葉子。l3 3 一棵具有個結點的完全二叉樹，它的深一棵具有個結點的完全二叉樹，它的深度為度為 。l4.4. 設一棵完全二叉樹有設一棵完全二叉樹有700700個結點，則共有個結點，則共有 個葉子結點。個葉子結點。l5. 5. 設一棵完全二叉樹具有設一棵完全二叉樹具有10001000個結點，則此完全二個結點，則此完全二叉樹有叉樹有 個葉子結點，有個葉子結點，有 個度為個度為2 2的結的結點