第6章 樹1樹的邏輯結(jié)構(gòu) 核心關(guān)系：層次關(guān)系。1.1 通俗定義樹形表示法廣義表表示法A(B(E,F,G),C(H),D(I,J)樹是n(n>0)個結(jié)點的有限集，在任意一棵樹中：1 有且只有一個特定的根(root)結(jié)點；2 當n>1時，其余結(jié)點可分為m(m>0)個互不相交的有限子集T1,T2.Tm，每個子集是一棵樹，稱為子樹。1.2 形式定義 D=ai | aiElemSet，i=1,n二元關(guān)系S的定義： 當n=1時，S=；當n>1時：1根的特殊地位唯一無前驅(qū)的元素：根結(jié)點(root)；2結(jié)點的劃分可將D-root劃分成m(m>0)個互不相交的子集D1,D2,Dm，對任意子集Di，唯一存在xiDi，有<root,xi>S；3關(guān)系的劃分對應(yīng)D-root的劃分,可將S-<root,x1>,<root,xm>唯一劃分成互不相交的子集S1,S2,.,Sm，對于任意i, Si是Di上的二元關(guān)系。(Di,Si)是一棵樹，稱為根root的子樹。示例：D=A,B,C,D,E,F,G,H,I,J,KS=<A,B>,<A,C>,<A,D>, <B,E>,<B,F>,<B,G>, <C,H>, <D,I>,<D,J> root: AD-A可分為：D1=B,E,F,GD2=C,HD3=D,I,JS-<A,B>,<A,C>,<A,D>可分為：S1: <B,E>,<B,F>,<B,G>S2: <C,H>S3: <D,I>,<D,J>1.3 概念1.3.1 若干角色雙親、孩子一個序偶中的直接前驅(qū)、直接后繼。祖先、子孫一個序偶集合中的前驅(qū)、后繼。兄弟具有相同直接前驅(qū)的數(shù)據(jù)元素。堂兄弟具有相同前驅(qū)的數(shù)據(jù)元素。1.3.2 與“度”相關(guān)的概念結(jié)點的度結(jié)點擁有的子樹數(shù)。葉子結(jié)點度為0的結(jié)點。分支結(jié)點度不為0的結(jié)點。樹的度樹內(nèi)所有結(jié)點的度的最大值。1.3.3 與“深度”相關(guān)的概念結(jié)點深度根結(jié)點的深度為1若某結(jié)點深度為i, 則其子結(jié)點深度為i+1樹的深度 樹中結(jié)點的最大深度?；?空樹深度為0； 非空樹深度等于子樹深度的最大值加1。1.3.4 其他概念有序樹、無序樹左右結(jié)點是否等價森林m棵互不相交的樹的集合。m=0：空集；m=1：樹 1.4 基本操作 構(gòu)造、析構(gòu)、遍歷、查找、插入、刪除、2 二叉樹的邏輯結(jié)構(gòu)2.1 定義 結(jié)構(gòu)簡化、概念強化：左子樹、右子樹。樹形表示法廣義表表示法A(B(D),C(F(,E),G) 2.2 二叉樹的形態(tài)具有n個結(jié)點的不同形態(tài)的二叉樹有多少顆？ 二叉樹相似：二者都為空；或它們的左右子樹相似。例：n個結(jié)點的相似樹的個數(shù)template <class T>int BinTree<T>: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é)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1。試題例：若一棵m叉樹中度為i的結(jié)點有Ni個，則該樹的葉結(jié)點有 (N1+2N2+mNm+1)-(N1+N2+Nm) 個。2.3.2 性質(zhì)2二叉樹的第i層上的結(jié)點數(shù)最多為2i-1。2.3.3 性質(zhì)3深度為k的二叉樹中結(jié)點總數(shù)最多為2k-1。滿二叉樹完全二叉樹深度為k，共有2k-1個結(jié)點。深度為k，前k-1層是滿二叉樹，第k層的結(jié)點從左至右依次排列。2.3.4 性質(zhì)4具有n個結(jié)點的完全二叉樹的深度為int(log2n)+1。2.3.5 性質(zhì)5有n個結(jié)點的完全二叉樹，結(jié)點從0順序標號，則：1、若i>0，i的雙親結(jié)點是(i-1)/2。2、若2i+1<n，i的左孩子是2i+1；否則，i無左孩子。3、若2i+2<n，i的右孩子是2i+2；否則，i無右孩子。3 二叉樹的存儲結(jié)構(gòu)3.1 順序結(jié)構(gòu)3.1.1 存儲規(guī)則依照滿二叉樹的結(jié)點順序，存放各個結(jié)點。存儲位置暗藏樹的關(guān)系。試題例：將68個結(jié)點的完全二叉樹，按順序存儲結(jié)構(gòu)存于數(shù)組A0100中，葉子結(jié)點的最小編號是 。 A、32B、33C、34D、35試題例：具有101個結(jié)點的完全二叉樹，度為1的結(jié)點有 個。3.1.2 性能分析滿/完全二叉樹：存儲效率最高，插入、刪除方便。非完全二叉樹的處理方法：非完全二叉樹修補結(jié)構(gòu)不存在的結(jié)點，用特殊符號標識。退化的二叉樹及其存儲效果：評價：空間浪費大，不靈活。 3.2 鏈式結(jié)構(gòu)3.2.1 二叉鏈表結(jié)構(gòu)Template <class T>struct BinTreeNode T data; BinTreeNode<T> *lchild, *rchild;template <class T>class BinTree BinTreeNode<T>* m_Root;邏輯結(jié)構(gòu)存儲結(jié)構(gòu)空指針域有多少？3.2.2 三叉鏈表結(jié)構(gòu)Template <class T>struct BinTreeNode T data; BinTreeNode *parent; BinTreeNode *lchild; BinTreeNode *rchild;邏輯結(jié)構(gòu)存儲結(jié)構(gòu)3.2.3 三叉靜鏈表結(jié)構(gòu)Template <class T>struct BinTreeNode T data; int parent,lchild, rchild;template <class T>class BinTree int m_Root; / 根結(jié)點的下標 BinTreeNode<T>* m_Data; / 結(jié)點的存儲空間邏輯結(jié)構(gòu)存儲結(jié)構(gòu)第6章 樹專題：二叉樹存儲結(jié)構(gòu)的遐想一、結(jié)構(gòu)定義enum Tag LEFT,NOLEFT;Template <class T>struct BinTreeNode Tag type; T data; BinTreeNode<T> *child, *right;若結(jié)點*p有左孩子，則p->type=LEFT;否則p->type=NOLEFT;若結(jié)點*p是根結(jié)點，則p->right=NULL;若結(jié)點*p是葉子結(jié)點，則p->child=NULL;若結(jié)點*p有且僅有一個子結(jié)點*q，則 p->child=q; q->right=p;若結(jié)點*p有左孩子*q，有右孩子*r，則 p->child=q; q->right=r; r->right=p;二、結(jié)構(gòu)示例二叉鏈表結(jié)構(gòu)三、基本操作求結(jié)點*p的左孩子*p_LeftChild。 if(p->type=LEFT) p_LeftChild=p->child;求結(jié)點*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;當p->right!=NULL時，求結(jié)點*p的父結(jié)點*p_Parent。 設(shè)q=p->right if(q->child=p) p_Parent=q; / *p是獨左/右子 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)點 查找父結(jié)點的時間復(fù)雜度為O(1)； 遍歷二叉樹，不再需要棧，提高了指針的利用率。第6章 樹4 遍歷二叉樹遍歷：每個結(jié)點訪問且只訪問一次。template <class T>class BinTree BinTreeNode<T>* m_Root; public: void TraverseDFS(int kind); / 深度遍歷二叉樹 void TraverseBFS(); / 層次(廣度)遍歷二叉樹private: void TraversePre(BinTreeNode<T> *p); void TraverseMid(BinTreeNode<T> *p); void TraversePost(BinTreeNode<T> *p);4.1 深度遍歷(遞歸)：先序、中序、后序4.1.1 算法 算法思路：二叉樹 = 根結(jié)點 + 左子樹 + 右子樹將二叉樹的遍歷轉(zhuǎn)變?yōu)樽訕涞谋闅v。先序算法：根左右中序算法：左根右后序算法：左右根若二叉樹為空，結(jié)束訪問根結(jié)點先序遍歷左子樹先序遍歷右子樹若二叉樹為空，結(jié)束中序遍歷左子樹訪問根結(jié)點中序遍歷右子樹若二叉樹為空，結(jié)束后序遍歷左子樹后序遍歷右子樹訪問根結(jié)點先序序列：根左右 ABDECF中序序列：左根右 DBEAFC后序序列：左右根 DEBFCA遍歷序列與二叉樹不是一一對應(yīng)的。例：若前序序列為123，對應(yīng)的二叉樹有5種。試題例：試找出分別滿足下列條件的所有二叉樹先序序列和中序序列相同中序序列和后序序列相同先序序列和后序序列相同4.1.2 算法實現(xiàn)、調(diào)試、理解template <class T>void BinTree<T>:TraverseDFS(int kind)/ 深度遍歷二叉樹 switch(kind) case 1: TraversePre (m_Root); break; case 2: TraverseMid (m_Root); break; case 3: TraversePost(m_Root); break; cout<<endl;/ 核心函數(shù)： template <class T>void BinTree<T>:TraversePre(BinTreeNode<T> *p) if(p=NULL) return; cout<<p->data; TraversePre(p->lchild); TraversePre(p->rchild); 評價：邏輯極其清晰。但只有邏輯能力強的人，才能理解。調(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é)點數(shù)為n，樹深度為k）時間復(fù)雜度O(n)空間復(fù)雜度O(k) 棧的最大深度等于樹深度4.1.3 算法的另一種實現(xiàn)template <class T>vector<T> BinTree<T>:TraverseDFS2(int kind) vector<T> 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 <class T>void BinTree<T>:TraverseMid (BinTreeNode<T> *p,vector<T> &L) if(p=NULL) return; TraverseMid(p->lchild,L); L.push_back(p->data); TraverseMid(p->rchild,L); 4.2 層次(廣度)遍歷二叉樹4.2.1 算法將根指針加入隊列；取隊首元素，設(shè)為p；訪問結(jié)點*p；若*p存在左孩子，將其加入隊列； 若*p存在右孩子，將其加入隊列；若隊列不空，則循環(huán)，否則遍歷完成。template <class T>void BinTree<T>:TraverseBFS()/ 層次遍歷二叉樹 BinTreeNode<T> *p; queue<BinTreeNode<T> *> Q; / Q為指針隊列 if(m_Root=NULL) return; Q.push(m_Root); / 將m_Root進隊列 while(!Q.empty() p=Q.front(); / 將隊首元素賦給p Q.pop(); / 隊首元素出隊列 cout<<p->data; if(p->lchild) Q.push(p->lchild); if(p->rchild) Q.push(p->rchild); cout<<endl;4.2.2 算法評價 算法模式：進隊列提交問題，使問題排隊。出隊列解決局部問題，分解問題。隊列不空問題未完。 性能分析：（設(shè)結(jié)點數(shù)為n）時間復(fù)雜度O(n)空間復(fù)雜度O(k) k是各層結(jié)點數(shù)的最大值4.3 深度遍歷(非遞歸)：先序、中序、后序4.3.1 流程分析與狀態(tài)棧狀態(tài)的組成：當前結(jié)點的位置、當前方向。enum TravFlagSTART,LEFT,RIGHT;template <class T>class Status / 遍歷狀態(tài)類 public: BinTreeNode<T> *p; / 遍歷中的位置 TravFlag flag; / 遍歷中的方向 void NextFlag() if(flag=START) flag=LEFT; return; if(flag=LEFT ) flag=RIGHT; return; ;4.3.2 算法及實現(xiàn)將起點狀態(tài)m_Root,START進棧；取棧頂狀態(tài)，設(shè)為s； 若s的當前方向是START， 若存在左孩子，則將左孩子,START進棧； 若s的當前方向是START， 若存在右孩子，則將右孩子,START進棧；若棧不空，則循環(huán)，否則遍歷完成。template <class T>void BinTree<T>:TraverseDFS(int kind) stack<Status<T> > S; / 遍歷狀態(tài)棧 Status<T> s1=m_Root,START; S.push(s1); while( !S.empty() ) Status<T> &s=S.top(); / s是棧頂狀態(tài)的引用 Status<T> nexts; switch (s.flag) case START: if(kind=1) cout<<s.p->data<<" " if(s.p->lchild) / 若存在左孩子，向左孩子方向前進 nexts.p=s.p->lchild; nexts.flag=START; S.push(nexts); s.NextFlag(); / 調(diào)整棧頂狀態(tài)的方向 break; case LEFT: if(kind=2) cout<<s.p->data<<" " if(s.p->rchild) / 若存在左孩子，向左孩子方向前進 nexts.p=s.p->rchild; nexts.flag=START; S.push(nexts); s.NextFlag(); / 調(diào)整棧頂狀態(tài)的方向 break; case RIGHT: if(kind=3) cout<<s.p->data<<" " S.pop(); cout<<endl;評價：將遞歸函數(shù)改為非遞歸函數(shù)的經(jīng)典套路。4.3.3 算法的調(diào)試、理解調(diào)試案例：以后序遍歷為例訪問D訪問E訪問B訪問C訪問A5 遍歷算法的應(yīng)用5.1 統(tǒng)計結(jié)點的個數(shù)5.1.1 深度遍歷模式template <class T>int BinTree<T>:GetCount() return Count(m_Root); template <class T>int BinTree<T>:Count(BinTreeNode<T> *p) int left,right; if(p=NULL) return(0); left= Count(p->lchild); right=Count(p->rchild); return 1+left+right;思考：下列二叉樹計數(shù)算法是否有錯？template <class T>int BinTree<T>:Count(BinTreeNode<T> *p) int s=0; if(p) s+; count(p->lchild); count(p->rchild); return(s); / 統(tǒng)計葉子結(jié)點的個數(shù)template <class T>int BinTree<T>:GetLeafCount() return LeafCount(m_Root); template <class T>int BinTree<T>:LeafCount(BinTreeNode<T> *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+right;5.1.2 層次遍歷模式template <class T>int BinTree<T>:GetCount() BinTreeNode<T> *p; int count=0; queue<BinTreeNode<T> *> Q; / Q為指針隊列 if(m_Root=NULL) return; Q.push(m_Root); / 將m_Root進隊列 while(!Q.empty() p=Q.front(); / 將隊首元素賦給p Q.pop(); / 隊首元素出隊列 count+; if(p->lchild) Q.push(p->lchild); if(p->rchild) Q.push(p->rchild); return count;5.2 析構(gòu)函數(shù)：釋放整個樹的空間5.2.1 深度遍歷模式template <class T>void BinTree<T>:Free() DoFree(m_Root); m_Root=NULL; template <class T>void BinTree<T>:DoFree(BinTreeNode<T> *p) if(p=NULL) return; DoFree( p->lchild ); / 釋放左子樹 DoFree( p->rchild ); / 釋放右子樹 delete p; 5.2.2 層次遍歷模式template <class T>void BinTree<T>:Free() BinTreeNode<T> *p; queue<BinTreeNode<T> *> Q; / Q為指針隊列 if(m_Root=NULL) return; Q.push(m_Root); / 將m_Root進隊列 while(!Q.empty() p=Q.front(); / 將隊首元素賦給p Q.pop(); / 隊首元素出隊列 if(p->lchild) Q.push(p->lchild); if(p->rchild) Q.push(p->rchild); delete p; 5.3 計算二叉樹的深度/高度template <class T>int BinTree<T>:GetHeight() return Height(m_Root); template <class T>int BinTree<T>:Height(BinTreeNode<T> *p) int left,right; if(p=NULL) return(0); left =Height(p->lchild); right=Height(p->rchild); if (left>right) return left+1; return right+1;思考：與廣義表的深度算法的相似之處。5.4 交換樹中每個結(jié)點的左右子樹template <class T>void BinTree<T>:Exchange() DoExchange(m_Root); template <class T>void BinTree<T>:DoExchange(BinTreeNode<T> *p) if(p=NULL) return; DoExchange( p->lchild ); DoExchange( p->rchild ); BinTreeNode<T> *tmp=p->lchild; p->lchild=p->rchild; p->rchild=tmp; 5.5 查找函數(shù)5.5.1 查找值為e的結(jié)點的地址template <class T>BinTreeNode<T> *BinTree<T>:Search(T e) return DoSearch(m_Root, e); template <class T>BinTreeNode<T> *BinTree<T>:DoSearch(BinTreeNode<T> *p,T e) if(p=NULL) return(NULL); if(p->data=e) return(p); BinTreeNode<T> *q=DoSearch(p->lchild, e); if(q) return q; return DoSearch(p->rchild, e);5.5.2 查找值為e的結(jié)點的父結(jié)點的地址template <class T>BinTreeNode<T> *BinTree<T>:SearchParent(T e) return DoSearchParent(m_Root, e); template <class T>BinTreeNode<T> *BinTree<T>:DoSearchParent(BinTreeNode<T> *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<T> *q=DoSearchParent(p->lchild, e); if(q) return q; return DoSearchParent(p->rchild, e);5.5.3 思考題: 查找所有值為e的結(jié)點，刪除以該結(jié)點為根的子樹。template <class T>void BinTree<T>:SearchDelete(T e) return DoSearchDelete(m_Root, e); template <class T>void BinTree<T>:DoSearchDelete(BinTreeNode<T> *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é)點template<class T>BinTreeNode<T> * BinTree<T>:GetMax() return GetMax(m_Root); template<class T>BinTreeNode<T> * BinTree<T>:GetMax(BinTreeNode<T> *p) if(p=NULL) return NULL; BinTreeNode<T> *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=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ù)：帶空指針標記的先序序列）先序序列：ABDECF帶空指針標記的先序序列：ABD*E*CF*template <class T>BinTree<T>:BinTree(vector<T> &pre) m_pre=pre; m_prei=0; / 完成數(shù)據(jù)準備 m_Root=DoCreateByPre(); / 調(diào)用核心函數(shù)template <class T>BinTreeNode<T> *BinTree<T>:DoCreateByPre() T e=m_prem_prei; m_prei+; if(e='*') return(NULL); BinTreeNode<T> *p=new BinTreeNode<T> p->data=e; p->lchild=DoCreateByPre(); / 建左子樹 p->rchild=DoCreateByPre(); / 建右子樹 return(p);5.8 構(gòu)造函數(shù)（參數(shù)：先序序列、中序序列）5.8.1 先序序列、中序序列與二叉樹的對應(yīng)關(guān)系先序: A 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 算法與實現(xiàn)遞歸算法的常識：組成分解策略，最終小問題的解決方案。外觀大小問題必須具有完全相同的形式。template <class T>BinTree<T>:BinTree(vector<T> &pre,vector<T> &mid) m_pre=pre; m_mid=mid; / 完成數(shù)據(jù)準備 int n=m_pre.size(); m_Root=DoCreateByPreMid(0,0, n); / 調(diào)用核心函數(shù)template <class T>BinTreeNode<T> *BinTree<T>:DoCreateByPreMid(int ipre,int imid,int n) if(n=0) return(NULL); / 最終解決方案 BinTreeNode<T> *p=new BinTreeNode<T> p->data = m_preipre; for(int i=0; i<n; i+) / 在中序序列中定位根結(jié)點 if(m_preipre=m_midimid+i) break; 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 <class T>BinTree<T>:BinTree(BinTree<T> &tree) m_Root=DoCopy(tree.m_Root); template <class T>BinTreeNode<T> * BinTree<T>:DoCopy(BinTreeNode<T> *p) if(p=NULL) return NULL; BinTreeNode<T> *newp=new BinTreeNode<T> newp->data=p->data; newp->lchild= DoCopy(p->lchild); / 復(fù)制左子樹 newp->rchild= DoCopy(p->rchild); / 復(fù)制右子樹 return newp; 5.10 表達式樹5.10.1 存儲結(jié)構(gòu)的優(yōu)化字符串存儲結(jié)構(gòu)：在運算中，需要識別運算符、運算數(shù)；比較優(yōu)先級。效率低。表達式樹的邏輯結(jié)構(gòu)運算符運算對象左操作數(shù)右操作數(shù)分支結(jié)點葉子結(jié)點左子樹右子樹例：a+b*c-d 5.10.2 表達式樹的類定義class BinTree static char m_Priority44;BinTreeNode* m_Root; public: BinTree(); BinTree(char mid); BinTree(); void Free(); / 釋放整個樹的空間 void TraverseDFS(int kind); / 深度遍歷二叉樹 double Value(); 5.10.3 遍歷的意義：求值先序：前綴表達式中序：中綴表達式后序：后綴表達式/ 一次建樹，多次高效計算、轉(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è)已有表達式樹的根指針為m_Root，則每建立一個運算符結(jié)點*op和運算數(shù)結(jié)點*opd3時，結(jié)點關(guān)系需做如下調(diào)整： 若*op優(yōu)先級高：*op作*m_Root的右孩子。 a+ba+b*cop->lchild=m_Root->rchild; op->rchild=opd3;m_Root->rchild=op;若*op優(yōu)先級低：*m_Root作為*op的左孩子。 a*ba*b-cop->lchild=m_Root; op->rchild=opd3;m_Root=op; 5.10.5 算法實現(xiàn)理解次序： 1 設(shè)表達式不含括號，忽略代碼中所有紅字部分，即實現(xiàn)簡單表達式的建樹過程。 2 考慮任一運算數(shù)都可能是括號表達式的情形，則紅字部分的遞歸調(diào)用實現(xiàn)了復(fù)雜表達式的建樹過程。BinTree:BinTree(char mid) m_midi=0; / 與mid配合使用的下標變量 m_Root = DoCreate(mid);BinTreeNode* BinTree:DoCreate(char mid) / 初始化最初始的樹（3個結(jié)點） BinTreeNode *root,*opd1,*opd2; if(midm_midi='(') m_midi+; opd1=DoCreate(mid); else opd1=new BinTreeNode; / 第1個運算數(shù)結(jié)點 opd1->type=OPD; opd1->data=midm_midi+-'0' opd1->lchild=opd1->rchild=NULL; root = new BinTreeNode; / 第1個運算符結(jié)點 root->type=OP; root->op=midm_midi+; if(midm_midi='(') m_midi+; opd2=DoCreate(mid); else opd2=new BinTreeNode; / 第2個運算數(shù)結(jié)點 opd2->type=OPD; opd2->data=midm_midi+-'0' opd2->lchild=opd2->rchild=NULL; root->lchild=opd1; root->rchild=opd2; / 每躺循環(huán)增加2個結(jié)點: *op和*opd3 while(midm_midi) if(midm_midi=')') m_midi+; break; BinTreeNode *op=new BinTreeNode; / 運算符結(jié)點 op->type=OP; op->op=midm_midi+; BinTreeNode *opd3; if(midm_midi='(') m_midi+; opd3=DoCreate(mid); else opd3=new BinTreeNode; / 運算數(shù)結(jié)點 opd3->type=OPD; opd3->data=midm_midi+-'0' opd3->lchild=opd3->rchild=NULL; / 比較*root和*op的優(yōu)先級 if(Precede(root->op, op->op)='<') if(Precede(root->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 體會 棧和樹是等價的。作業(yè)與上機1 二叉樹類建立二叉樹類，應(yīng)包含以下成員函數(shù)：構(gòu)造、深度/層次遍歷、查找、深度。方向1：盡可能的豐富二叉樹類的成員函數(shù)；方向2：設(shè)計更多拷貝構(gòu)造函數(shù)（實現(xiàn)類型轉(zhuǎn)換功能），如：將二叉樹的順序結(jié)構(gòu)轉(zhuǎn)換為二/三叉鏈表；將序偶的集合結(jié)構(gòu)轉(zhuǎn)換為二/三叉鏈表；方向3：建立表達式樹類；方向4：其他二叉樹類的應(yīng)用算法：計算寬度、結(jié)點坐標方向5：趣味賽題的程序結(jié)構(gòu)的共性研究；2 二叉線索樹類建立二叉樹線索樹類，應(yīng)包含以下成員函數(shù)：構(gòu)造、某種線索化、遍歷。 方向1：三類線索樹、樹類，構(gòu)成類的繼承體系 方向2：線索樹的插入、刪除等算法3 樹類采用二叉鏈表結(jié)構(gòu)，建立樹類，應(yīng)包含以下成員函數(shù)：構(gòu)造、先/后根遍歷、結(jié)點/樹的度、深度。4 哈夫曼類 采用哈夫曼樹結(jié)構(gòu)，計算哈夫曼編碼；實現(xiàn)壓縮與解壓縮功能。第6章 樹6 線索二叉樹如何快捷地找出結(jié)點在遍歷過程中的前驅(qū)、后繼？如何保存遍歷過程得到的先后次序？方法評價每個結(jié)點增加前驅(qū)域、后繼域。浪費空間利用結(jié)點的空鏈域存儲前驅(qū)指針和后繼指針。問題：如何區(qū)別左孩子指針和前驅(qū)指針？對策：增加標記域。質(zhì)疑：浪費空間？解釋：標記數(shù)據(jù)有許多靈巧的存儲方法。6.1 線索二叉樹的存儲結(jié)構(gòu)中序線索樹示例：6.2 線索二叉樹類/ 二叉線索樹結(jié)點template <class T>struct BinThrTreeNode BinThrTreeNodeType ltype,rtype; T data; BinThrTreeNode<T> *lchild,*rchild;/ 二叉“中序”線索樹的類template <class T>class BinThrTree BinThrTreeNode<T> *m_Root;public: BinThrTree(); BinThrTree(); BinThrTree(vector<T> &pre); / 根據(jù)pre創(chuàng)建二叉樹 void Free(); / 釋放整個樹的空間 void MT_Order(); / 中序線索化 / 求中序遍歷中的后繼、前驅(qū) BinThrTreeNode<T> * MT_GetNext(BinThrTreeNode<T> *p); BinThrTreeNode<T> * MT_GetPrev(BinThrTreeNode<T> *p); void MT_Travese(); / 不使用棧的中序遍歷 / 求父結(jié)點地址 BinThrTreeNode<T> *MT_GetParent(BinThrTreeNode<T> *p);6.3 線索化6.3.1 利用遞歸遍歷程序模式，實現(xiàn)中序線索化設(shè)已有二叉樹所有結(jié)點的ltype、rtype為LINK遍歷指針p依次指向各結(jié)點，m_lastp緊隨其后，指向上一個被訪問的結(jié)點。每次指針變調(diào)整前，進行*p的前驅(qū)線索化、*m_lastp的后繼線索化。template <class T>void BinThrTree<T>:MT_Order() / 中序線索化 if(m_Root=NULL) return; m_lastp=NULL; MT_DoOrder(m_Root); m_lastp->rtype=THREAD; /最后遍歷的是最右下的葉子template <class T>void BinThrTree<T>:MT_DoOrder(BinThrTreeNode<T> *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 );時間/空間復(fù)雜度： 等同于原遍歷算法。6.3.2 利用非遞歸遍歷程序模式注意：在先序、中序、后續(xù)線索化中，最后一個結(jié)點的后繼線索化，需要具體分析。先序、中序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é)點求*p的后繼若p->RTag=THREAD：后繼為*p->rchild 若p->RTag=LINK ：后繼為*p的右子樹中最左下結(jié)點求*p的前驅(qū)若p->LTag=THREAD：前驅(qū)為*p->lchild若p->LTag=LINK ：前驅(qū)為*p的左子樹中最右下結(jié)點/ 求*p的后繼 template <class T>BinThrTreeNode<T>* BinThrTree<T>:MT_GetNext(BinThrTreeNode<T> *p) if(p->rtype=THREAD) return p->rchild; for(p=p->rchild; p->ltype=LINK; p=p->lchild); return p;/ 求*p的前驅(qū) template <class T>BinThrTreeNode<T>* BinThrTree<T>:MT_GetPrev(BinThrTreeNo