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