《數(shù)據(jù)結(jié)構(gòu)(C語言版) 第6章 樹》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)(C語言版) 第6章 樹（63頁珍藏版）》請(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(n>0)個(gè)結(jié)點(diǎn)的有限集，在任意一棵樹中： 1 有且只有一個(gè)特定的根(root)結(jié)點(diǎn)； 2 當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限子集T1,T2...Tm，每個(gè)子集是一棵樹，稱為子樹。 1.2 形式定義 D={ai | ai∈ElemSet，i=1,…,n} 二元關(guān)系S的定義： 當(dāng)n=1時(shí)，S=φ； 當(dāng)n>1時(shí)： 1 根的特殊地位 唯一無前驅(qū)的元素：根結(jié)點(diǎn)(root)

2、； 2 結(jié)點(diǎn)的劃分 可將D-{root}劃分成m(m>0)個(gè)互不相交的子集D1,D2,…Dm，對(duì)任意子集Di，唯一存在xi∈Di，有∈S； 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,K} S={,,, ,,, , <

3、D,I>, } root: A D-{A}可分為： D1={B,E,F,G} D2={C,H} D3={D,I,J} S-{,,}可分為： 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ù)。

4、 葉子結(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 其他概念 有序樹、無序樹 左右結(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)化、

5、概念強(qiáng)化：左子樹、右子樹。 樹形表示法 廣義表表示法 A(B(D),C(F(,E),G)) 2.2 二叉樹的形態(tài) 具有n個(gè)結(jié)點(diǎn)的不同形態(tài)的二叉樹有多少顆？ 二叉樹相似：二者都為空；或它們的左右子樹相似。 例：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 += GetT

6、reeCount(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)有 (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)。 深

7、度為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、若i>0，i的雙親結(jié)點(diǎn)是(i-1)/2。 2、若2i+1

8、結(jié)構(gòu)存于數(shù)組A[0…100]中，葉子結(jié)點(diǎn)的最小編號(hào)是 。 A、32 B、33 C、34 D、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 BinTreeNod

9、e { T data; BinTreeNode *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; };

10、 邏輯結(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 { 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 T

11、ag {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->right=p; ⑤若結(jié)點(diǎn)*p有左孩子*q，有右孩子*r，則

12、 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)

13、 p_RightChild=p->child; ③當(dāng)p->right!=NULL時(shí)，求結(jié)點(diǎn)*p的父結(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->

14、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) 查找父結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)； 遍歷二叉樹，不再需要棧，提高了指針的利用率。 第6章 樹 4 遍歷二叉樹 遍歷：每個(gè)結(jié)點(diǎn)訪問且只訪問一次。 template class BinTree { BinTreeNode* m_Root;

15、 public: void TraverseDFS(int kind); // 深度遍歷二叉樹 void TraverseBFS(); // 層次(廣度)遍歷二叉樹 private: void TraversePre(BinTreeNode *p); void TraverseMid(BinTreeNode *p); void TraversePost(BinTreeNode *p); } 4.1 深度遍歷(遞歸)：先序、中序、后序 4.1.1 算法 算法思路：二叉樹 = 根結(jié)點(diǎn) + 左子樹 + 右子樹 將二

16、叉樹的遍歷轉(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種。 試題

17、例：試找出分別滿足下列條件的所有二叉樹 ①先序序列和中序序列相同 ②中序序列和后序序列相同 ③先序序列和后序序列相同 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; }

18、 cout< void BinTree::TraversePre(BinTreeNode *p) { ①if(p==NULL) return; ②cout<data; ③TraversePre(p->lchild); ④TraversePre(p->rchild); } 評(píng)價(jià)： 邏輯極其清晰。 但只有邏輯能力強(qiáng)的人，才能理解。 調(diào)試、理解程序： 調(diào)試技術(shù)： 觀察調(diào)用棧alt+7 P(&A) ①② =>'A'

19、③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) 棧的

20、最大深度等于樹深度 4.1.3 算法的另一種實(shí)現(xiàn) template vector BinTree::TraverseDFS2(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

21、 void BinTree::TraverseMid (BinTreeNode *p,vector &L) { if(p==NULL) return; TraverseMid(p->lchild,L); L.push_back(p->data); TraverseMid(p->rchild,L); } 4.2 層次(廣度)遍歷二叉樹 4.2.1 算法 ①將根指針加入隊(duì)列； ②取隊(duì)首元素，設(shè)為p；訪問結(jié)點(diǎn)*p； ③若*p存在左孩子，將其加入隊(duì)列； 若*p存在右孩子，將其加入隊(duì)列； ④若隊(duì)列不空，則循環(huán)②③，否則遍歷完成。

22、 template void BinTree::TraverseBFS() // 層次遍歷二叉樹 { BinTreeNode *p; queue *> 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ì)列 cout<data;

23、if(p->lchild) Q.push(p->lchild); if(p->rchild) Q.push(p->rchild); } cout<

24、avFlag{START,LEFT,RIGHT}; template class 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_Ro

25、ot,START}進(jìn)棧； ②取棧頂狀態(tài)，設(shè)為s； ③若s的當(dāng)前方向是START， 若存在左孩子，則將{左孩子,START}進(jìn)棧； 若s的當(dāng)前方向是START， 若存在右孩子，則將{右孩子,START}進(jìn)棧； ④若棧不空，則循環(huán)②③，否則遍歷完成。 template void BinTree::TraverseDFS(int kind) { stack > S; // 遍歷狀態(tài)棧 Status s1={m_Root,START}; S.push(s1); while( !S.empty(

26、) ) { Status &s=S.top(); // s是棧頂狀態(tài)的引用 Status nexts; switch (s.flag) { case START: if(kind==1) cout<data<<" "; if(s.p->lchild) // 若存在左孩子，向左孩子方向前進(jìn) { nexts.p=s.p->lchild; nexts.flag=START; S.push(nexts); } s.NextFla

27、g(); // 調(diào)整棧頂狀態(tài)的方向 break; case LEFT: if(kind==2) cout<data<<" "; if(s.p->rchild) // 若存在左孩子，向左孩子方向前進(jìn) { nexts.p=s.p->rchild; nexts.flag=START; S.push(nexts); } s.NextFlag(); // 調(diào)整棧頂狀態(tài)的方向 break; case R

28、IGHT: if(kind==3) cout<data<<" "; S.pop(); } } cout< int BinTree

29、>::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(Bin

30、TreeNode *p) { int s=0; if(p) { s++; count(p->lchild); 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 lef

31、t,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+right; } 5.1.2 層次遍歷模式 template int BinTree::GetCount() { BinTreeNode *p; int count=0; queue

32、 *> 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 count; } 5.2 析構(gòu)函數(shù)：釋放

33、整個(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 層次遍歷模式

34、 template void BinTree::Free() { BinTreeNode *p; queue *> 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ì)列 if(p->lchild) Q.push(p->lchild);

35、 if(p->rchild) Q.push(p->rchild); delete p; } } 5.3 計(jì)算二叉樹的深度/高度 template int BinTree::GetHeight() { return Height(m_Root); } template int BinTree::Height(BinTreeNode *p) { int left,right; if(p==NULL) return(0); left =Height(p->lchild); ri

36、ght=Height(p->rchild); if (left>right) 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; DoExchan

37、ge( 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 *Bi

38、nTree::DoSearch(BinTreeNode *p,T e) { if(p==NULL) return(NULL); if(p->data==e) return(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)

39、 { return DoSearchParent(m_Root, e); } template BinTreeNode *BinTree::DoSearchParent(BinTreeNode *p,T e) { if(p==NULL) return NULL; if(p->lchild && p->lchild->data==e) return p; if(p->rchild && p->rchild->data==e) return p; BinTreeNode *q=DoSearchParent(p->lchild,

40、 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::DoSearchDelete(BinTreeNode *p,T e) { if(p==NULL) return

41、 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) template BinTreeNode * BinTree

42、>::GetMax() { return GetMax(m_Root); } template BinTreeNode * 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; // 左右子樹均為空

43、 if(plMax==NULL) // 右子樹不為空 if(prMax->data > p->data) return prMax; else return p; if(prMax==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; el

44、se 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; // 完成數(shù)據(jù)準(zhǔn)備 m_Root=DoCreateByPre(); // 調(diào)用核心函數(shù) } template BinTreeNode *BinTree::DoCreateByPre()

45、 { T e=m_pre[m_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 B H F D E C K G 中序: H B D

46、 F A E K C G 取A 取B 取H 取F 取D 取E 取C 取K 取G 5.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,

47、 n); // 調(diào)用核心函數(shù) } template BinTreeNode *BinTree::DoCreateByPreMid(int ipre,int imid,int n) { if(n==0) return(NULL); // 最終解決方案 BinTreeNode *p=new BinTreeNode; p->data = m_pre[ipre]; for(int i=0; i

48、; p->lchild = 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 BinTree::BinTree(BinTree &tree) { m_Root=DoCopy(tree.m_Root); }

49、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

50、.10.1 存儲(chǔ)結(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_Priority[4][4]; BinTreeNode* m_Root; public: BinTree(); BinTree(char mid[]); ~BinTree(); vo

51、id Free(); // 釋放整個(gè)樹的空間 void TraverseDFS(int kind); // 深度遍歷二叉樹 double Value(); …………… } 5.10.3 遍歷的意義：求值 先序：前綴表達(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);

52、 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)算符結(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+b a+b*c op->lchild=m_Root->rchild; op->rchild=opd3; m_Root->rchild=

53、op; 若*op優(yōu)先級(jí)低：*m_Root作為*op的左孩子。 a*b a*b-c op->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á)式的建樹過程。 BinTree::BinTree(char mid[]) { m_midi=0; // 與mid配合使用的下標(biāo)變量 m_Root = DoCreate(

54、mid); } BinTreeNode* BinTree::DoCreate(char mid[]) { // 初始化最初始的樹（3個(gè)結(jié)點(diǎn)） BinTreeNode *root,*opd1,*opd2; if(mid[m_midi]=='(') { m_midi++; opd1=DoCreate(mid); } else { opd1=new BinTreeNode; // 第1個(gè)運(yùn)算數(shù)結(jié)點(diǎn) opd1->type=OPD; opd1->data=mid[m_midi++]-'0'; opd1->lchild=

55、opd1->rchild=NULL; } root = new BinTreeNode; // 第1個(gè)運(yùn)算符結(jié)點(diǎn) root->type=OP; root->op=mid[m_midi++]; if(mid[m_midi]=='(') { m_midi++; opd2=DoCreate(mid); } else { opd2=new BinTreeNode; // 第2個(gè)運(yùn)算數(shù)結(jié)點(diǎn) opd2->type=OPD; opd2->data=mid[m_midi++]-'0'; opd2->lchild=

56、opd2->rchild=NULL; } root->lchild=opd1; root->rchild=opd2; // 每躺循環(huán)增加2個(gè)結(jié)點(diǎn): *op和*opd3 while(mid[m_midi]) { if(mid[m_midi]==')') { m_midi++; break; } BinTreeNode *op=new BinTreeNode; // 運(yùn)算符結(jié)點(diǎn) op->type=OP; op->op=mid[m_midi++]; BinTreeNode *opd3; if(mid[m_midi]==

57、'(') { m_midi++; opd3=DoCreate(mid); } else { opd3=new BinTreeNode; // 運(yùn)算數(shù)結(jié)點(diǎn) opd3->type=OPD; opd3->data=mid[m_midi++]-'0'; opd3->lchild=opd3->rchild=NULL; } // 比較*root和*op的優(yōu)先級(jí) if(Precede(root->op, op->op)=='<') if(Precede(root->op, op->o

58、p)=='<') { 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ì)更多

59、拷貝構(gòu)造函數(shù)（實(shí)現(xiàn)類型轉(zhuǎn)換功能），如：將二叉樹的順序結(jié)構(gòu)轉(zhuǎn)換為二/三叉鏈表；將序偶的集合結(jié)構(gòu)轉(zhuǎn)換為二/三叉鏈表； 方向3：建立表達(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ì)算哈夫曼編碼

60、；實(shí)現(xiàn)壓縮與解壓縮功能。 第6章 樹 6 線索二叉樹 如何快捷地找出結(jié)點(diǎn)在遍歷過程中的前驅(qū)、后繼？如何保存遍歷過程得到的先后次序？ 方法 評(píng)價(jià) 每個(gè)結(jié)點(diǎn)增加前驅(qū)域、后繼域。 浪費(fèi)空間 利用結(jié)點(diǎn)的空鏈域存儲(chǔ)前驅(qū)指針和后繼指針。 問題：如何區(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 { BinThrTree

61、NodeType ltype,rtype; T data; BinThrTreeNode *lchild,*rchild; }; // 二叉“中序”線索樹的類 template class BinThrTree { BinThrTreeNode *m_Root; public: BinThrTree(); ~BinThrTree(); BinThrTree(vector &pre); // 根據(jù)pre創(chuàng)建二叉樹 void Free(); // 釋放整個(gè)樹的空間 void MT_Ord

62、er(); // 中序線索化 // 求中序遍歷中的后繼、前驅(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 利用遞歸遍歷程序模式，實(shí)現(xiàn)中序

63、線索化 設(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

64、ss T> void BinThrTree::MT_DoOrder(BinThrTreeNode *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->rt

65、ype=THREAD; m_lastp->rchild=p; } m_lastp = p; // 右子樹中序線索化 if(p->rtype==LINK) MT_DoOrder( p->rchild ); } 時(shí)間/空間復(fù)雜度： 等同于原遍歷算法。 6.3.2 利用非遞歸遍歷程序模式 注意：在先序、中序、后續(xù)線索化中，最后一個(gè)結(jié)點(diǎn)的后繼線索化，需要具體分析。 先序、中序 m_lastp->rtype=THREAD; 后序 if(m_lastp->rchild) m_lastp->rtype=LINK; else

66、 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