2023年離散數(shù)學(xué)樹知識(shí)點(diǎn)總結(jié)

第六章樹一、掌握基本概念樹的子樹是互不相交的，樹可認(rèn)為空(空樹)非空的樹中，只有一個(gè)結(jié)點(diǎn)是沒有前趨的,那就是根。非空樹只有一個(gè)樹根，是一對(duì)多的關(guān)系。葉子結(jié)點(diǎn)、結(jié)點(diǎn)的度、樹的度、結(jié)點(diǎn)的層次、樹的深度、樹的四種表達(dá)方法二、二叉樹的定義、特點(diǎn)、五種基本形態(tài)二叉樹是有序樹，左右子樹不能互相顛倒二叉樹中結(jié)點(diǎn)的最大度為２,但不一定都是2。三、二叉樹的性質(zhì)要掌握性質(zhì)1:二叉樹的第i層上至多有2i-1（i1）個(gè)結(jié)點(diǎn)。性質(zhì)２:深度為k的二叉樹中至多２k－1個(gè)結(jié)點(diǎn)。性質(zhì)3：對(duì)任何一棵二叉樹T,假如其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0＝n2+1。證明：1)結(jié)點(diǎn)總數(shù)ｎ=ｎ0+n1+ｎ2(n1是度為1的結(jié)點(diǎn)數(shù))2）進(jìn)入分支總數(shù)m（每個(gè)結(jié)點(diǎn)唯一分支進(jìn)入)n＝m+１3)m個(gè)分支是由非葉子結(jié)點(diǎn)射出m=n1+２n2性質(zhì)４：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度ｋ為[log2n]+1四、滿二叉樹和完全二叉樹的區(qū)別是什么？滿二叉樹一定是完全二叉樹,但是完全二叉樹不一定是滿二叉樹。深度為ｋ的二叉樹,最少有k個(gè)結(jié)點(diǎn)，最多有２k-1深度為ｋ的完全二叉樹，最少有2k－1-１+１個(gè)結(jié)點(diǎn),最多有2ｋ-1五、二叉樹的存儲(chǔ)結(jié)構(gòu)(可以通過下標(biāo)找結(jié)點(diǎn)的左右孩子)1.順序存儲(chǔ)結(jié)構(gòu)合用于滿二叉樹和完全二叉樹。（其缺陷是必須把其他二叉樹補(bǔ)成完全二叉樹，從上到下,從左到右依次存儲(chǔ)在順序存儲(chǔ)空間里,會(huì)導(dǎo)致空間浪費(fèi)）2.二叉鏈表存儲(chǔ)結(jié)構(gòu)(其優(yōu)點(diǎn)是找左孩子和右孩子方便，但缺陷是找父節(jié)點(diǎn)麻煩）lchild Ｄaｔａ?ｒｃhｉｌｄ(重點(diǎn)）3.三叉鏈表存儲(chǔ)結(jié)構(gòu)不僅找其左、右孩子很方便，并且找其雙親也方便六、遍歷的概念是什么？七、二叉樹的遍歷有三種：前序(先序、先根）遍歷、中序（中序、中根)遍歷、后序(后序、后根)遍歷１.給出一棵二叉樹,要會(huì)二叉樹的三種遍歷2.給出兩種遍歷(必須有中序遍歷)，規(guī)定會(huì)畫該二叉樹。八、了解引入線索（中序、先序、后序）二叉樹的因素是什么?九、會(huì)在二叉樹上畫先序線索化、中序線索化、后序線索化。在線索二叉樹的格式中,可以找到任意結(jié)點(diǎn)的直接后繼。(錯(cuò))在線索二叉樹中,假如某結(jié)點(diǎn)的右孩子為空，那么可以找到該結(jié)點(diǎn)的直接后繼。（對(duì)）在線索二叉樹中,假如某結(jié)點(diǎn)的左孩子為空,那么可以找到該結(jié)點(diǎn)的直接前趨。（對(duì)）十、樹.森林和二叉樹的互相轉(zhuǎn)換樹轉(zhuǎn)換成二叉樹后，轉(zhuǎn)換后的二叉樹根的右子樹為空。十一、森林的遍歷(只有先序遍歷和后序遍歷）先序遍歷一棵樹，相稱于先序遍歷該樹所相應(yīng)的二叉樹。后序遍歷一棵樹，相稱于中序遍歷該樹所相應(yīng)的二叉樹。十二、赫夫曼樹(又稱最優(yōu)二叉樹或哈夫曼樹）、赫夫曼樹編碼1.赫夫曼樹中，權(quán)越大的葉子離根越近，其形態(tài)不唯一，但是ＷPL帶權(quán)途徑長(zhǎng)度一定是最小。2.一定要會(huì)構(gòu)造哈夫曼樹,在構(gòu)造好的哈夫曼樹上會(huì)構(gòu)造哈夫曼編碼。(認(rèn)真看題目規(guī)定）第６章算法設(shè)計(jì)題1.已知二叉樹中的結(jié)點(diǎn)類型用ＢiTNｏｄe表達(dá)，被定義描述為:ＴypｅdefstｒuctBiTNｏｄe{ＴEｌemTｙpedatａ；structBiTNodｅ*ＬＣhild,*RChiｌd；｝BiＴNode,＊ＢｉＴree;其中datａ為結(jié)點(diǎn)值域，LChｉld和ＲChild分別為指向左、右孩子結(jié)點(diǎn)的指針域，編寫出求一棵二叉樹高度的算法。InｔBＴreeHeｉght（BiTreeＢＴ）{if(ＢT=＝NＵLＬ）reｔuｒn0；elsｅ{h1=ＢTreｅHeigｈt（BＴ－>LＣhild）；h2=BTrｅe(cuò)Hｅｉght(ＢT->ＲChｉlｄ);if(h１＞h2)reｔｕrn(ｈ1+1);elsｅrｅturn(h２+1)；}}２．已知二叉樹中的結(jié)點(diǎn)類型用BｉＴＮode表達(dá)，被定義描述為：TyｐeｄｅfsｔｒuctBiＴNode{TEleｍＴypedａt(yī)a;structＢｉTNoｄe*LCｈｉld,*Rchｉld；}BiTＮodｅ,＊ＢiＴrｅe(cuò);BiTreeＴ;其中ｄatａ為結(jié)點(diǎn)值域,ＬＣｈild和RCｈiｌd分別為指向左、右孩子結(jié)點(diǎn)的指針域，編寫算法,求出二叉樹中２度結(jié)點(diǎn)個(gè)數(shù)。intdｅｇree2nodenｕｍ(BiTreeT）{iｆ(Ｔ){ｉｆ(Ｔ-＞lｃhild！=NULL＆&T->cｈild！=NUＬＬ)cｏｕnt＋+;leafｎｏdenuｍ(l－>lchｉlｄ)；lｅａfnｏdenum(l->ｒchild);}retｕrｎcoｕnt;}3.已知二叉樹中的結(jié)點(diǎn)類型用ＢiTNode表達(dá)，被定義描述為:TｙpeｄefstructBｉTNode{ＴEleｍTｙｐeｄａt(yī)a；strｕｃtBiTNode*LＣhｉlｄ,*ＲChｉld;}BiTNodｅ,*BiTｒeｅ;BiTreeT;其中data為結(jié)點(diǎn)值域,LChiｌd和RChｉｌd分別為指向左、右孩子結(jié)點(diǎn)的指針域，寫一算法,求出二叉樹中的葉子結(jié)點(diǎn)個(gè)數(shù)。ｖｏidBTrｅe(cuò)Leaｆ(BiTｒeeＢT）｛if（BT){if（BT->LChｉlｄ=＝NULＬ&&ＢＴ->RCｈild==ＮＵLL)count+＋;BＴreeLeaf(BT-＞LChild)；／/訪問左子樹BTreeLeaf(BＴ->RCｈild);//訪問右子樹}}或下面算法均可編寫遞歸算法,計(jì)算二叉樹中葉子結(jié)點(diǎn)的數(shù)目。ｉnｔLeafCouｎt＿BiTrｅe(cuò)(BｉtreeＴ)//求二叉樹中葉子結(jié)點(diǎn)的數(shù)目{

iｆ(!T）ｒeturn0；//空樹沒有葉子

elsｅif(!T－>lchild＆&！T-＞rchild)return１;//葉子結(jié)點(diǎn)

elsereturｎLeaf_Coｕｎt(T-＞lｃｈild）+Leaf_Count(T－>rchiｌｄ)；/／左子樹的葉子數(shù)加上右子樹的葉子數(shù)}/／LｅａｆCoｕnt_BiＴｒeｅ4．PPT上的三種遍歷遞歸算法和課本上P１31先序遞歸創(chuàng)建二叉鏈表。5.給定一棵二叉樹，其根指針為rｏｏt。試寫出求二叉樹結(jié)點(diǎn)數(shù)目的算法（遞歸算法或非遞歸算法）。?【提醒】采用遞歸算法實(shí)現(xiàn)。ｉntcｏｕnt(ＢｉTｒeｅt）{if(ｔ==NULL)rｅturn０;eｌseretｕrnｃount(t->lchｉlｄ）+ｃounｔ(t->rｃhｉｌｄ)＋1；}6.以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，寫一算法互換各結(jié)點(diǎn)的左右子樹?！痉治觥恳李}意，設(shè)t為一棵用二叉鏈表存儲(chǔ)的二叉樹，則互換各結(jié)點(diǎn)的左右子樹的運(yùn)算基于后序遍歷實(shí)現(xiàn)：互換左子樹上各結(jié)點(diǎn)的左右子樹;互換右子樹上各結(jié)點(diǎn)的左右子樹;再互換根結(jié)點(diǎn)的左右子樹。【算法】voｉdExchg(BｉTree*t)｛ＢinNｏde＊p;ｉf(t){Ｐ=(*t)-＞lchild；(*ｔ)->ｌchild=(＊ｔ)－＞rｃｈiｌd;(*ｔ）-＞rcｈｉlｄ＝p;Ｅxchg(&(（＊t）－>lchiｌd））;Exｃhg（&（(*t)->ｒchilｄ）);}｝７．已知一棵二叉樹采用二叉鏈表結(jié)構(gòu)存儲(chǔ),每個(gè)結(jié)點(diǎn)的值為整數(shù)類型。規(guī)定：給出相應(yīng)的語言描述，在此基礎(chǔ)上設(shè)計(jì)計(jì)算二叉樹中所有結(jié)點(diǎn)值之和的算法。tyｐedefstruｃｔlｉnｋ｛inｔ