第6章樹和二叉樹1-樹的定義和性質(zhì)

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

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

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

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

5、 1 2 3 4 5 6 7 8 9 10 11l鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉鏈表typedef struct node datatype data; struct node *lchild, *rchild;JD;lchild data rchild ABCDEFG在n個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空指針域 AB C D E F G空指針個(gè)數(shù)：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一、下面是有關(guān)二叉樹的敘述，請判斷正誤。一、下面是有關(guān)二叉樹的敘述，請判斷正誤。l（ ）1. 1. 若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n n個(gè)結(jié)點(diǎn)的二叉樹鏈表個(gè)結(jié)點(diǎn)的二叉樹鏈表中只有中只有n n1 1個(gè)非空指針域。個(gè)非空指針域。l（ ）2.2.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹的高度差等于二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹的高度差等于1 1。 l（ ）3.3.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹是有序的。二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹是有序的。 l（ ）4.4.二叉樹中每個(gè)結(jié)點(diǎn)有兩棵非空子樹或有兩棵空子樹。二

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

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