數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版) 第6章 樹

《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版) 第6章 樹》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版) 第6章 樹（63頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第6章 樹1樹的邏輯結(jié)構(gòu) 核心關(guān)系：層次關(guān)系。1.1 通俗定義樹形表示法廣義表表示法A(B(E,F,G),C(H),D(I,J)樹是n(n0)個(gè)結(jié)點(diǎn)的有限集，在任意一棵樹中：1 有且只有一個(gè)特定的根(root)結(jié)點(diǎn)；2 當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為m(m0)個(gè)互不相交的有限子集T1,T2.Tm，每個(gè)子集是一棵樹，稱為子樹。1.2 形式定義 D=ai | aiElemSet，i=1,n二元關(guān)系S的定義： 當(dāng)n=1時(shí)，S=；當(dāng)n1時(shí)：1根的特殊地位唯一無(wú)前驅(qū)的元素：根結(jié)點(diǎn)(root)；2結(jié)點(diǎn)的劃分可將D-root劃分成m(m0)個(gè)互不相交的子集D1,D2,Dm，對(duì)任意子集Di，唯一存在xiDi，有S；

2、3關(guān)系的劃分對(duì)應(yīng)D-root的劃分,可將S-,唯一劃分成互不相交的子集S1,S2,.,Sm，對(duì)于任意i, Si是Di上的二元關(guān)系。(Di,Si)是一棵樹，稱為根root的子樹。示例：D=A,B,C,D,E,F,G,H,I,J,KS=, , , , root: AD-A可分為：D1=B,E,F,GD2=C,HD3=D,I,JS-,可分為：S1: ,S2: S3: ,1.3 概念1.3.1 若干角色雙親、孩子一個(gè)序偶中的直接前驅(qū)、直接后繼。祖先、子孫一個(gè)序偶集合中的前驅(qū)、后繼。兄弟具有相同直接前驅(qū)的數(shù)據(jù)元素。堂兄弟具有相同前驅(qū)的數(shù)據(jù)元素。1.3.2 與“度”相關(guān)的概念結(jié)點(diǎn)的度結(jié)點(diǎn)擁有的子樹數(shù)。葉子

3、結(jié)點(diǎn)度為0的結(jié)點(diǎn)。分支結(jié)點(diǎn)度不為0的結(jié)點(diǎn)。樹的度樹內(nèi)所有結(jié)點(diǎn)的度的最大值。1.3.3 與“深度”相關(guān)的概念結(jié)點(diǎn)深度根結(jié)點(diǎn)的深度為1若某結(jié)點(diǎn)深度為i, 則其子結(jié)點(diǎn)深度為i+1樹的深度 樹中結(jié)點(diǎn)的最大深度?；?空樹深度為0； 非空樹深度等于子樹深度的最大值加1。1.3.4 其他概念有序樹、無(wú)序樹左右結(jié)點(diǎn)是否等價(jià)森林m棵互不相交的樹的集合。m=0：空集；m=1：樹 1.4 基本操作 構(gòu)造、析構(gòu)、遍歷、查找、插入、刪除、2 二叉樹的邏輯結(jié)構(gòu)2.1 定義 結(jié)構(gòu)簡(jiǎn)化、概念強(qiáng)化：左子樹、右子樹。樹形表示法廣義表表示法A(B(D),C(F(,E),G) 2.2 二叉樹的形態(tài)具有n個(gè)結(jié)點(diǎn)的不同形態(tài)的二叉樹有多少

4、顆？ 二叉樹相似：二者都為空；或它們的左右子樹相似。例：n個(gè)結(jié)點(diǎn)的相似樹的個(gè)數(shù)template int BinTree:GetTreeCount(int n) int left,count=0; if(n=0 | n=1) return(1); for(left=n-1; left=0; left-) count += GetTreeCount(left) * GetTreeCount(n-1-left); return(count);2.3 性質(zhì)2.3.1 性質(zhì)1若某二叉樹的葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。試題例：若一棵m叉樹中度為i的結(jié)點(diǎn)有Ni個(gè)，則該樹的葉結(jié)點(diǎn)有

5、 (N1+2N2+mNm+1)-(N1+N2+Nm) 個(gè)。2.3.2 性質(zhì)2二叉樹的第i層上的結(jié)點(diǎn)數(shù)最多為2i-1。2.3.3 性質(zhì)3深度為k的二叉樹中結(jié)點(diǎn)總數(shù)最多為2k-1。滿二叉樹完全二叉樹深度為k，共有2k-1個(gè)結(jié)點(diǎn)。深度為k，前k-1層是滿二叉樹，第k層的結(jié)點(diǎn)從左至右依次排列。2.3.4 性質(zhì)4具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為int(log2n)+1。2.3.5 性質(zhì)5有n個(gè)結(jié)點(diǎn)的完全二叉樹，結(jié)點(diǎn)從0順序標(biāo)號(hào)，則：1、若i0，i的雙親結(jié)點(diǎn)是(i-1)/2。2、若2i+1n，i的左孩子是2i+1；否則，i無(wú)左孩子。3、若2i+2n，i的右孩子是2i+2；否則，i無(wú)右孩子。3 二叉樹的存儲(chǔ)

6、結(jié)構(gòu)3.1 順序結(jié)構(gòu)3.1.1 存儲(chǔ)規(guī)則依照滿二叉樹的結(jié)點(diǎn)順序，存放各個(gè)結(jié)點(diǎn)。存儲(chǔ)位置暗藏樹的關(guān)系。試題例：將68個(gè)結(jié)點(diǎn)的完全二叉樹，按順序存儲(chǔ)結(jié)構(gòu)存于數(shù)組A0100中，葉子結(jié)點(diǎn)的最小編號(hào)是 。 A、32B、33C、34D、35試題例：具有101個(gè)結(jié)點(diǎn)的完全二叉樹，度為1的結(jié)點(diǎn)有 個(gè)。3.1.2 性能分析滿/完全二叉樹：存儲(chǔ)效率最高，插入、刪除方便。非完全二叉樹的處理方法：非完全二叉樹修補(bǔ)結(jié)構(gòu)不存在的結(jié)點(diǎn)，用特殊符號(hào)標(biāo)識(shí)。退化的二叉樹及其存儲(chǔ)效果：評(píng)價(jià)：空間浪費(fèi)大，不靈活。 3.2 鏈?zhǔn)浇Y(jié)構(gòu)3.2.1 二叉鏈表結(jié)構(gòu)Template struct BinTreeNode T data; BinT

7、reeNode *lchild, *rchild;template class BinTree BinTreeNode* m_Root;邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)空指針域有多少？3.2.2 三叉鏈表結(jié)構(gòu)Template struct BinTreeNode T data; BinTreeNode *parent; BinTreeNode *lchild; BinTreeNode *rchild;邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)3.2.3 三叉靜鏈表結(jié)構(gòu)Template struct BinTreeNode T data; int parent,lchild, rchild;template class BinTree

8、int m_Root; / 根結(jié)點(diǎn)的下標(biāo) BinTreeNode* m_Data; / 結(jié)點(diǎn)的存儲(chǔ)空間邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)第6章 樹專題：二叉樹存儲(chǔ)結(jié)構(gòu)的遐想一、結(jié)構(gòu)定義enum Tag LEFT,NOLEFT;Template struct BinTreeNode Tag type; T data; BinTreeNode *child, *right;若結(jié)點(diǎn)*p有左孩子，則p-type=LEFT;否則p-type=NOLEFT;若結(jié)點(diǎn)*p是根結(jié)點(diǎn)，則p-right=NULL;若結(jié)點(diǎn)*p是葉子結(jié)點(diǎn)，則p-child=NULL;若結(jié)點(diǎn)*p有且僅有一個(gè)子結(jié)點(diǎn)*q，則 p-child=q; q-rig

9、ht=p;若結(jié)點(diǎn)*p有左孩子*q，有右孩子*r，則 p-child=q; q-right=r; r-right=p;二、結(jié)構(gòu)示例二叉鏈表結(jié)構(gòu)三、基本操作求結(jié)點(diǎn)*p的左孩子*p_LeftChild。 if(p-type=LEFT) p_LeftChild=p-child;求結(jié)點(diǎn)*p的右孩子*p_RightChild。 if(p-type=LEFT & p-child-right!=p) p_RightChild=p-child-right; 或 if(p-type=NOLEFT & p-child!=NULL) p_RightChild=p-child;當(dāng)p-right!=NULL時(shí)，求結(jié)點(diǎn)*p

10、的父結(jié)點(diǎn)*p_Parent。 設(shè)q=p-right if(q-child=p) p_Parent=q; / *p是獨(dú)左/右子 if(q-child=NULL) p_Parent=q-right; / *p和*q是兄弟 if(q-child!=NULL & q-child-right=p) p_Parent=q; /q-child指向左孩子，p指向右孩子 if(q-right=NULL) p_Parent=q; / *p_Parent是根 if(q-right!=NULL & q-right-child=p) p_Parent=q-right; / *p是左孩子，*q是右孩子四、結(jié)構(gòu)優(yōu)點(diǎn) 查找父

11、結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)； 遍歷二叉樹，不再需要棧，提高了指針的利用率。第6章 樹4 遍歷二叉樹遍歷：每個(gè)結(jié)點(diǎn)訪問且只訪問一次。template class BinTree BinTreeNode* m_Root; public: void TraverseDFS(int kind); / 深度遍歷二叉樹 void TraverseBFS(); / 層次(廣度)遍歷二叉樹private: void TraversePre(BinTreeNode *p); void TraverseMid(BinTreeNode *p); void TraversePost(BinTreeNode *p);4

12、.1 深度遍歷(遞歸)：先序、中序、后序4.1.1 算法 算法思路：二叉樹 = 根結(jié)點(diǎn) + 左子樹 + 右子樹將二叉樹的遍歷轉(zhuǎn)變?yōu)樽訕涞谋闅v。先序算法：根左右中序算法：左根右后序算法：左右根若二叉樹為空，結(jié)束訪問根結(jié)點(diǎn)先序遍歷左子樹先序遍歷右子樹若二叉樹為空，結(jié)束中序遍歷左子樹訪問根結(jié)點(diǎn)中序遍歷右子樹若二叉樹為空，結(jié)束后序遍歷左子樹后序遍歷右子樹訪問根結(jié)點(diǎn)先序序列：根左右 ABDECF中序序列：左根右 DBEAFC后序序列：左右根 DEBFCA遍歷序列與二叉樹不是一一對(duì)應(yīng)的。例：若前序序列為123，對(duì)應(yīng)的二叉樹有5種。試題例：試找出分別滿足下列條件的所有二叉樹先序序列和中序序列相同中序序列和后

13、序序列相同先序序列和后序序列相同4.1.2 算法實(shí)現(xiàn)、調(diào)試、理解template void BinTree:TraverseDFS(int kind)/ 深度遍歷二叉樹 switch(kind) case 1: TraversePre (m_Root); break; case 2: TraverseMid (m_Root); break; case 3: TraversePost(m_Root); break; coutendl;/ 核心函數(shù)： template void BinTree:TraversePre(BinTreeNode *p) if(p=NULL) return; coutd

14、ata; TraversePre(p-lchild); TraversePre(p-rchild); 評(píng)價(jià)：邏輯極其清晰。但只有邏輯能力強(qiáng)的人，才能理解。調(diào)試、理解程序：調(diào)試技術(shù)：觀察調(diào)用棧alt+7P(&A) =A P(&B) =B P(&D) =D P(NULL);P(NULL) P(&E) =E P(NULL);P(NULL) P(&C) =C P(&F) =F P(NULL);P(NULL) P(NULL) 性能分析：（設(shè)結(jié)點(diǎn)數(shù)為n，樹深度為k）時(shí)間復(fù)雜度O(n)空間復(fù)雜度O(k) 棧的最大深度等于樹深度4.1.3 算法的另一種實(shí)現(xiàn)template vector BinTree:Tra

15、verseDFS2(int kind) vector L; switch(kind) case 1: TraversePre (m_Root,L); break; case 2: TraverseMid (m_Root,L); break; case 3: TraversePost(m_Root,L); break; return L;template void BinTree:TraverseMid (BinTreeNode *p,vector &L) if(p=NULL) return; TraverseMid(p-lchild,L); L.push_back(p-data); Trave

16、rseMid(p-rchild,L); 4.2 層次(廣度)遍歷二叉樹4.2.1 算法將根指針加入隊(duì)列；取隊(duì)首元素，設(shè)為p；訪問結(jié)點(diǎn)*p；若*p存在左孩子，將其加入隊(duì)列； 若*p存在右孩子，將其加入隊(duì)列；若隊(duì)列不空，則循環(huán)，否則遍歷完成。template void BinTree:TraverseBFS()/ 層次遍歷二叉樹 BinTreeNode *p; queueBinTreeNode * Q; / Q為指針隊(duì)列 if(m_Root=NULL) return; Q.push(m_Root); / 將m_Root進(jìn)隊(duì)列 while(!Q.empty() p=Q.front(); / 將隊(duì)首元

17、素賦給p Q.pop(); / 隊(duì)首元素出隊(duì)列 coutdata; if(p-lchild) Q.push(p-lchild); if(p-rchild) Q.push(p-rchild); coutendl;4.2.2 算法評(píng)價(jià) 算法模式：進(jìn)隊(duì)列提交問題，使問題排隊(duì)。出隊(duì)列解決局部問題，分解問題。隊(duì)列不空問題未完。 性能分析：（設(shè)結(jié)點(diǎn)數(shù)為n）時(shí)間復(fù)雜度O(n)空間復(fù)雜度O(k) k是各層結(jié)點(diǎn)數(shù)的最大值4.3 深度遍歷(非遞歸)：先序、中序、后序4.3.1 流程分析與狀態(tài)棧狀態(tài)的組成：當(dāng)前結(jié)點(diǎn)的位置、當(dāng)前方向。enum TravFlagSTART,LEFT,RIGHT;template cla

18、ss Status / 遍歷狀態(tài)類 public: BinTreeNode *p; / 遍歷中的位置 TravFlag flag; / 遍歷中的方向 void NextFlag() if(flag=START) flag=LEFT; return; if(flag=LEFT ) flag=RIGHT; return; ;4.3.2 算法及實(shí)現(xiàn)將起點(diǎn)狀態(tài)m_Root,START進(jìn)棧；取棧頂狀態(tài)，設(shè)為s； 若s的當(dāng)前方向是START， 若存在左孩子，則將左孩子,START進(jìn)棧； 若s的當(dāng)前方向是START， 若存在右孩子，則將右孩子,START進(jìn)棧；若棧不空，則循環(huán)，否則遍歷完成。template

19、 void BinTree:TraverseDFS(int kind) stackStatus S; / 遍歷狀態(tài)棧 Status s1=m_Root,START; S.push(s1); while( !S.empty() ) Status &s=S.top(); / s是棧頂狀態(tài)的引用 Status nexts; switch (s.flag) case START: if(kind=1) coutdatalchild) / 若存在左孩子，向左孩子方向前進(jìn) nexts.p=s.p-lchild; nexts.flag=START; S.push(nexts); s.NextFlag();

20、/ 調(diào)整棧頂狀態(tài)的方向 break; case LEFT: if(kind=2) coutdatarchild) / 若存在左孩子，向左孩子方向前進(jìn) nexts.p=s.p-rchild; nexts.flag=START; S.push(nexts); s.NextFlag(); / 調(diào)整棧頂狀態(tài)的方向 break; case RIGHT: if(kind=3) coutdata ; S.pop(); coutendl;評(píng)價(jià)：將遞歸函數(shù)改為非遞歸函數(shù)的經(jīng)典套路。4.3.3 算法的調(diào)試、理解調(diào)試案例：以后序遍歷為例訪問D訪問E訪問B訪問C訪問A5 遍歷算法的應(yīng)用5.1 統(tǒng)計(jì)結(jié)點(diǎn)的個(gè)數(shù)5.1.1

21、 深度遍歷模式template int BinTree:GetCount() return Count(m_Root); template int BinTree:Count(BinTreeNode *p) int left,right; if(p=NULL) return(0); left= Count(p-lchild); right=Count(p-rchild); return 1+left+right;思考：下列二叉樹計(jì)數(shù)算法是否有錯(cuò)？template int BinTree:Count(BinTreeNode *p) int s=0; if(p) s+; count(p-lchil

22、d); count(p-rchild); return(s); / 統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(shù)template int BinTree:GetLeafCount() return LeafCount(m_Root); template int BinTree:LeafCount(BinTreeNode *p) int left,right; if(p=NULL) return(0); if(root-lchild=NULL & root-rchild=NULL) return 1; left= Count(p-lchild); right=Count(p-rchild); return left+ri

23、ght;5.1.2 層次遍歷模式template int BinTree:GetCount() BinTreeNode *p; int count=0; queueBinTreeNode * Q; / Q為指針隊(duì)列 if(m_Root=NULL) return; Q.push(m_Root); / 將m_Root進(jìn)隊(duì)列 while(!Q.empty() p=Q.front(); / 將隊(duì)首元素賦給p Q.pop(); / 隊(duì)首元素出隊(duì)列 count+; if(p-lchild) Q.push(p-lchild); if(p-rchild) Q.push(p-rchild); return co

24、unt;5.2 析構(gòu)函數(shù)：釋放整個(gè)樹的空間5.2.1 深度遍歷模式template void BinTree:Free() DoFree(m_Root); m_Root=NULL; template void BinTree:DoFree(BinTreeNode *p) if(p=NULL) return; DoFree( p-lchild ); / 釋放左子樹 DoFree( p-rchild ); / 釋放右子樹 delete p; 5.2.2 層次遍歷模式template void BinTree:Free() BinTreeNode *p; queueBinTreeNode * Q;

25、/ Q為指針隊(duì)列 if(m_Root=NULL) return; Q.push(m_Root); / 將m_Root進(jìn)隊(duì)列 while(!Q.empty() p=Q.front(); / 將隊(duì)首元素賦給p Q.pop(); / 隊(duì)首元素出隊(duì)列 if(p-lchild) Q.push(p-lchild); if(p-rchild) Q.push(p-rchild); delete p; 5.3 計(jì)算二叉樹的深度/高度template int BinTree:GetHeight() return Height(m_Root); template int BinTree:Height(BinTree

26、Node *p) int left,right; if(p=NULL) return(0); left =Height(p-lchild); right=Height(p-rchild); if (leftright) return left+1; return right+1;思考：與廣義表的深度算法的相似之處。5.4 交換樹中每個(gè)結(jié)點(diǎn)的左右子樹template void BinTree:Exchange() DoExchange(m_Root); template void BinTree:DoExchange(BinTreeNode *p) if(p=NULL) return; DoEx

27、change( p-lchild ); DoExchange( p-rchild ); BinTreeNode *tmp=p-lchild; p-lchild=p-rchild; p-rchild=tmp; 5.5 查找函數(shù)5.5.1 查找值為e的結(jié)點(diǎn)的地址template BinTreeNode *BinTree:Search(T e) return DoSearch(m_Root, e); template BinTreeNode *BinTree:DoSearch(BinTreeNode *p,T e) if(p=NULL) return(NULL); if(p-data=e) retu

28、rn(p); BinTreeNode *q=DoSearch(p-lchild, e); if(q) return q; return DoSearch(p-rchild, e);5.5.2 查找值為e的結(jié)點(diǎn)的父結(jié)點(diǎn)的地址template BinTreeNode *BinTree:SearchParent(T e) return DoSearchParent(m_Root, e); template BinTreeNode *BinTree:DoSearchParent(BinTreeNode *p,T e) if(p=NULL) return NULL; if(p-lchild & p-lc

29、hild-data=e) return p; if(p-rchild & p-rchild-data=e) return p; BinTreeNode *q=DoSearchParent(p-lchild, e); if(q) return q; return DoSearchParent(p-rchild, e);5.5.3 思考題: 查找所有值為e的結(jié)點(diǎn)，刪除以該結(jié)點(diǎn)為根的子樹。template void BinTree:SearchDelete(T e) return DoSearchDelete(m_Root, e); template void BinTree:DoSearchDel

30、ete(BinTreeNode *p,T e) if(p=NULL) return NULL; if(p-lchild & p-lchild-data=e) DoFree(p-lchild); p-lchild=NULL; if(p-rchild & p-rchild-data=e) DoFree(p-rchild); p-rchild=NULL; DoSearchDelete(p-lchild, e); DoSearchDelete(p-rchild, e);5.6 查找極值結(jié)點(diǎn)templateBinTreeNode * BinTree:GetMax() return GetMax(m_Ro

31、ot); templateBinTreeNode * BinTree:GetMax(BinTreeNode *p) if(p=NULL) return NULL; BinTreeNode *plMax, *prMax, *pMax; plMax = GetMax(p-lchild); prMax = GetMax(p-rchild); if(plMax=NULL & prMax=NULL) return p; / 左右子樹均為空 if(plMax=NULL) / 右子樹不為空 if(prMax-data p-data) return prMax; else return p; if(prMax

32、=NULL) / 右子樹不為空 if(plMax-data p-data) return plMax; else return p; / 左右子樹均不為空 if(plMax-data prMax-data) pMax=plMax; else pMax=prMax; if(p-data pMax-data) return p; else return pMax;5.7 構(gòu)造函數(shù)（參數(shù)：帶空指針標(biāo)記的先序序列）先序序列：ABDECF帶空指針標(biāo)記的先序序列：ABD*E*CF*template BinTree:BinTree(vector &pre) m_pre=pre; m_prei=0; / 完成

33、數(shù)據(jù)準(zhǔn)備 m_Root=DoCreateByPre(); / 調(diào)用核心函數(shù)template BinTreeNode *BinTree:DoCreateByPre() T e=m_prem_prei; m_prei+; if(e=*) return(NULL); BinTreeNode *p=new BinTreeNode; p-data=e; p-lchild=DoCreateByPre(); / 建左子樹 p-rchild=DoCreateByPre(); / 建右子樹 return(p);5.8 構(gòu)造函數(shù)（參數(shù)：先序序列、中序序列）5.8.1 先序序列、中序序列與二叉樹的對(duì)應(yīng)關(guān)系先序: A

34、 B H F D E C K G中序: H B D F A E K C G取A取B取H取F取D取E取C取K取G5.8.2 算法與實(shí)現(xiàn)遞歸算法的常識(shí)：組成分解策略，最終小問題的解決方案。外觀大小問題必須具有完全相同的形式。template BinTree:BinTree(vector &pre,vector &mid) m_pre=pre; m_mid=mid; / 完成數(shù)據(jù)準(zhǔn)備 int n=m_pre.size(); m_Root=DoCreateByPreMid(0,0, n); / 調(diào)用核心函數(shù)template BinTreeNode *BinTree:DoCreateByPreMid(i

35、nt ipre,int imid,int n) if(n=0) return(NULL); / 最終解決方案 BinTreeNode *p=new BinTreeNode; p-data = m_preipre; for(int i=0; ilchild = DoCreateByPreMid(ipre+1, imid, i); p-rchild = DoCreateByPreMid(ipre+i+1,imid+i+1,n-i-1); return p;5.8.3 延伸思考 利用后序序列、中序序列，可以構(gòu)造二叉樹嗎？ 利用先序序列、后序序列，可以構(gòu)造二叉樹嗎？5.9 拷貝構(gòu)造函數(shù)template

36、 BinTree:BinTree(BinTree &tree) m_Root=DoCopy(tree.m_Root); template BinTreeNode * BinTree:DoCopy(BinTreeNode *p) if(p=NULL) return NULL; BinTreeNode *newp=new BinTreeNode; newp-data=p-data; newp-lchild= DoCopy(p-lchild); / 復(fù)制左子樹 newp-rchild= DoCopy(p-rchild); / 復(fù)制右子樹 return newp; 5.10 表達(dá)式樹5.10.1 存儲(chǔ)

37、結(jié)構(gòu)的優(yōu)化字符串存儲(chǔ)結(jié)構(gòu)：在運(yùn)算中，需要識(shí)別運(yùn)算符、運(yùn)算數(shù)；比較優(yōu)先級(jí)。效率低。表達(dá)式樹的邏輯結(jié)構(gòu)運(yùn)算符運(yùn)算對(duì)象左操作數(shù)右操作數(shù)分支結(jié)點(diǎn)葉子結(jié)點(diǎn)左子樹右子樹例：a+b*c-d 5.10.2 表達(dá)式樹的類定義class BinTree static char m_Priority44;BinTreeNode* m_Root; public: BinTree(); BinTree(char mid); BinTree(); void Free(); / 釋放整個(gè)樹的空間 void TraverseDFS(int kind); / 深度遍歷二叉樹 double Value(); 5.10.3 遍歷的

38、意義：求值先序：前綴表達(dá)式中序：中綴表達(dá)式后序：后綴表達(dá)式/ 一次建樹，多次高效計(jì)算、轉(zhuǎn)換方便double BinTree:Value() return DoValue(m_Root); double BinTree:DoValue(BinTreeNode* p) if(p-type=OPD) return(p-data); double opd1 = DoValue(p-lchild); double opd2 = DoValue(p-rchild); return Compute(opd1,p-op,opd2);5.10.4 建樹算法 設(shè)已有表達(dá)式樹的根指針為m_Root，則每建立一個(gè)運(yùn)算

39、符結(jié)點(diǎn)*op和運(yùn)算數(shù)結(jié)點(diǎn)*opd3時(shí)，結(jié)點(diǎn)關(guān)系需做如下調(diào)整： 若*op優(yōu)先級(jí)高：*op作*m_Root的右孩子。 a+ba+b*cop-lchild=m_Root-rchild; op-rchild=opd3;m_Root-rchild=op;若*op優(yōu)先級(jí)低：*m_Root作為*op的左孩子。 a*ba*b-cop-lchild=m_Root; op-rchild=opd3;m_Root=op; 5.10.5 算法實(shí)現(xiàn)理解次序： 1 設(shè)表達(dá)式不含括號(hào)，忽略代碼中所有紅字部分，即實(shí)現(xiàn)簡(jiǎn)單表達(dá)式的建樹過程。 2 考慮任一運(yùn)算數(shù)都可能是括號(hào)表達(dá)式的情形，則紅字部分的遞歸調(diào)用實(shí)現(xiàn)了復(fù)雜表達(dá)式的建樹過

40、程。BinTree:BinTree(char mid) m_midi=0; / 與mid配合使用的下標(biāo)變量 m_Root = DoCreate(mid);BinTreeNode* BinTree:DoCreate(char mid) / 初始化最初始的樹（3個(gè)結(jié)點(diǎn)） BinTreeNode *root,*opd1,*opd2; if(midm_midi=() m_midi+; opd1=DoCreate(mid); else opd1=new BinTreeNode; / 第1個(gè)運(yùn)算數(shù)結(jié)點(diǎn) opd1-type=OPD; opd1-data=midm_midi+-0; opd1-lchild=o

41、pd1-rchild=NULL; root = new BinTreeNode; / 第1個(gè)運(yùn)算符結(jié)點(diǎn) root-type=OP; root-op=midm_midi+; if(midm_midi=() m_midi+; opd2=DoCreate(mid); else opd2=new BinTreeNode; / 第2個(gè)運(yùn)算數(shù)結(jié)點(diǎn) opd2-type=OPD; opd2-data=midm_midi+-0; opd2-lchild=opd2-rchild=NULL; root-lchild=opd1; root-rchild=opd2; / 每躺循環(huán)增加2個(gè)結(jié)點(diǎn): *op和*opd3 wh

42、ile(midm_midi) if(midm_midi=) m_midi+; break; BinTreeNode *op=new BinTreeNode; / 運(yùn)算符結(jié)點(diǎn) op-type=OP; op-op=midm_midi+; BinTreeNode *opd3; if(midm_midi=() m_midi+; opd3=DoCreate(mid); else opd3=new BinTreeNode; / 運(yùn)算數(shù)結(jié)點(diǎn) opd3-type=OPD; opd3-data=midm_midi+-0; opd3-lchild=opd3-rchild=NULL; / 比較*root和*op的優(yōu)

43、先級(jí) if(Precede(root-op, op-op)=op, op-op)=lchild=root-rchild; op-rchild=opd3; root-rchild=op; else op-lchild=root; op-rchild=opd3; root=op; return root;5.9.6 體會(huì) 棧和樹是等價(jià)的。作業(yè)與上機(jī)1 二叉樹類建立二叉樹類，應(yīng)包含以下成員函數(shù)：構(gòu)造、深度/層次遍歷、查找、深度。方向1：盡可能的豐富二叉樹類的成員函數(shù)；方向2：設(shè)計(jì)更多拷貝構(gòu)造函數(shù)（實(shí)現(xiàn)類型轉(zhuǎn)換功能），如：將二叉樹的順序結(jié)構(gòu)轉(zhuǎn)換為二/三叉鏈表；將序偶的集合結(jié)構(gòu)轉(zhuǎn)換為二/三叉鏈表；方向3

44、：建立表達(dá)式樹類；方向4：其他二叉樹類的應(yīng)用算法：計(jì)算寬度、結(jié)點(diǎn)坐標(biāo)方向5：趣味賽題的程序結(jié)構(gòu)的共性研究；2 二叉線索樹類建立二叉樹線索樹類，應(yīng)包含以下成員函數(shù)：構(gòu)造、某種線索化、遍歷。 方向1：三類線索樹、樹類，構(gòu)成類的繼承體系 方向2：線索樹的插入、刪除等算法3 樹類采用二叉鏈表結(jié)構(gòu)，建立樹類，應(yīng)包含以下成員函數(shù)：構(gòu)造、先/后根遍歷、結(jié)點(diǎn)/樹的度、深度。4 哈夫曼類 采用哈夫曼樹結(jié)構(gòu)，計(jì)算哈夫曼編碼；實(shí)現(xiàn)壓縮與解壓縮功能。第6章 樹6 線索二叉樹如何快捷地找出結(jié)點(diǎn)在遍歷過程中的前驅(qū)、后繼？如何保存遍歷過程得到的先后次序？方法評(píng)價(jià)每個(gè)結(jié)點(diǎn)增加前驅(qū)域、后繼域。浪費(fèi)空間利用結(jié)點(diǎn)的空鏈域存儲(chǔ)前驅(qū)指

45、針和后繼指針。問題：如何區(qū)別左孩子指針和前驅(qū)指針？對(duì)策：增加標(biāo)記域。質(zhì)疑：浪費(fèi)空間？解釋：標(biāo)記數(shù)據(jù)有許多靈巧的存儲(chǔ)方法。6.1 線索二叉樹的存儲(chǔ)結(jié)構(gòu)中序線索樹示例：6.2 線索二叉樹類/ 二叉線索樹結(jié)點(diǎn)template struct BinThrTreeNode BinThrTreeNodeType ltype,rtype; T data; BinThrTreeNode *lchild,*rchild;/ 二叉“中序”線索樹的類template class BinThrTree BinThrTreeNode *m_Root;public: BinThrTree(); BinThrTree();

46、 BinThrTree(vector &pre); / 根據(jù)pre創(chuàng)建二叉樹 void Free(); / 釋放整個(gè)樹的空間 void MT_Order(); / 中序線索化 / 求中序遍歷中的后繼、前驅(qū) BinThrTreeNode * MT_GetNext(BinThrTreeNode *p); BinThrTreeNode * MT_GetPrev(BinThrTreeNode *p); void MT_Travese(); / 不使用棧的中序遍歷 / 求父結(jié)點(diǎn)地址 BinThrTreeNode *MT_GetParent(BinThrTreeNode *p);6.3 線索化6.3.1

47、利用遞歸遍歷程序模式，實(shí)現(xiàn)中序線索化設(shè)已有二叉樹所有結(jié)點(diǎn)的ltype、rtype為L(zhǎng)INK遍歷指針p依次指向各結(jié)點(diǎn)，m_lastp緊隨其后，指向上一個(gè)被訪問的結(jié)點(diǎn)。每次指針變調(diào)整前，進(jìn)行*p的前驅(qū)線索化、*m_lastp的后繼線索化。template void BinThrTree:MT_Order() / 中序線索化 if(m_Root=NULL) return; m_lastp=NULL; MT_DoOrder(m_Root); m_lastp-rtype=THREAD; /最后遍歷的是最右下的葉子template void BinThrTree:MT_DoOrder(BinThrTree

48、Node *p) if(p=NULL) return; / 左子樹中序線索化 if(p-ltype=LINK) MT_DoOrder( p-lchild ); if(p-lchild=NULL) / *p的前驅(qū)線索化 p-ltype=THREAD; p-lchild=m_lastp; if(m_lastp & m_lastp-rchild=NULL) / m_lastp的后繼線索化 m_lastp-rtype=THREAD; m_lastp-rchild=p; m_lastp = p; / 右子樹中序線索化 if(p-rtype=LINK) MT_DoOrder( p-rchild );時(shí)間/

49、空間復(fù)雜度： 等同于原遍歷算法。6.3.2 利用非遞歸遍歷程序模式注意：在先序、中序、后續(xù)線索化中，最后一個(gè)結(jié)點(diǎn)的后繼線索化，需要具體分析。先序、中序m_lastp-rtype=THREAD;后序if(m_lastp-rchild) m_lastp-rtype=LINK; else m_lastp-rtype=THREAD;6.4 中序線索樹中的若干應(yīng)用6.4.1 檢索結(jié)點(diǎn)求*p的后繼若p-RTag=THREAD：后繼為*p-rchild 若p-RTag=LINK ：后繼為*p的右子樹中最左下結(jié)點(diǎn)求*p的前驅(qū)若p-LTag=THREAD：前驅(qū)為*p-lchild若p-LTag=LINK ：前驅(qū)為*p的左子樹中最右下結(jié)點(diǎn)/ 求*p的后繼 template BinThrTreeNode* BinThrTree:MT_GetNext(BinThrTreeNode *p) if(p-rtype=THREAD) return p-rchild; for(p=p-rchild; p-ltype=LINK; p=p-lchild); return p;/ 求*p的前驅(qū) template BinThrTreeNode* BinThrTree:MT_GetPrev(BinThrTreeNo