【文章內(nèi)容簡介】 虛擬實現(xiàn)： typedef 用戶數(shù)據(jù)類型 elemtype。 //定義數(shù)據(jù)元素類型 struct bitree { elemtype data 。 //結點數(shù)據(jù)類型 bitree *parent， *lson, *rson。 //定義左、右孩子為指針型 } 167。 .2 二叉樹的鏈式存儲結構及虛擬實現(xiàn) 167。 二叉樹的存儲結構及操作的虛擬實現(xiàn) a b c d e f g 舉例： a b ^ c d e f g ^ ^ ^ ^ ^ ^ ^ ^ 167。 .3 二叉樹鏈式存儲結構下操作的虛擬實現(xiàn) （二叉鏈式存儲結構） 167。 二叉樹的存儲結構及操作的虛擬實現(xiàn) 一、遍歷操作 遍歷 ( Traversal )： 把二叉樹中的結點訪問且僅訪問一次， 又稱為掃描。 遍歷方式 ： 由于元素之間的關系復雜了，按什么樣的順序 訪問數(shù)據(jù)元素？ 廣度優(yōu)先遍歷 深度優(yōu)先遍歷 廣度優(yōu)先遍歷 ： 又稱為層次遍歷，從第 1層開始，逐層訪問 二叉樹的元素，每一層從左向右。 167。 二叉樹的存儲結構及操作的虛擬實現(xiàn) 167。 .3 二叉樹鏈式存儲結構下操作的虛擬實現(xiàn) （二叉鏈式存儲結構） a b c d e f g a a b c b c d e d e f g f g 167。 二叉樹的存儲結構及操作的虛擬實現(xiàn) 167。 .3 二叉樹鏈式存儲結構下操作的虛擬實現(xiàn) （二叉鏈式存儲結構） 算法： void lorder(t:bitreptr)。 { Iniqueue(Q)。 //隊列 初始化 if(t!=NULL) Enqueue(Q,t)。 //樹 根入隊 while (!Empty(Q)) // 當 隊列不空時，重復 { Dlqueue(Q,p)。 //出 隊一個元素 visit(pdata)。 if(p lchild!=NULL) Enqueue(Q,plchild)。 if (prchild!=NULL) Enqueue(Q,prchild)。 } } 要實現(xiàn)分層輸出，如何處理？ 167。 二叉樹的存儲結構及操作的虛擬實現(xiàn) 167。 .3 二叉樹鏈式存儲結構下操作的虛擬實現(xiàn) （二叉鏈式存儲結構） 隊列 1 隊列 2 當前層入隊列 1，出隊時，其左、右兒子入隊列 2， 當隊列 1為空，則當前層結束，其下層在隊列 2中， 隊列 2變?yōu)楫斍皩樱? 自己寫出算法！ 上次課內(nèi)容回顧 二叉樹的定義：遞歸、形態(tài) 二叉樹的性質： 滿二叉樹、完全二叉樹 二叉樹的存儲結構：方式、特點 順序存儲、二叉鏈式、三叉鏈式 二叉樹的操作的虛擬實現(xiàn)（二叉鏈式存儲結構） 遍歷：廣度方式 167。 二叉樹的存儲結構及操作的虛擬實現(xiàn) 167。 .3 二叉樹鏈式存儲結構下操作的虛擬實現(xiàn) （二叉鏈式存儲結構） 深度優(yōu)先遍歷 ： 基本思想是： 按某種原則訪問一個元素，由于它與多個元素 有關系（ 1個前趨、 2個后繼），按同樣原則選 擇一個元素繼續(xù)訪問。 注意與廣度遍歷的區(qū)別！ 假設一棵樹表示為根（ D）、 左子樹（ L）、 右子樹（ R） 則，它們的順序關系有 3！ =6種： DLR DRL LDR RDL LRD RLD 如果規(guī)定先左后右，則剩下 3種。 L D R 167。 二叉樹的存儲結構及操作的虛擬實現(xiàn) 167。 .3 二叉樹鏈式存儲結構下操作的虛擬實現(xiàn) （二叉鏈式存儲結構） 前序遍歷（ DLR）： 訪問根； 前序遍歷左子樹； 前序遍歷右子樹； 中序遍歷（ LDR）： 中序遍歷左子樹； 訪問根； 中序遍歷右子樹； 后序遍歷（ LRD）： 后序遍歷左子樹； 后序遍歷右子樹； 訪問根； Preorder Traversal Inorder Traversal Postorder Traversal 遍歷序列：按某種方式遍歷二叉樹的元素，得到的元素序列 167。 二叉樹的存儲結構及操作的虛擬實現(xiàn) 167。 .3 二叉樹鏈式存儲結構下操作的虛擬實現(xiàn) （二叉鏈式存儲結構） a b c d e f g 前序遍歷序列： 1 a 2 b 3 d 4 c 5 e 6 f 7 g 中序遍歷序列： d b a f e g c 后序遍歷序列： d b f g e c a 167。 二叉樹的存儲結構及操作的虛擬實現(xiàn) 167。 .3 二叉樹鏈式存儲結構下操作的虛擬實現(xiàn) （二叉鏈式存儲結構） 遍歷序列的特點： 根結點 左子樹的前序遍歷 右子樹的前序遍歷 根結點 左子樹的中序遍歷 右子樹的中序遍歷 根結點 左子樹的后序遍歷 右子樹的后序遍歷 167。 二叉樹的存儲結構及操作的虛擬實現(xiàn) 167。 .3 二叉樹鏈式存儲結構下操作的虛擬實現(xiàn) （二叉鏈式存儲結構） 前序遍 歷算法： void preorder(bitree *root) { bitree *p。 p=root。 if(p!=NULL) {coutpdata“ ”。 preorder(plchild)。 preorder (prchild)。 } } 訪問到該元素！ 遞歸前序遍歷左子樹 遞歸前序遍歷右子樹 167。 二叉樹的存儲結構及操作的虛擬實現(xiàn) 167。 .3 二叉樹鏈式存儲結構下操作的虛擬實現(xiàn) （二叉鏈式存儲結構） 中序遍 歷算法： void inorder(biteee *root) { bitree *p。 p=root。 if (p!=NULL) { inorder(plchild)。 coutpdata“ ”。 inorder(prchild)。 } } 訪問到該元素！ 遞歸中序遍歷左子樹 遞歸中序遍歷右子樹 167。 二叉樹的存儲結構及操作的虛擬實現(xiàn) 167。 .3 二叉樹鏈式存儲結構下操作的虛擬實現(xiàn) （二叉鏈式存儲結構） 后序遍 歷算法： void postorder( bitree *root) { bitree *p。 p=root。 if (p!=NULL) { postorder (plchild)。 postorder (prchild)。 coutpdata“ ”。 } } 訪問到該元素！ 遞歸后序遍歷左子樹 遞歸后序遍歷右子樹 167。 二叉樹的存儲結構及操作的虛擬實現(xiàn) 167。 .3 二叉樹鏈式存儲結構下操作的虛擬實現(xiàn) （二叉鏈式存儲結構） 算術表達式的二叉樹表示及前、后綴形式 （ 1）算術表達式表示為二叉樹： 若表達式為常數(shù)、簡單變量，則二叉樹只有根，數(shù)據(jù)元素為 常數(shù)或變量； 否則，表達式可以寫作： 表達式 =表達式 1 算符 表達式 2 于是，二叉樹的根是 算符 ，根的左子樹由 表達式 1形成， 根的右子樹由 表達式 2 形成；（遞歸的！?。? 167。 二叉樹的存儲結構及操作的虛擬實現(xiàn) 167。 .3 二叉樹鏈式存儲結構下操作的虛擬實現(xiàn) （二叉鏈式存儲結構） 例如有算術表達式 ： a+b*(cd)e/f e/f a + b*(cd) a b*(cd) + b * cd c d e / f c d e b * a + / f 表達式的二叉樹形式是否唯一？ 167。 二叉樹的存儲結構及操作的虛擬實現(xiàn) 167。 .3 二叉樹鏈式存儲結構下操作的虛擬實現(xiàn) （二叉鏈式存儲結構） （ 2）算術表達式的前綴、后綴形式： 前序遍歷表達式的二叉樹，得到的前序遍歷序 列是表達式的前綴形式。 后序遍歷表達式的二叉樹，得到的后序遍歷序 列是表達式的后綴形式。 167。 二叉樹的存儲結構及操作的虛擬實現(xiàn) 167。 .3 二叉樹鏈式存儲結構下操作的虛擬實現(xiàn) （二叉鏈式存儲結構） c d e b * a + / f 例： a+b*(cd)e/f 前綴： +a*bcd/ef 后綴： abcd*+ef/ 表達式的中綴形式如何得到 ?中序遍歷？ 167。 二叉樹的存儲結構及操作的虛擬實現(xiàn) 167。 .3 二叉樹鏈式存儲結構下操作的虛擬實現(xiàn) （二叉鏈式存儲結構） 167。 二叉樹的存儲結構及操作的虛擬實現(xiàn) 167。 .3 二叉樹鏈式存儲結構下操作的虛擬實現(xiàn) （二叉鏈式存儲結構） 二、二叉樹的插入與刪除操作 在二叉樹中進行插入、刪除操作，若簡單的描述為“在二叉 樹的某個位置插入（刪除）一個結點”，是無法進行操作的因為 ，它涉及前驅（ 1個）和后繼（ 2個）的調整，不象線性表那么簡 單！ 除了知道在哪個位置插入、刪除外，一般遵循兩個原則： （ 1）、插入、刪除后如何調整 ——對一般二叉樹 （ 2）、達到某種性質（或保持某種性質） ——對特殊二叉樹 167。 二叉樹的存儲結構及操作的虛擬實現(xiàn) 167。 .3 二叉樹鏈式存儲結構下操作的虛擬實現(xiàn) （二叉鏈式存儲結構） 插入： 插入一個數(shù)據(jù)元素 Y， 使之成為數(shù)據(jù)元素 X的左兒子， 而原來 X的左兒子成為 Y的左兒子。 方法：找到數(shù)據(jù)元素 X， 可采用廣度、深度遍歷均可； 生成插入結點； 插入并調整； ... ... ( r 指向數(shù)據(jù)元素 X結點 ) New(p)。 pdata=y。 plchild=rlchild。 rlchild=p。 X Y 167。 二叉樹的存儲結構及操作的虛擬實現(xiàn) 167。 .3 二叉樹鏈式存儲結構下操作的虛擬實現(xiàn) （二叉鏈式存儲結構） 刪除： 刪除數(shù)據(jù)元素為 X的結點，使其左兒子成為其雙親的 兒子， X原來的右兒子成為 X原來左兒子的最右下兒 子。 方法：找到數(shù)據(jù)元素 X， 可采用廣度、深度遍歷均可（ 由于 涉及元素 X的雙親，所以要得到指向雙親結點的指針）； 得到指向 X左、右兒子的指針； 刪除元素 X結點； 按置好左、右兒子 167。 二叉樹的存儲結構及操作的虛擬實現(xiàn) 167。 .3 二叉樹鏈式存儲結構下