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

第六章樹(shù)一、掌握基本概念樹(shù)的子樹(shù)是互不相交的，樹(shù)可認(rèn)為空(空樹(shù))非空的樹(shù)中，只有一個(gè)結(jié)點(diǎn)是沒(méi)有前趨的,那就是根。非空樹(shù)只有一個(gè)樹(shù)根，是一對(duì)多的關(guān)系。葉子結(jié)點(diǎn)、結(jié)點(diǎn)的度、樹(shù)的度、結(jié)點(diǎn)的層次、樹(shù)的深度、樹(shù)的四種表達(dá)方法二、二叉樹(shù)的定義、特點(diǎn)、五種基本形態(tài)二叉樹(shù)是有序樹(shù)，左右子樹(shù)不能互相顛倒二叉樹(shù)中結(jié)點(diǎn)的最大度為２,但不一定都是2。三、二叉樹(shù)的性質(zhì)要掌握性質(zhì)1:二叉樹(shù)的第i層上至多有2i-1（i1）個(gè)結(jié)點(diǎn)。性質(zhì)２:深度為k的二叉樹(shù)中至多２k－1個(gè)結(jié)點(diǎn)。性質(zhì)3：對(duì)任何一棵二叉樹(shù)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)的完全二叉樹(shù)的深度ｋ為[log2n]+1四、滿(mǎn)二叉樹(shù)和完全二叉樹(shù)的區(qū)別是什么？滿(mǎn)二叉樹(shù)一定是完全二叉樹(shù),但是完全二叉樹(shù)不一定是滿(mǎn)二叉樹(shù)。深度為ｋ的二叉樹(shù),最少有k個(gè)結(jié)點(diǎn)，最多有２k-1深度為ｋ的完全二叉樹(shù)，最少有2k－1-１+１個(gè)結(jié)點(diǎn),最多有2ｋ-1五、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)(可以通過(guò)下標(biāo)找結(jié)點(diǎn)的左右孩子)1.順序存儲(chǔ)結(jié)構(gòu)合用于滿(mǎn)二叉樹(shù)和完全二叉樹(shù)。（其缺陷是必須把其他二叉樹(shù)補(bǔ)成完全二叉樹(shù)，從上到下,從左到右依次存儲(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)不僅找其左、右孩子很方便，并且找其雙親也方便六、遍歷的概念是什么？七、二叉樹(shù)的遍歷有三種：前序(先序、先根）遍歷、中序（中序、中根)遍歷、后序(后序、后根)遍歷１.給出一棵二叉樹(shù),要會(huì)二叉樹(shù)的三種遍歷2.給出兩種遍歷(必須有中序遍歷)，規(guī)定會(huì)畫(huà)該二叉樹(shù)。八、了解引入線索（中序、先序、后序）二叉樹(shù)的因素是什么?九、會(huì)在二叉樹(shù)上畫(huà)先序線索化、中序線索化、后序線索化。在線索二叉樹(shù)的格式中,可以找到任意結(jié)點(diǎn)的直接后繼。(錯(cuò))在線索二叉樹(shù)中,假如某結(jié)點(diǎn)的右孩子為空，那么可以找到該結(jié)點(diǎn)的直接后繼。（對(duì)）在線索二叉樹(shù)中,假如某結(jié)點(diǎn)的左孩子為空,那么可以找到該結(jié)點(diǎn)的直接前趨。（對(duì)）十、樹(shù).森林和二叉樹(shù)的互相轉(zhuǎn)換樹(shù)轉(zhuǎn)換成二叉樹(shù)后，轉(zhuǎn)換后的二叉樹(shù)根的右子樹(shù)為空。十一、森林的遍歷(只有先序遍歷和后序遍歷）先序遍歷一棵樹(shù)，相稱(chēng)于先序遍歷該樹(shù)所相應(yīng)的二叉樹(shù)。后序遍歷一棵樹(shù)，相稱(chēng)于中序遍歷該樹(shù)所相應(yīng)的二叉樹(shù)。十二、赫夫曼樹(shù)(又稱(chēng)最優(yōu)二叉樹(shù)或哈夫曼樹(shù)）、赫夫曼樹(shù)編碼1.赫夫曼樹(shù)中，權(quán)越大的葉子離根越近，其形態(tài)不唯一，但是ＷPL帶權(quán)途徑長(zhǎng)度一定是最小。2.一定要會(huì)構(gòu)造哈夫曼樹(shù),在構(gòu)造好的哈夫曼樹(shù)上會(huì)構(gòu)造哈夫曼編碼。(認(rèn)真看題目規(guī)定）第６章算法設(shè)計(jì)題1.已知二叉樹(shù)中的結(jié)點(diǎn)類(lèi)型用Ｂ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)的指針域，編寫(xiě)出求一棵二叉樹(shù)高度的算法。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)；}}２．已知二叉樹(shù)中的結(jié)點(diǎn)類(lèi)型用BｉＴＮode表達(dá)，被定義描述為：TyｐeｄｅfsｔｒuctBiＴNode{TEleｍＴypedａt(yī)a;structＢｉT(mén)Noｄe*LCｈｉld,*Rchｉld；}BiTＮodｅ,＊ＢiＴrｅe(cuò);BiTreeＴ;其中ｄatａ為結(jié)點(diǎn)值域,ＬＣｈild和RCｈiｌd分別為指向左、右孩子結(jié)點(diǎn)的指針域，編寫(xiě)算法,求出二叉樹(shù)中２度結(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.已知二叉樹(shù)中的結(jié)點(diǎn)類(lèi)型用ＢiTNode表達(dá)，被定義描述為:TｙpeｄefstructBｉT(mén)Node{Ｔ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)的指針域，寫(xiě)一算法,求出二叉樹(shù)中的葉子結(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)；／/訪問(wèn)左子樹(shù)BTreeLeaf(BＴ->RCｈild);//訪問(wèn)右子樹(shù)}}或下面算法均可編寫(xiě)遞歸算法,計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目。ｉnｔLeafCouｎt＿BiTrｅe(cuò)(BｉtreeＴ)//求二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目{

iｆ(!T）ｒeturn0；//空樹(shù)沒(méi)有葉子

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

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