【文章內(nèi)容簡(jiǎn)介】 *TNODE。 void Create_t(TNODE amp。bt) { char ch。 cinch。 if(ch==39。39。) bt=NULL。 else { bt=new struct tnode。 btdata=ch。 Create_t(btlchild)。 Create_t(btrchild)。 } } A B C D E F ABC..DE..F... 下一頁(yè) 上一頁(yè) 停止放映 第 41 頁(yè) 建立二叉樹(shù) (續(xù)） void preOrder_t (struct tnode *root) { if ( root != NULL ) {coutrootdata 。 preOrder_t(rootlchild)。 preOrder_t(rootrchild)。 } } main() { TNODE root。 Create_t(root)。 preOrder_t(root)。 } 下一頁(yè) 上一頁(yè) 停止放映 第 42 頁(yè) 樹(shù)的存儲(chǔ)結(jié)構(gòu) ? 雙親表示法 ? 孩子表示法 ? 孩子兄弟表示法 下一頁(yè) 上一頁(yè) 停止放映 第 43 頁(yè) 雙親表示法 1 2 3 4 5 6 7 8 9 結(jié)點(diǎn)序號(hào) 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 0 1 1 2 2 3 5 5 5 方法特點(diǎn)： 找根容易，找子結(jié)點(diǎn)難， 要遍歷整個(gè)數(shù)組。 下一頁(yè) 上一頁(yè) 停止放映 第 44 頁(yè) 雙親表示法 C++描述 用數(shù)組存儲(chǔ)樹(shù)的結(jié)點(diǎn)信息 ， 在每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指示器指示其雙親結(jié)點(diǎn)在數(shù)組中的位置 ,也稱為數(shù)組實(shí)現(xiàn)方法 。 結(jié)構(gòu)描述： define MAXSIZE 100 typedef struct PTNode{ TElemType data； int parent ； } PTNode； typedef struc { PTNode nodes[MAXSIZE]； int n； } Ptree； 下一頁(yè) 上一頁(yè) 停止放映 第 45 頁(yè) 孩子表示法 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 2 3 ^ 4 5 ^ 6 ^ ^ ^ ^ ^ ^ 7 8 9 ^ 方法特點(diǎn) : 便于實(shí)現(xiàn)對(duì)孩子的操 作 ,卻不便于對(duì)父親 的操作 . 下一頁(yè) 上一頁(yè) 停止放映 第 46 頁(yè) 孩子表示法 C++描述 ? 把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來(lái)，組成一個(gè)線性表，且以單鏈表作為存儲(chǔ)結(jié)構(gòu)，則 n個(gè)結(jié)點(diǎn)有 n個(gè)孩子鏈表，也稱為鏈表實(shí)現(xiàn)方式 。 ? 結(jié)構(gòu)描述為： typedef struct CTNode typedef struct { int child； { CTBox nodes[MAXSIZE]； struct CTNode *next： int n； } *Childptr； } Ctree； typedef struct { TElemType data； Childptr firstchild； } CTBox； 下一頁(yè) 上一頁(yè) 停止放映 第 47 頁(yè) 孩子兄弟表示法 1 2 3 4 5 6 7 8 9 1 2 ^ 3 7 4 5 6 8 9 ^ ^ ^ ^ ^ ^ ^ ^ 方法特點(diǎn) : 這種存儲(chǔ)結(jié)構(gòu)便于實(shí)現(xiàn)各種樹(shù)的操作 . ^ 下一頁(yè) 上一頁(yè) 停止放映 第 48 頁(yè) 孩子兄弟表示法 C++描述 ? 二叉鏈表實(shí)現(xiàn)方式 （ 孩子兄弟表示法 ） 以二叉鏈表作為樹(shù)的存儲(chǔ)結(jié)構(gòu) 。 鏈表中結(jié)點(diǎn)的兩個(gè)鏈域分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn) 。 結(jié)構(gòu)描述為： typedef struct CSNode{ ElemType data； struct CSNode *firstchild ， *nextsibling； } CSNode， * CSTree； 下一頁(yè) 上一頁(yè) 停止放映 第 49 頁(yè) 表達(dá)式樹(shù)及應(yīng)用 ? 在計(jì)算機(jī)中對(duì)表達(dá)式進(jìn)行分析和計(jì)算是一項(xiàng)重要的任務(wù) 。 ? 舉例 ， 用二叉樹(shù)表示表達(dá)式： a + b * （ c d ） － ｅ ／ｆ 前序遍歷序列：－＋ａ＊ｂ－ｃｄ／ｅｆ 中序遍歷序列：ａ＋ｂ＊ｃ－ｄ－ｅ／ｆ 后序遍歷序列：ａｂｃｄ－＊＋ｅｆ／－ ? 分析： – 每個(gè)葉結(jié)點(diǎn)為運(yùn)算對(duì)象； – 每個(gè)非葉結(jié)點(diǎn)為運(yùn)算符； – 每個(gè)子樹(shù)對(duì)應(yīng)一個(gè)子表達(dá)式 。 ? 表達(dá)式處理一般采用后序法 ， 也稱 “ 逆波蘭 ” 法 。 ? 表達(dá)式處理規(guī)則： – 見(jiàn)運(yùn)算數(shù)入棧； – 見(jiàn)運(yùn)算符 ， 取兩個(gè)棧頂元素運(yùn)算后再壓棧； – 直到處理結(jié)束 。 － ＋ ／ － e f ＊b － c d a 下一頁(yè) 上一頁(yè) 停止放映 第 50 頁(yè) 樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換 ? 由于二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)比較簡(jiǎn)單 ， 處理起來(lái)也比較方便 ， 所以有時(shí)需要把復(fù)雜的樹(shù) ， 轉(zhuǎn)換為簡(jiǎn)單的二叉樹(shù)后再作處理 。 ? 樹(shù)轉(zhuǎn)換成二叉樹(shù) ? 森林轉(zhuǎn)換成二叉樹(shù) 下一頁(yè) 上一頁(yè) 停止放映 第 51 頁(yè) 樹(shù)轉(zhuǎn)換成二叉樹(shù) ? 操作算法： – 保留一個(gè)結(jié)點(diǎn)的最左子結(jié)點(diǎn)； – 抹掉其余兄弟結(jié)點(diǎn)與上級(jí)結(jié)點(diǎn)的連線； – 將兄弟結(jié)點(diǎn)連在一起； – 以根為軸 ， 順時(shí)針旋轉(zhuǎn)一個(gè)角度 。 ? 舉例： o o o o o o o o o o o o o o 加線 抹線 o o o o o o o 旋轉(zhuǎn) o o o o o o o 下一頁(yè) 上一頁(yè) 停止放映 第 52 頁(yè) 森林轉(zhuǎn)換成二叉樹(shù) ? 操作算法： – 將森林中每棵樹(shù)的樹(shù)根連接起來(lái)； – 將每棵樹(shù)轉(zhuǎn)換成對(duì)應(yīng)的二叉樹(shù)； – 以森林中第一棵樹(shù)的根為軸順時(shí)針旋轉(zhuǎn)一個(gè)角度 。 ? 舉例 o o o o o o o o o o 連線 o o o o o o o o o o 抹線 o o o o o o o o o o 旋轉(zhuǎn) o o o o o o o o o o 下一頁(yè) 上一頁(yè) 停止放映 第 53 頁(yè) 將二叉樹(shù)還原成樹(shù)事例 A B E C F D G A B E C F D G （ a）二叉樹(shù) （ b）加連線 A B E C F D G （ c）刪除與 右子的連線 A B E C F D G （ d）還原后的樹(shù) 下一頁(yè) 上一頁(yè) 停止放映 第 54 頁(yè) 將二叉樹(shù)還原成樹(shù) ? 將二叉樹(shù)還原成樹(shù)的操作步驟為： step1 把各結(jié)點(diǎn)的右子、都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用線連起來(lái)； step2 刪除原二叉樹(shù)中所有的雙親結(jié)點(diǎn)與右子結(jié)點(diǎn)的連線； step3 旋轉(zhuǎn)一定角度。 下一頁(yè) 上一頁(yè) 停止放映 第 55 頁(yè) 六、二叉排序樹(shù)的生成 對(duì)給定數(shù)列 {a1， a2， … ,an},根據(jù)二叉排序樹(shù)特性 ,逐個(gè)將結(jié)點(diǎn)插入到二叉排序中 。 具體操作步驟： step1 a1是根結(jié)點(diǎn)； step2 若 aiaj ,且 aj的左子為空 ,則將 ai插入到 aj的左子 。若 aj的左子非空 ,則繼續(xù)尋找合適的插入位置 。 若 ai?aj， 且 aj的右子為空 ， 則將 ai插入到 aj的右子；否則繼續(xù)沿右子樹(shù)尋找合適的插入位置； 插入 ai 插入到 aj的左子 ai〈 aj 插入到 aj的右子 ai ? aj step3 重復(fù) step2，直到所有結(jié)點(diǎn)插入完為止。 下一頁(yè) 上一頁(yè) 停止放映 第 56 頁(yè) 二叉排序樹(shù)算法 二叉排序樹(shù)結(jié)點(diǎn)結(jié)構(gòu)： struct tree { char info；