樹與二叉樹ppt課件

1、第六章 樹和二叉樹 樹是一類重要的非線性數(shù)據(jù)構(gòu)造，是以分支關(guān)系定義的層次構(gòu)造5.1 樹的定義定義定義：樹(tree)是n(n0)個結(jié)點的有限集T，其中：有且僅有一個特定的結(jié)點，稱為樹的根(root)當n1時，其他結(jié)點可分為m(m0)個互不相交的有限集T1,T2,Tm，其中每一個集合本身又是一棵樹，稱為根的子樹(subtree)特點：樹中至少有一個結(jié)點根樹中各子樹是互不相交的集合A只需根結(jié)點的樹ABCDEFGHIJKLM有子樹的樹根子樹根本術(shù)語結(jié)點(node)表示樹中的元素，包括數(shù)據(jù)項及假設(shè)干指向其子樹的分支結(jié)點的度(degree)結(jié)點擁有的子樹數(shù)葉子(leaf)度為0的結(jié)點孩子(child)結(jié)

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

3、先bacghdefijabdeijfcghijdfghabcea ( b ( d, e ( i, j ), c ( g, h ) ) )5.2 二叉樹定義定義：二叉樹是n(n0)個結(jié)點的有限集，它或為空樹(n=0)，或由一個根結(jié)點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成特點每個結(jié)點至多有二棵子樹(即不存在度大于2的結(jié)點)二叉樹的子樹有左、右之分，且其次序不能恣意顛倒根本形狀A(yù)只需根結(jié)點的二叉樹空二叉樹AB右子樹為空AB左子樹為空ABC左、右子樹均非空二叉樹性質(zhì)性質(zhì)1：) 1(21iii個結(jié)點層上至多有在二叉樹的第證明：用歸納法證明之 i=1時，只需一個根結(jié)點， 是對的 假設(shè)對一切j(

4、1j1，那么其雙親是i/2u (2) 假設(shè)2in，那么結(jié)點i無左孩子；假設(shè)2in，那么其左孩子是2iu (3) 假設(shè)2i+1n，那么結(jié)點i無右孩子；假設(shè)2i+1n，那么其右孩子是2i+15.3 樹的存儲構(gòu)造樹的存儲構(gòu)造雙親表示法實現(xiàn)：定義構(gòu)造數(shù)組存放樹的結(jié)點，每個結(jié)點含兩個域：數(shù)據(jù)域：存放結(jié)點本身信息雙親域：指示本結(jié)點的雙親結(jié)點在數(shù)組中位置特點：找雙親容易，找孩子難typedef struct node datatype data; int parent;JD;JD tM;abcdefhgiacdefghib012235551096012345789dataparent0號單元不用或存結(jié)點個數(shù)

5、如何找孩子結(jié)點v孩子表示法v多重鏈表：每個結(jié)點有多個指針域，分別指向其子樹的根v結(jié)點同構(gòu)：結(jié)點的指針個數(shù)相等，為樹的度Dv結(jié)點不同構(gòu)：結(jié)點指針個數(shù)不等，為該結(jié)點的度ddata child1 child2 . childDdata degree child1 child2 . childdl孩子鏈表：每個結(jié)點的孩子結(jié)點用單鏈表存儲，再用含n個元素的構(gòu)造數(shù)組指向每個孩子鏈表孩子結(jié)點：typedef struct node int child; /該結(jié)點在表頭數(shù)組中下標 struct node *next; /指向下一孩子結(jié)點 JD;表頭結(jié)點：typedef struct tnode datatyp

6、e data; /數(shù)據(jù)域 struct node *fc; /指向第一個孩子結(jié)點 TD; TD tM; /t0不用abcdefhgi6012345789acdefghibdatafc 2 3 4 5 9 7 8 6如何找雙親結(jié)點l帶雙親的孩子鏈表612345789acdefghibdatafc 2 3 4 5 9 7 8 6012235551parentabcdefhgiv孩子兄弟表示法二叉樹表示法v實現(xiàn)：用二叉鏈表作樹的存儲構(gòu)造，鏈表中每個結(jié)點的兩個指針域分別指向其第一個孩子結(jié)點和下一個兄弟結(jié)點v特點v操作容易v破壞了樹的層次typedef struct node datatype data; struct node *fch, *nsib;JD;abcdefhgi a b c d e f g h i二叉樹的存儲構(gòu)造順序存儲構(gòu)造實現(xiàn)：按滿二叉樹的結(jié)點層次編號，依