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

1、第六章 樹一、掌握基本概念 樹的子樹是互不相交的，樹可以為空（空樹） 非空的樹中，只有一個(gè)結(jié)點(diǎn)是沒有前趨的，那就是根。非空樹只有一個(gè)樹根，是一對(duì)多的關(guān)系。葉子結(jié)點(diǎn)、結(jié)點(diǎn)的度、樹的度、結(jié)點(diǎn)的層次、樹的深度、樹的四種表示方法二、二叉樹的定義、特點(diǎn)、五種基本形態(tài)二叉樹是有序樹，左右子樹不能互相顛倒二叉樹中結(jié)點(diǎn)的最大度為2，但不一定都是2。三、二叉樹的性質(zhì)要掌握性質(zhì)1：二叉樹的第i層上至多有2 i-1（i 1）個(gè)結(jié)點(diǎn)。性質(zhì)2：深度為k的二叉樹中至多2k-1個(gè)結(jié)點(diǎn)。性質(zhì)3：對(duì)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0n21。 證明：1)結(jié)點(diǎn)總數(shù) n=n0+n1+n2 (n1是

2、度為1的結(jié)點(diǎn)數(shù)) 2)進(jìn)入分支總數(shù)m(每個(gè)結(jié)點(diǎn)唯一分支進(jìn)入) n=m+1 3)m個(gè)分支是由非葉子結(jié)點(diǎn)射出 m=n1+2n2性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度k為log2n+1四、滿二叉樹和完全二叉樹的區(qū)別是什么？ 滿二叉樹一定是完全二叉樹，但是完全二叉樹不一定是滿二叉樹。深度為k的二叉樹，最少有k個(gè)結(jié)點(diǎn)，最多有2k-1深度為k的完全二叉樹，最少有2k-1-1+1個(gè)結(jié)點(diǎn),最多有2k-1五、二叉樹的存儲(chǔ)結(jié)構(gòu)（可以通過下標(biāo)找結(jié)點(diǎn)的左右孩子） 1.順序存儲(chǔ)結(jié)構(gòu)適用于滿二叉樹和完全二叉樹。（其缺點(diǎn)是必須把其他二叉樹補(bǔ)成完全二叉樹，從上到下，從左到右依次存儲(chǔ)在順序存儲(chǔ)空間里，會(huì)造成空間浪費(fèi)）2.二叉鏈

3、表存儲(chǔ)結(jié)構(gòu)（其優(yōu)點(diǎn)是找左孩子和右孩子方便，但缺點(diǎn)是找父節(jié)點(diǎn)麻煩）lchild Datarchild （重點(diǎn)） 3. 三叉鏈表存儲(chǔ)結(jié)構(gòu) 不僅找其左、右孩子很方便，而且找其雙親也方便六、遍歷的概念是什么？七、二叉樹的遍歷有三種：前序（先序、先根）遍歷、中序（中序、中根）遍歷、后序（后序、后根）遍歷 1.給出一棵二叉樹，要會(huì)二叉樹的三種遍歷2.給出兩種遍歷（必須有中序遍歷），要求會(huì)畫該二叉樹。八、了解引入線索（中序、先序、后序）二叉樹的原因是什么？九、會(huì)在二叉樹上畫先序線索化、中序線索化、后序線索化。在線索二叉樹的格式中，可以找到任意結(jié)點(diǎn)的直接后繼。（錯(cuò)）在線索二叉樹中，如果某結(jié)點(diǎn)的右孩子為空，那么

4、可以找到該結(jié)點(diǎn)的直接后繼。（對(duì)）在線索二叉樹中，如果某結(jié)點(diǎn)的左孩子為空，那么可以找到該結(jié)點(diǎn)的直接前趨。（對(duì)）十、樹.森林和二叉樹的相互轉(zhuǎn)換 樹轉(zhuǎn)換成二叉樹后，轉(zhuǎn)換后的二叉樹根的右子樹為空。十一、森林的遍歷（只有先序遍歷和后序遍歷）先序遍歷一棵樹，相當(dāng)于先序遍歷該樹所對(duì)應(yīng)的二叉樹。后序遍歷一棵樹，相當(dāng)于中序遍歷該樹所對(duì)應(yīng)的二叉樹。十二、赫夫曼樹（又稱最優(yōu)二叉樹或哈夫曼樹）、赫夫曼樹編碼 1. 赫夫曼樹中，權(quán)越大的葉子離根越近，其形態(tài)不唯一，但是WPL帶權(quán)路徑長(zhǎng)度一定是最小。2.一定要會(huì)構(gòu)造哈夫曼樹，在構(gòu)造好的哈夫曼樹上會(huì)構(gòu)造哈夫曼編碼。（認(rèn)真看題目要求）第6章算法設(shè)計(jì)題1已知二叉樹中的結(jié)點(diǎn)類型用

5、BiTNode表示，被定義描述為：Typedef struct BiTNode TElemType data ; struct BiTNode * LChild , *RChild; BiTNode,*BiTree;其中data為結(jié)點(diǎn)值域，LChild和RChild分別為指向左、右孩子結(jié)點(diǎn)的指針域，編寫出求一棵二叉樹高度的算法。 Int BTreeHeight(BiTree BT) if (BT=NULL) return 0; else h1=BTreeHeight(BT-LChild); h2=BTreeHeight(BT-RChild); if (h1h2) return(h1+1); e

6、lse return( h2+1); 2已知二叉樹中的結(jié)點(diǎn)類型用BiTNode表示，被定義描述為：Typedef struct BiTNode TElemType data ; struct BiTNode * LChild , *Rchild； BiTNode,*BiTree；BiTree T；其中data為結(jié)點(diǎn)值域，LChild和RChild分別為指向左、右孩子結(jié)點(diǎn)的指針域，編寫算法，求出二叉樹中2度結(jié)點(diǎn)個(gè)數(shù)。int degree2nodenum(BiTree T) if (T) if(T-lchild！=NULL &T-child！=NULL) count+; leafnodenum(l

7、-lchild); leafnodenum(l-rchild); return count; 3已知二叉樹中的結(jié)點(diǎn)類型用BiTNode表示，被定義描述為：Typedef struct BiTNode TElemType data ; struct BiTNode * LChild , *RChild; BiTNode,*BiTree;BiTree T；其中data為結(jié)點(diǎn)值域，LChild和RChild分別為指向左、右孩子結(jié)點(diǎn)的指針域，寫一算法，求出二叉樹中的葉子結(jié)點(diǎn)個(gè)數(shù)。void BTreeLeaf (BiTree BT)if(BT) if(BT- LChild=NULL & BT-RChil

8、d=NULL) count+; BTreeLeaf (BT-LChild); / 訪問左子樹BTreeLeaf (BT-RChild); / 訪問右子樹 或下面算法均可編寫遞歸算法，計(jì)算二叉樹中葉子結(jié)點(diǎn)的數(shù)目。int LeafCount_BiTree(Bitree T)/求二叉樹中葉子結(jié)點(diǎn)的數(shù)目if(!T) return 0; /空樹沒有葉子else if(!T-lchild&!T-rchild) return 1; /葉子結(jié)點(diǎn)else return Leaf_Count(T-lchild)+Leaf_Count(T-rchild);/左子樹的葉子數(shù)加上右子樹的葉子數(shù)/LeafCount_Bi

9、Tree4PPT上的三種遍歷遞歸算法和課本上P131先序遞歸創(chuàng)建二叉鏈表。5. 給定一棵二叉樹，其根指針為root。試寫出求二叉樹結(jié)點(diǎn)數(shù)目的算法（遞歸算法或非遞歸算法）。【提示】采用遞歸算法實(shí)現(xiàn)。int count(BiTree t)if (t=NULL)return 0;elsereturn count(t-lchild)+count(t-rchild)+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)的左右子樹?！舅惴ā縱oid Exchg(BiTree *t) BinNode *p; if (t) P=(*t)-lchild; (*t)-lchild=(*t)-rchild; (*t)-rchild=p; Exchg(&(*t)-lchild); Exchg(&(*t)-rchild); 7. 已知一棵二叉樹采用二叉鏈表結(jié)構(gòu)存儲(chǔ)，每個(gè)結(jié)點(diǎn)的值為整數(shù)類型。要求：給出相應(yīng)的語言描述，在此基礎(chǔ)上設(shè)計(jì)計(jì)算二叉樹中所有結(jié)點(diǎn)值之和的算法。typedef struct linkint d