離散數(shù)學(xué)課件-第七章-樹(shù)trees

第7章樹(shù)trees分類(lèi)根樹(shù)有序樹(shù)定位樹(shù)無(wú)向樹(shù)標(biāo)號(hào){a,b}無(wú)有無(wú)有無(wú)有無(wú)有N=1N=2N=3§7.1樹(shù)定義1：T是集合A上一個(gè)二元關(guān)系，T稱(chēng)為樹(shù)tree，如果存在v0∈A，任意v∈A，v≠v0，到v0都有唯一一條路徑，（v0,v0）T.T叫做根樹(shù)，記做（T，v0）。A中元素稱(chēng)為T(mén)的頂點(diǎn)vertex，T中元素稱(chēng)為邊，v0稱(chēng)為根root。定理1.設(shè)（T，v0）是樹(shù)，則(a)T中沒(méi)有回路。(b)只有一個(gè)根v0。(c)任意v∈A，v≠v0，v有入度1，v0入度是0。證明：定義2層次levelv0的層次為0，v0的子女offspring層次為1，v0是子女的父母parent。vi的層次為k，vi的子女offspring層次為k＋1，vi是子女的父母parent，T的最大層次稱(chēng)為高度height。無(wú)子女的頂點(diǎn)叫葉leaf。vi的子女叫同胞sibling，同胞如有長(zhǎng)幼，從左到右，老大，老二，老三等，組成線性序，T稱(chēng)為有序樹(shù)，orderedtree定理2.設(shè)（T，v0）是根樹(shù)，則(a)T反自反。(b)T反對(duì)稱(chēng)。(c)(a,b)∈T，(b，c)∈T(a，c)T。定義3：n－樹(shù)：每個(gè)頂點(diǎn)至多n個(gè)子女。二叉樹(shù)：2－樹(shù)。完全n－樹(shù)：每個(gè)非葉頂點(diǎn)恰有n個(gè)子女。定義4Arootedbinarytreeisarooted\o"Treedatastructure"treeinwhicheverynodehasatmosttwochildren.Afullbinarytree(sometimesproperbinarytreeor2-tree)isatreeinwhicheverynodeotherthantheleaveshastwochildren.Aperfectbinarytreeisafullbinarytreeinwhichallleavesareatthesamedepthorsamelevel.[1](Thisisambiguouslyalsocalledacompletebinarytree.)Acompletebinarytreeisabinarytreeinwhicheverylevel,exceptpossiblythelast,iscompletelyfilled,andallnodesareasfarleftaspossible.[2]Aninfinitecompletebinarytreeisatreewithlevels,whereforeachleveldthenumberofexistingnodesatleveldisequalto2d.Thecardinalnumberofthesetofallnodesis.Thecardinalnumberofthesetofallpathsis.Abalancedbinarytreeisatreewherethedepthofallthesub-treesdiffersbyatmost1.定理3.設(shè)（T，v0）是根樹(shù)，v∈T，則T(v)是T的子樹(shù)，T(v)的根是v。HomeworkP248－24918，19，20，21，26，28§7.2標(biāo)識(shí)樹(shù)labeledtrees中綴表達(dá)式centraloperatorexpression（3－2×x）＋（（x－2））＋（3＋x））定位樹(shù)positionaltree定義Positionaln-treeisan-treewhosevertexpotentiallyhasexactlynoffspringorderedby1,2,…,n,butsomeoftheoffspringsmaybemissing.定位3－樹(shù)每個(gè)頂點(diǎn)的子女都有一定位置。定位2－樹(shù)左右子樹(shù)普通二叉樹(shù)。問(wèn)題7.2.1n個(gè)節(jié)點(diǎn)的定位二叉樹(shù)有多少個(gè)？如何枚舉？定位二叉樹(shù)的計(jì)算機(jī)表示ComputerRepresentationofBinaryPositionalTreesIndexLeftDataRight12start026＋337+4483550x0610-12711-098030902010030110x01214×13130x014020HomeworkPP253－25410，11，12，16，18，§7.3樹(shù)的遍歷treesearching（自學(xué)）二叉樹(shù)的遍歷中序遍歷的遞歸算法定義(1)遍歷左子樹(shù)；(2)訪問(wèn)根結(jié)點(diǎn)；(3)遍歷右子樹(shù)。先序遍歷的遞歸算法定義(1)訪問(wèn)根結(jié)點(diǎn)；(2)遍歷左子樹(shù)；(3)遍歷右子樹(shù)。后序遍歷得遞歸算法定義(1)遍歷左子樹(shù)；(2)遍歷右子樹(shù)；(3)訪問(wèn)根結(jié)點(diǎn)樹(shù)的搜索深度優(yōu)先搜索廣度優(yōu)先搜索啟發(fā)式搜索博弈樹(shù)搜索§7.4無(wú)向樹(shù)undirectedtrees無(wú)向圖連通不含回路的圖叫無(wú)向樹(shù)例bbfgdcea無(wú)向樹(shù)：有向樹(shù)的對(duì)稱(chēng)閉包。定義：有向樹(shù)的對(duì)稱(chēng)閉包。定理1.R是對(duì)稱(chēng)關(guān)系。則下列命題等價(jià)thefollowingstatementareequivalent：（TFAE）a)R是無(wú)向樹(shù)。b)R連通connected，無(wú)回路acycle。證明：b)R顯然連通若R有回路a)若R連通無(wú)回路，我們可以在R上構(gòu)造一棵樹(shù)。定理2.R是對(duì)稱(chēng)關(guān)系。TFAER是無(wú)向樹(shù)。R無(wú)回路，每增加一條邊，都產(chǎn)生一個(gè)新的回路。證明：R連通，所以沒(méi)加一邊都有新的回路若R不連通則有兩個(gè)以上連通分支，所以可以加一邊不產(chǎn)生回路R連通，去掉任意一條邊都不連通。證明：若去掉一邊還連通，則原圖一定有回路。若原圖有回路，則可以去掉一邊后仍連通。R無(wú)回路，且有n-1條邊對(duì)定點(diǎn)做歸納即可得邊數(shù)為n-1若原圖不連通，則有k個(gè)連通分支，每支都是樹(shù)，總邊數(shù)為n-k。R連通，且有n-1條邊若原圖有回路，則刪掉k條邊后為樹(shù)，則總邊數(shù)為n-1+k連通圖的生成樹(shù)spanningtree:定義含有所有頂點(diǎn)的極小連通圖.存在性n個(gè)頂點(diǎn)連通圖至少有n-1條邊。m條邊的連通圖去掉m－n＋1條邊可以得到生成樹(shù)。從連通圖中如有回路，去掉回路中的一條邊，繼續(xù)直至沒(méi)有回路，就得到生成樹(shù)唯一性最小生成樹(shù)：權(quán)重最小的生成樹(shù)。帶權(quán)的邊：帶邊長(zhǎng)的邊。帶權(quán)的圖：每邊都帶權(quán)。Prim算法：設(shè)G=<V,E>,1.U={v0},W=V-U,T={}.2.U=U∪{v1},W=W-{v1},T=T∪{(u1,v1)}3.重復(fù)2，直至U=V.例UABCDEFu1v1TKruskal克魯斯卡爾算法G=(V,E)連通圖令T=(V,{})是G的所有頂點(diǎn)而無(wú)邊的非連通圖。選擇E中權(quán)值最小的邊，若該邊連接T的兩個(gè)連通分量，將它加入T,這時(shí)T的連通分量減少1；否則選下一條權(quán)值最小的邊。3重復(fù)1n-1次直到T連通。T就是最小生成樹(shù)ACDFBECFADCDBCABCEEF1234555666ABCDEF123456其他相關(guān)內(nèi)容介紹最快的算法Thefastestminimumspanningtreealgorithmtodatewasdevelopedby\o"BernardChazelle"BernardChazelle,whichisbasedonthe\o"Softheap"softheap,anapproximatepriorityqueue.[1][2]Itsrunningtimeis\o"BigOnotation"O(m

α(m,n)),wheremisthenumberofedges,nisthenumberofverticesandαistheclassicalfunctionalinverseofthe\o"Ackermannfunction"Ackermannfunction.Thefunctionαgrowsextremelyslowly,sothatforallpracticalpurposesitmaybeconsideredaconstantnogreaterthan4;thusChazelle'salgorithmtakesveryclosetolineartime.Degree-constrainedspanningtreeInput:n-nodeundirectedgraphG(V,E);positive\o"Integer"integerk≤n.Question:DoesGhaveaspanningtreeinwhichno\o"Node(computerscience)"nodehasdegreegreaterthank?Degree-constrainedspanningtreeproblemisNPCDirectedminimumspanningtreeEdmonds'salgorithmO(EV)1986,Gabow,Galil,Spencer,andTarjanO(E+VlogV).求從點(diǎn)1出發(fā)的最小樹(shù)形圖對(duì)除1以外的每個(gè)點(diǎn)，選一條指向它的最小權(quán)的邊。將所得到的圖為G，其對(duì)應(yīng)的無(wú)向圖為H若H連通，則已經(jīng)找到。否則H的每個(gè)連通分支，要么是從點(diǎn)1出發(fā)