資源描述：
《第6章-樹與二叉樹》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、本章主要內(nèi)容:樹二叉樹樹、森林與二叉樹的轉(zhuǎn)換樹的應(yīng)用本章重點:樹的各種表示、各種存儲方式和運算，二叉樹的概念及其上的運算和應(yīng)用。本章難點:二叉樹的非遞歸運算及應(yīng)用。第六章樹和二叉樹16.1樹樹的定義樹是由n(n?0)個結(jié)點組成的有限集合。如果n=0，稱為空樹；如果n>0，則?有一個特定的稱之為根(root)的結(jié)點，它只有直接后繼，但沒有直接前驅(qū)；?除根以外的其它結(jié)點劃分為m(m?0)個互不相交的有限集合T0,T1,…,Tm-1，每個集合又是一棵樹，并且稱之為根的子樹(subTree)。每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，但可以有0個或多個直接后繼。2結(jié)點(n
2、ode)結(jié)點的度(degree)結(jié)點的子樹個數(shù)分支(branch)結(jié)點度不為0的結(jié)點葉(leaf)結(jié)點度為0的結(jié)點子女(child)結(jié)點某結(jié)點子樹的根結(jié)點雙親(parent)結(jié)點某個結(jié)點是其子樹之根的雙親3兄弟(sibling)結(jié)點具有同一雙親的所有結(jié)點祖先(ancestor)結(jié)點若樹中結(jié)點k到ks存在一條路徑，則稱k是ks的祖先子孫(descendant)結(jié)點若樹中結(jié)點k到ks存在一條路徑，則稱ks是k的子孫結(jié)點所處層次(level)根結(jié)點的層數(shù)為0，其余結(jié)點的層數(shù)為雙親結(jié)點的層數(shù)加1樹的高度(depth)樹中結(jié)點的最大層數(shù)樹的度(degree)樹中所有結(jié)點
3、度的最大值有序樹子樹的次序不能互換無序樹子樹的次序可以互換森林互不相交的樹的集合4樹的表示樹型表示bacghdefij5凹入表表示abdeijfcgh6嵌套集合表示嵌套括號表示ijdfghabcea(b(d,e(i,j),f),c(g,h))7樹的存儲結(jié)構(gòu)1雙親的表示法2孩子表示法3雙親孩子表示法4孩子兄弟表示法樹轉(zhuǎn)二叉樹的方法8雙親表示法實現(xiàn)：定義結(jié)構(gòu)數(shù)組存放樹的結(jié)點，每個結(jié)點含兩個域：數(shù)據(jù)域：存放結(jié)點本身信息雙親域：指示本結(jié)點的雙親結(jié)點在數(shù)組中位置特點：找雙親容易，找孩子難typedefstructnode{datatypedata;intparent;}
4、bnode;bnodet[M];9abcdefhgiacdefghib012235551601234578dataparent如何找孩子結(jié)點10孩子表示法多重鏈表：每個結(jié)點有多個指針域，分別指向其子樹的根結(jié)點同構(gòu)：結(jié)點的指針個數(shù)相等，為樹的度D結(jié)點不同構(gòu)：結(jié)點指針個數(shù)不等，為該結(jié)點的度ddatachild1child2……….childDdatadegreechild1child2……….childd孩子鏈表：每個結(jié)點的孩子結(jié)點用單鏈表存儲，再用含n個元素的結(jié)構(gòu)數(shù)組指向每個孩子鏈表孩子結(jié)點：typedefstructnode{intchild;//該結(jié)點在表頭
5、數(shù)組中下標(biāo)structnode*next;//指向下一孩子結(jié)點}bnode;表頭結(jié)點：typedefstructtnode{datatypedata;//數(shù)據(jù)域structnode*fc;//指向第一個孩子結(jié)點}TD;TDt[M];//t[0]不用11abcdefhgi6012345789acdefghibdatafc23^45^^978^6^^^^^如何找雙親結(jié)點12帶雙親的孩子鏈表612345789acdefghibdatafc23459786^^^^^^^^^012235551parentabcdefhgi13孩子兄弟表示法（二叉樹表示法）實現(xiàn)：用二叉鏈
6、表作樹的存儲結(jié)構(gòu)，鏈表中每個結(jié)點的兩個指針域分別指向其第一個孩子結(jié)點和下一個兄弟結(jié)點特點操作容易破壞了樹的層次typedefstructnode{datatypedata;structnode*fch,*nsib;}bnode;abcdefhgiabcdefghi^^^^^^^^^^146.2二叉樹(BinaryTree)二叉樹的定義二叉樹的五種不同形態(tài)一棵二叉樹是結(jié)點的一個有限集合，該集合或者為空，或者是由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。15定義1滿二叉樹(FullBinaryTree)一棵深度為k且有2k+1-1個結(jié)點的二
7、叉樹。245367116定義2完全二叉樹(CompleteBinaryTree)若設(shè)二叉樹的高度為h，則共有h+1層。除第h層外，其它各層(0?h-1)的結(jié)點數(shù)都達(dá)到最大個數(shù)，第h層從右向左連續(xù)缺若干結(jié)點，這就是完全二叉樹。17123114589121367101415123114589126710123456712345618二叉樹的抽象數(shù)據(jù)類型數(shù)據(jù)集合:二叉樹結(jié)點的集合,每個結(jié)點由數(shù)據(jù)元素和構(gòu)造數(shù)據(jù)元素之間的關(guān)系的指針組成.操作集合:創(chuàng)建:MakeTree(T)撤消:DestroyTree(T)左插入結(jié)點:InsertLeftNode(curr,x)右插入
8、結(jié)點:InsertRightNode(
