【正文】 個(gè)結(jié)點(diǎn)有兩個(gè)域，一個(gè)是 data域，用來存放數(shù)據(jù)元素，一個(gè)是 parent域，用來存放指示其父結(jié)點(diǎn)位置的指針。 ?這種存儲(chǔ)表示適合經(jīng)常需要尋找父結(jié)點(diǎn)的應(yīng)用。 EBAFDGC0123456ABCDEFG 1000113樹 雙 親 表 示 法d a t ap a r e n tData Structure— Ch5 Tree 2022/1/4 mayan 樹與森林 樹的存儲(chǔ)表示 ? 孩子表示法（子女鏈表表示法） ? 為樹中每個(gè)結(jié)點(diǎn)設(shè)置一個(gè)子女鏈表，并將這些結(jié)點(diǎn)的數(shù)據(jù)和對(duì)應(yīng)子女鏈表的頭指針放在一個(gè)向量中，就構(gòu)成了子女鏈表表示。 ? 這種存儲(chǔ)表示適合需要頻繁尋找子女的應(yīng)用。無序樹情形鏈表中各結(jié)點(diǎn)順序任意，有序樹必須自左向右鏈接各個(gè)子女結(jié)點(diǎn)。 EBAFDGC樹ABCDEFG∧∧∧∧12 3 ∧45 ∧6 ∧0123456d a t a f i r s t孩 子 表 示 法Data Structure— Ch5 Tree 2022/1/4 mayan 樹與森林 樹的存儲(chǔ)表示 ? 孩子兄弟表示法（子女 兄弟鏈表表示法） ? 子女 兄弟鏈表表示法也稱為樹的二叉樹表示。他的每個(gè)結(jié)點(diǎn)的度為 2 ，是最節(jié)省存儲(chǔ)空間的樹的存儲(chǔ)表示。每個(gè)結(jié)點(diǎn)由三個(gè)域組成： ? firstChild 指向該結(jié)點(diǎn)的第一個(gè)子女結(jié)點(diǎn)。無序樹時(shí)，可任意指定一個(gè)結(jié)點(diǎn)為第一個(gè)子女。 ? nextSibling 指向該結(jié)點(diǎn)的下一個(gè)兄弟。任一結(jié)點(diǎn)在存儲(chǔ)時(shí)總是有順序的。 d a t a f i r s t C h i l d n e x t S i b l i n gData Structure— Ch5 Tree 2022/1/4 mayan 樹與森林 樹的存儲(chǔ)表示 ? 孩子兄弟表示法（子女 兄弟鏈表表示法） A∧BE∧F∧ ∧C∧D∧G∧ ∧子 女 兄 弟 鏈 表 表 示 法EBAFDGC樹Data Structure— Ch5 Tree 2022/1/4 mayan 樹與森林 樹的子女 兄弟表示的類定義 template class T struct TreeNode { //樹的結(jié)點(diǎn)類 T data。 //結(jié)點(diǎn)數(shù)據(jù) TreeNodeT *firstChild, *nextSibling。 //子女及兄弟指針 TreeNode (T value = 0, TreeNodeT *fc = NULL, TreeNodeT *ns = NULL) //構(gòu)造函數(shù) : data (value), firstChild (fc), nextSibling (ns) { } }。 Data Structure— Ch5 Tree 2022/1/4 mayan 樹與森林 樹的子女 兄弟表示的類定義 template class T class Tree { //樹類 private: TreeNodeT *root, *current。 //根指針及當(dāng)前指針 int Find (TreeNodeT *p, T value)。 //在以 p為根的樹中搜索 value void RemovesubTree (TreeNodeT *p)。 //刪除以 p為根的子樹 bool FindParent (TreeNodeT *t, TreeNodeT *p)。 public: Data Structure— Ch5 Tree 2022/1/4 mayan 樹與森林 樹的子女 兄弟表示的類定義 Tree () { root = current = NULL。 } //構(gòu)造函數(shù) bool Root ()。 //置根結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn) bool IsEmpty () { return root == NULL。 } bool FirstChild ()。 //將當(dāng)前結(jié)點(diǎn)的第一個(gè)子女置為當(dāng)前結(jié)點(diǎn) bool NextSibling ()。 //將當(dāng)前結(jié)點(diǎn)的下一個(gè)兄弟置為當(dāng)前結(jié)點(diǎn) bool Parent ()。//將當(dāng)前結(jié)點(diǎn)的雙親置為當(dāng)前結(jié)點(diǎn) bool Find (T target)。 //搜索含 target的結(jié)點(diǎn) , 使之成為當(dāng)前結(jié)點(diǎn) …… // 樹的其他公共操作 }。 Data Structure— Ch5 Tree 2022/1/4 mayan 樹與森林 子女 兄弟鏈表常用操作的實(shí)現(xiàn) //讓樹的根結(jié)點(diǎn)成為樹的當(dāng)前結(jié)點(diǎn) template class T bool TreeT::Root () { if (root == NULL) {current = NULL。 return false。 } else {current = root。 return true。 } } Data Structure— Ch5 Tree 2022/1/4 mayan 樹與森林 子女 兄弟鏈表常用操作的實(shí)現(xiàn) //置當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn) template class T bool TreeT::Parent () { TreeNodeT *p = current。 if (current == NULL || current == root) { current = NULL。 return false。 }//空樹或根無雙親 return FindParent (root, p)。 //從根開始找 *p的雙親結(jié)點(diǎn) } Data Structure— Ch5 Tree 2022/1/4 mayan 樹與森林 子女 兄弟鏈表常用操作的實(shí)現(xiàn) //在根為 *t的樹中找 *p的雙親 , 并置為當(dāng)前結(jié)點(diǎn) template class T bool TreeT:: FindParent (TreeNodeT *t, TreeNodeT *p) { TreeNodeT *q = tfirstChild。 //*q是 *t長子 bool succ。 Data Structure— Ch5 Tree 2022/1/4 mayan 樹與森林 子女 兄弟鏈表常用操作的實(shí)現(xiàn) while (q != NULL amp。amp。 q != p) {//掃描兄弟鏈 if ((succ = FindParent (q, p)) == true) return succ。 //遞歸搜索以 *q為根的子樹 q = qnextSibling。 } if (q != NULL amp。amp。 q == p) { current = t。 return true。 } else { current = NULL。 return false。 } //未找到 } Data Structure— Ch5 Tree 2022/1/4 mayan 樹與森林 子女 兄弟鏈表常用操作的實(shí)現(xiàn) //在樹中找當(dāng)前結(jié)點(diǎn)的長子 , 并置為當(dāng)前結(jié)點(diǎn) template class T bool TreeT::FirstChild () { if (current amp。amp。 currentfirstChild ) { current = currentfirstChild。 return true。 } current = NULL。 return false。 } Data Structure— Ch5 Tree 2022/1/4 mayan 樹與森林 子女 兄弟鏈表常用操作的實(shí)現(xiàn) //在樹中找當(dāng)前結(jié)點(diǎn)的兄弟 , 并置為當(dāng)前結(jié)點(diǎn) template class T bool TreeT::NextSibling () { if (current amp。amp。 currentnextSibling) {current = currentnextSibling。 return true。 } current = NULL。 return false。 } Data Structure— Ch5 Tree 2022/1/4 mayan 樹與森林 子女 兄弟鏈表常用操作的實(shí)現(xiàn) template class T bool TreeT::Find (T target){ if(IsEmpty()) return false。 return Find(root,target)。 } template class T bool TreeT::Find (TreeNodeT *p,T value ){ Data Structure— Ch5 Tree 2022/1/4 mayan 樹與森林 子女 兄弟鏈表常用操作的實(shí)現(xiàn) bool result=false。 if(pdata==value){result=true。current=p。} else{ TreeNodeT *q=pfirstChild。 while(q!=NULLamp。amp。!(result=Find(q,value))) q=qnextSibling。 } return result。 } Data Structure— Ch5 Tree 2022/1/4 mayan 樹與森林 森林與二叉樹的轉(zhuǎn)換 ? 將一般樹化為二叉樹表示就是用樹的子女 兄弟表示來存儲(chǔ)樹的結(jié)構(gòu)。 ? 森林與二叉樹表示的轉(zhuǎn)換可以借助樹的二叉樹表示來實(shí)現(xiàn)。 Data Structure— Ch5 Tree 2022/1/4 mayan 樹與森林 森林與二叉樹的轉(zhuǎn)換 ? 森林轉(zhuǎn)化成二叉樹的規(guī)則 ? 若 F 為空 ， 即 n = 0， 則對(duì)應(yīng)的二叉樹 B 為空樹 。 ? 若 F 不空 ， 則 i. 二叉樹 B 的根是 F 第一棵樹 T1 的根； ii. 其左子樹為 B (T11, T12, … , T1m)， 其中 ， T11, T12, … , T1m 是 T1 的根的子樹； iii. 其右子樹為 B (T2, T3, … , Tn)， 其中 ， T2, T3, … , Tn 是除 T1 外其它樹構(gòu)成的森林 。 Data Structure— Ch5 Tree 2022/1/4 mayan 樹與森林 森林與二叉樹的轉(zhuǎn)換 ? 二叉樹轉(zhuǎn)換為森林的規(guī)則 ? 如果 B 為空 ， 則對(duì)應(yīng)的森林 F 也為空 。 ? 如果 B 非空 ， 則 i. F 中第一棵樹 T1 的根為 B 的根； ii. T1 的根的子樹森林 { T11, T12, … , T1m } 是由 B 的根的左子樹 LB 轉(zhuǎn)換而來； iii. F 中除了 T1 之外其余的樹組成的森林 { T2, T3, … , Tn } 是由 B 的根的右子樹 RB 轉(zhuǎn)換而成的森林 。 Data Structure— Ch5 Tree 2022/1/4 mayan 樹與森林 森林與二叉樹的轉(zhuǎn)換 IKHJEBA FD GC3 棵 樹 的 森 林IKHJEBA FDGC樹 的 二 叉 樹 表 示IKHJEBAFDGC森 林 的 二 叉 樹 表 示T1T2T3T1T2T3Data Structure— Ch5 Tree 2022/1/4 mayan 樹與森林 樹的遍歷 ? 深度優(yōu)先遍歷 ?先根次序遍歷：先訪問樹的根結(jié)點(diǎn)，然后先根遍歷根的每棵子樹。樹的先根遍歷結(jié)果與其對(duì)應(yīng)二叉樹表示的前序遍歷結(jié)果相同。樹的先根遍歷可以借助對(duì)應(yīng)二叉樹的前序遍歷算法實(shí)現(xiàn)。 ?后根次序遍歷：先依次后根遍歷每棵子樹，然后訪問根結(jié)點(diǎn)。樹的后根遍歷結(jié)果與其對(duì)應(yīng)二叉樹表示的中序遍歷結(jié)果相同。樹的后根遍歷可以借助對(duì)應(yīng)二叉樹的中序遍歷算法實(shí)現(xiàn)。 Data Structure— Ch5 Tree 2022/1/4 mayan 樹與森林 樹的遍歷 ? 樹的先根次序遍歷的遞歸算法 template class T void TreeT::PreOrder (ostreamamp。 out, TreeNodeT *p ) { //以 p為根 ,