數(shù)據(jù)結(jié)構(c語言版)樹、二叉樹詳細舉例介紹(編輯修改稿)

　

【文章內(nèi)容簡介】 r = CopyTree(Trchild)。//復制右子樹 else newrptr = NULL。 newT=GetTreeNode(Tdata,newlptr,newrptr)。 return newT。 } 問題 ： 若用先序框架，應如何修改？ A B C D E F G H K ^ D ^ C ^ ^ B ^ H ^ ^ K ^ G F ^ E ^ A 例如 :下列二叉樹的復制過程如下 : newT 4. 建立二叉樹的 存儲結(jié)構 不同的定義方法相應有不同的存儲結(jié)構的建立算法 以字符串的形式 根 左子樹 右子樹 定義一棵二叉樹 例如 : A B C D 以空白字符“ ”表示 A(B( ,C( , )),D( , )) 空樹 只含一個根結(jié)點的二叉樹 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é)點 CreateBiTree(Tlchild)。 // 構造左子樹 CreateBiTree(Trchild)。 // 構造右子樹 } return OK。 } A B C D B C D 上頁算法執(zhí)行過程舉例如下 : A T B C D ^ ^ ^ ^ ^ 按給定的表達式建相應二叉樹 ? 由先綴表示式建樹 例如：已知表達式的先綴表示式 + a b c / d e ? 由原表達式建樹 例如：已知表達式 (a+b) c – d/e 對應先綴表達式 + a b c / d e的二叉樹 a b c d e + / 特點 ： 操作數(shù) 為葉子結(jié)點， 運算符 為分支結(jié)點 scanf(amp。ch)。 if ( In(ch, 字母集 )) 建葉子結(jié)點 。 else { 建根結(jié)點 。 遞歸建左子樹 。 遞歸建右子樹 。 } 由先綴表示式建樹的算法的基本操作： a+b (a+b) c – d/e a+b c 分析表達式和二叉樹的關系 : a b + a b c + a b c + (a+b) c a b c d e + / 基本操作 : scanf(amp。ch)。 if (In(ch, 字母集 )) { 建葉子結(jié)點 。 暫存 。 } else if (In(ch, 運算符集 )) { 和前一個運算符比較優(yōu)先數(shù) 。 若當前的優(yōu)先數(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é)點并入棧 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)。 //建二叉樹并入棧 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é)點的算法為： void CrtNode(BiTreeamp。 T,char ch) { T=(BiTNode*)malloc(sizeof(BiTNode))。 Tdata = char。 Tlchild = Trchild = NULL。 Push( PTR, T )。 } 建子樹的算法為： 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)。 } 僅知二叉樹的先序序列“ abcdefg” 不能唯一確定一棵二叉樹， 由二叉樹的先序和中序序列建樹 如果同時已知二叉樹的中序序列“ cbdaegf”, 則會如何？ 二叉樹的先序序列 二叉樹的中序序列 左子樹 左子樹 右子樹 右子樹 根 根 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]為二叉樹的先序序列 , // ins[is..is+n1]為二叉樹的中序序列 , //本算法由此兩個序列構造二叉鏈表 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 )。 線索二叉樹 ? 何謂線索二叉樹？ ? 線索鏈表的遍歷算法 ? 如何建立線索鏈表？ 遍歷二叉樹的結(jié)果是， 求得結(jié)點的一個線性序列。 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 一 . 何謂線索二叉樹？ 指向該線性序列中的“前驅(qū)”和 “后繼” 的 指針 ，稱作“ 線索 ” 與其相應的二叉樹，稱作 “ 線索二叉樹 ” 包含 “線索” 的存儲結(jié)構，稱作 “ 線索鏈表 ” A B C D E F G H K ^ D ^ C ^ ^ B E ^ 對 線索鏈表 中結(jié)點的約定： 在二叉鏈表的結(jié)點中 增加兩個標志域 ， 并作如下規(guī)定： 若該結(jié)點的左子樹不空， 則 Lchild域的指針指向其左子樹， 且左標志域的值為“ 指針 Link”； 否則， Lchild域的指針指向其“前驅(qū)”， 且左標志的值為“ 線索 Thread” 。 若該結(jié)點的右子樹不空， 則 rchild域的指針指向其右子樹， 且右標志域的值為 “ 指針 Link”； 否則， rchild域的指針指向其“后繼”， 且右標志的值為“ 線索 Thread”。 如此定義的二叉樹的存儲結(jié)構稱作“ 線索鏈表 ” typedef struct BiThrNod { TElemType data。 struct BiThrNode *lchild,*rc