數(shù)據(jù)結(jié)構(gòu)(c語(yǔ)言版)樹(shù)、二叉樹(shù)詳細(xì)舉例介紹(編輯修改稿)
2024-07-16 16:19 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 r = CopyTree(Trchild)。//復(fù)制右子樹(shù) else newrptr = NULL。 newT=GetTreeNode(Tdata,newlptr,newrptr)。 return newT。 } 問(wèn)題 ： 若用先序框架，應(yīng)如何修改？ A B C D E F G H K ^ D ^ C ^ ^ B ^ H ^ ^ K ^ G F ^ E ^ A 例如 :下列二叉樹(shù)的復(fù)制過(guò)程如下 : newT 4. 建立二叉樹(shù)的 存儲(chǔ)結(jié)構(gòu) 不同的定義方法相應(yīng)有不同的存儲(chǔ)結(jié)構(gòu)的建立算法 以字符串的形式 根 左子樹(shù) 右子樹(shù) 定義一棵二叉樹(shù) 例如 : A B C D 以空白字符“ ”表示 A(B( ,C( , )),D( , )) 空樹(shù) 只含一個(gè)根結(jié)點(diǎn)的二叉樹(shù) A 以字符串“ A ” 表示 以下列字符串表示 Status CreateBiTree(BiTree amp。T) { scanf(amp。ch)。 if (ch==39。 39。) T = NULL。 else { if (!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW)。 Tdata = ch。 // 生成根結(jié)點(diǎn) CreateBiTree(Tlchild)。 // 構(gòu)造左子樹(shù) CreateBiTree(Trchild)。 // 構(gòu)造右子樹(shù) } return OK。 } A B C D B C D 上頁(yè)算法執(zhí)行過(guò)程舉例如下 : A T B C D ^ ^ ^ ^ ^ 按給定的表達(dá)式建相應(yīng)二叉樹(shù) ? 由先綴表示式建樹(shù) 例如：已知表達(dá)式的先綴表示式 + a b c / d e ? 由原表達(dá)式建樹(shù) 例如：已知表達(dá)式 (a+b) c – d/e 對(duì)應(yīng)先綴表達(dá)式 + a b c / d e的二叉樹(shù) a b c d e + / 特點(diǎn) ： 操作數(shù) 為葉子結(jié)點(diǎn)， 運(yùn)算符 為分支結(jié)點(diǎn) scanf(amp。ch)。 if ( In(ch, 字母集 )) 建葉子結(jié)點(diǎn) 。 else { 建根結(jié)點(diǎn) 。 遞歸建左子樹(shù) 。 遞歸建右子樹(shù) 。 } 由先綴表示式建樹(shù)的算法的基本操作： a+b (a+b) c – d/e a+b c 分析表達(dá)式和二叉樹(shù)的關(guān)系 : a b + a b c + a b c + (a+b) c a b c d e + / 基本操作 : scanf(amp。ch)。 if (In(ch, 字母集 )) { 建葉子結(jié)點(diǎn) 。 暫存 。 } else if (In(ch, 運(yùn)算符集 )) { 和前一個(gè)運(yùn)算符比較優(yōu)先數(shù) 。 若當(dāng)前的優(yōu)先數(shù)“高”，則暫存 。 否則建子樹(shù) 。 } void CrtExptree(BiTree amp。T, char exp[] ) { InitStack(S)。 Push(S, ??)。 InitStack(PTR)。 p = exp。 ch = *p。 while (!(GetTop(S)==?? amp。amp。 ch==??)) { if (!IN(ch, OP)) CrtNode( t, ch )。 // 建葉子結(jié)點(diǎn)并入棧 else { } if ( ch!= ?? ) { p++。 ch = *p。} } Pop(PTR, T)。 } … … switch (ch) { case ?(? : Push(S, ch)。 break。 case ?)? : Pop(S, c)。 while (c!= ?(? ) { CrtSubtree( t, c)。 //建二叉樹(shù)并入棧 Pop(S, c)。 } break。 defult : } // switch … … while(!Gettop(S, c) amp。amp。 ( precede(c,ch))) { CrtSubtree( t, c)。 Pop(S, c)。 } if ( ch!= ?? ) Push( S, ch)。 break。 建葉子結(jié)點(diǎn)的算法為： void CrtNode(BiTreeamp。 T,char ch) { T=(BiTNode*)malloc(sizeof(BiTNode))。 Tdata = char。 Tlchild = Trchild = NULL。 Push( PTR, T )。 } 建子樹(shù)的算法為： void CrtSubtree (Bitreeamp。 T, char c) { T=(BiTNode*)malloc(sizeof(BiTNode))。 Tdata = c。 Pop(PTR, rc)。 Trchild = rc。 Pop(PTR, lc)。 Tlchild = lc。 Push(PTR, T)。 } 僅知二叉樹(shù)的先序序列“ abcdefg” 不能唯一確定一棵二叉樹(shù)， 由二叉樹(shù)的先序和中序序列建樹(shù) 如果同時(shí)已知二叉樹(shù)的中序序列“ cbdaegf”, 則會(huì)如何？ 二叉樹(shù)的先序序列 二叉樹(shù)的中序序列 左子樹(shù) 左子樹(shù) 右子樹(shù) 右子樹(shù) 根 根 a b c d e f g c b d a e g f 例如 : a a b b c c d d e e f fg a b c d e f g ^ ^ ^ ^ ^ ^ ^ ^ 先序序列中序序列 void CrtBT(BiTreeamp。 T, char pre[], char ino[], int ps, int is, int n ) { // 已知 pre[ps..ps+n1]為二叉樹(shù)的先序序列 , // ins[is..is+n1]為二叉樹(shù)的中序序列 , //本算法由此兩個(gè)序列構(gòu)造二叉鏈表 if (n==0) T=NULL。 else { k=Search(ino, pre[ps])。//在中序序列中查詢 if (k== 1) T=NULL。 else { } } } … … T=(BiTNode*)malloc(sizeof(BiTNode))。 Tdata = pre[ps]。 if (k==is) TLchild = NULL。 else CrtBT(TLchild, pre[], ino[], ps+1, is, kis )。 if (k==is+n1) TRchild = NULL。 else CrtBT(TRchild, pre[], ino[], ps+1+(kis), k+1, n(kis)1 )。 線索二叉樹(shù) ? 何謂線索二叉樹(shù)？ ? 線索鏈表的遍歷算法 ? 如何建立線索鏈表？ 遍歷二叉樹(shù)的結(jié)果是， 求得結(jié)點(diǎn)的一個(gè)線性序列。 A B C D E F G H K 例如 : 先序序列 : A B C D E F G H K 中序序列 : B D C A H G K F E 后序序列 : D C B H K G F E A 一 . 何謂線索二叉樹(shù)？ 指向該線性序列中的“前驅(qū)”和 “后繼” 的 指針 ，稱作“ 線索 ” 與其相應(yīng)的二叉樹(shù)，稱作 “ 線索二叉樹(shù) ” 包含 “線索” 的存儲(chǔ)結(jié)構(gòu)，稱作 “ 線索鏈表 ” A B C D E F G H K ^ D ^ C ^ ^ B E ^ 對(duì) 線索鏈表 中結(jié)點(diǎn)的約定： 在二叉鏈表的結(jié)點(diǎn)中 增加兩個(gè)標(biāo)志域 ， 并作如下規(guī)定： 若該結(jié)點(diǎn)的左子樹(shù)不空， 則 Lchild域的指針指向其左子樹(shù)， 且左標(biāo)志域的值為“ 指針 Link”； 否則， Lchild域的指針指向其“前驅(qū)”， 且左標(biāo)志的值為“ 線索 Thread” 。 若該結(jié)點(diǎn)的右子樹(shù)不空， 則 rchild域的指針指向其右子樹(shù)， 且右標(biāo)志域的值為 “ 指針 Link”； 否則， rchild域的指針指向其“后繼”， 且右標(biāo)志的值為“ 線索 Thread”。 如此定義的二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)稱作“ 線索鏈表 ” typedef struct BiThrNod { TElemType data。 struct BiThrNode *lchild,*rc
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1