第五章樹和二叉樹-預覽頁
【正文】 。 typedef struct node { int ltag,rtag。2022/8/17 1 第五章 樹和二叉樹 2022/8/17 2 二叉樹在一般情況下無法直接找到某結(jié)點在 某種遍歷序列中的前驅(qū)和后繼結(jié)點。 一、線索二叉樹 2022/8/17 3 線索二叉樹結(jié)點的描述 typedef int datatype。 } bithptr。 plchild＝ pre。 prerchild = = NULL) { prertag＝ 1。 // 中序向前遍歷一個結(jié)點 INTHREAD(prchild, pre)。 if (prtag==1) return(prchild)。 } } 2022/8/17 9 若 *p 的左子樹為空，則 plchild 為左線 索，直接指向 *p 的中序前驅(qū)結(jié)點。 p＝ INORDERNEXT(p)。 qltag＝ 1。 prtag＝ 0。(sltag==1)) slchild＝ q。 } bitree。 // 將 s插入到左子樹中 else if ( sdata bdata ) INSERT(brchild, s)。 do{ scanf(“%d”,amp。 slchild=NULL。 } 2022/8/17 18 45 24 53 12 28 90 關(guān)鍵字輸入順序： 45， 24， 53，12， 28， 90 2022/8/17 19 二叉排序樹的結(jié)點刪除 (被刪除結(jié)點無左孩子 ) q p q p p是左孩子 p是右孩子 2022/8/17 20 二叉排序樹的結(jié)點刪除 (被刪除結(jié)點有左孩子 ) q p q p p是左孩子 p是右孩子 2022/8/17 21 二叉排序樹的結(jié)點刪除算法 // 在二叉排序樹 b中刪除一個數(shù)據(jù)域為 x的結(jié)點的算法函數(shù) void DELNODE(bitree *b, int x) { bitree *p, *q, *r, *t。amp。 p=prchild。 else qrchild=prchild。 // 被刪結(jié)點的左子樹根代替被刪結(jié)點 if (q==NULL) t=plchild。 else { if (bdata == x) return (b)。 所有葉結(jié)點在同一層，葉結(jié)點不包含任何關(guān)鍵字信息。 ????nkkk lwW P L12022/8/17 33 具有不同帶權(quán)路徑長度的二叉樹 赫夫曼樹 帶權(quán)路徑長度達到最小的二叉樹即為赫夫曼樹。置新的二叉樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和。 設給出一段報文： CAST CAST SAT AT A TASA 字符集合是 { C, A, S, T }，各個字符出現(xiàn)的頻度(次數(shù) )是 W＝ { 2, 7, 4, 5 }。左分支賦 0，右分支賦 1，得赫夫曼編碼 (變長編碼 )。 赫 夫曼編碼是一種 前綴編碼 。 } hufmtree。 for (i=1。 tree[i].rchild=0。i++) { scanf(“%d”,amp。i=m。 small2=MAXVAL。 small1=tree[j].weight。 p2=j。 tree[i].rchild=p2。 char ch。 codetype cd。 c=i。 else []=?1?。 } } 2022/8/17 45 赫夫曼解碼算法 DECODE(codetype code[],hufmtree tree[]) { int i,j,c,p,b。b)。 i=m。 }
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1