【正文】 } template class T void BTreeT::dest(BTreeNodeT *p) { if (p!=NULL ) { dest(plchild)。 bt) {dest(root)。 (2)調(diào)用相應(yīng)的遞歸函數(shù)來完成二叉樹的拷貝 。 其處理過程為： (1)釋放已分配的存儲(chǔ)空間 。 } 61 復(fù)制二叉樹：拷貝函數(shù) void copybt(BTreeTamp。 bt) 功能：將指定的二叉樹與求當(dāng)前的二叉樹進(jìn)行比較 ， 若相等則返回 true否則返回 false， template class T bool BTreeT::equal(BTreeTamp。 return(b)。amp。amp。 else if(p==NULL || q==NULL)b=false。amp。 template class T bool BTreeT::equal(BTreeNodeT *p,BTreeNodeT *q) {bool b。 } } 實(shí)例函數(shù)求當(dāng)前對(duì)象中的高度： template class T int BTreeT::dep() { return(dep(root))。 if (dep(prchild)max) max=dep(prchild)。 if(p==NULL)return(0)。 } 57 互動(dòng)環(huán)節(jié) :計(jì)算二叉樹的高度 int dep(BTreeNodeT *p) 功能 :返回 p所指向的二叉樹的高度 ， 其處理過程為： (1)若 p為 NULL則返回 0， 否則； (2)求出左 、 右子樹的高度 l l2并返回 max(l1+ l2)+1。 else return(num(plchild)+num(prchild)+1)。 } else return(NULL)。 prchild=build0(r)。 r=2*i+1。 pdata=a[i1]。 39。amp。 int l,r。 (3) 以 2*i+1為參數(shù) ， 調(diào)用 build0創(chuàng)建右子樹 ， 并掛在該結(jié)點(diǎn)的右支上 。 其處理過程為： (1) 若序號(hào)為 i的數(shù)組元素存在 ， 即 i小于等于數(shù)組的長度且數(shù)組的第 i個(gè)元素非空 ， 則創(chuàng)建一個(gè)結(jié)點(diǎn)作為根結(jié)點(diǎn) ， 在其數(shù)據(jù)域中存放數(shù)組的第 i個(gè)元素 。 root=build0(1)。 53 建立二叉鏈表 D H I lchild data rchild A B C F G A B C D F G H I 54 建立二叉鏈表 構(gòu)造函數(shù) template class T BTreeT:: BTree(T a[],int n) { thisa=a。 static void preorder(BTreeNodeT *p,void visit(BTreeNodeT *p))。p, BTreeNodeT *q)。 bt)。 static bool equal(BTreeNodeT *p, BTreeNodeT *q)。 bool equal(BTreeamp。 int dep()。 int num()。}。 protected: BTreeNodeT *root。 int n。 }。 BTreeNodeT *getleft(){return lchild}。 T getdata(){return data。 public: BTreeNode():lchild(NULL),rchild(NULL){}。 T data。 template class T class BTreeNode { friend class BTree T。 }； A B C D E lchild data rchild 51 二叉樹結(jié)點(diǎn)類的定義 template class T class BTree。 }； 三叉鏈表 ： struct BTreeNode { T data。 A B C D E A B C D E 50 二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 二叉鏈表 ： struct BTreeNode { T data。 49 二叉樹的存儲(chǔ)結(jié)構(gòu) 一維數(shù)組表示法： 用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)二叉樹的數(shù)據(jù)元素 。 ② 若 2i≤n， 則序號(hào)為 i的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的序號(hào)為 2i； 若 2i n， 則序號(hào)為 i的結(jié)點(diǎn)無左孩子 。 一個(gè)深度為 K具有 N個(gè)節(jié)點(diǎn)的二叉樹 ， 若其節(jié)點(diǎn)的編號(hào)與深度為 K的滿二叉樹編號(hào)為 1－ n的節(jié)點(diǎn)完全對(duì)應(yīng) ， 則稱之為完全二叉樹 47 完全二叉樹的基本性質(zhì) 高度規(guī)律 具有 n 0個(gè)結(jié)點(diǎn)的完全二叉樹的高度 k= ? log2n+1 ?。滿二叉樹的特點(diǎn)就是每層的結(jié)點(diǎn)數(shù)目都達(dá)到該層的最大結(jié)點(diǎn)數(shù) 。 （空） 43 二叉樹的基本性質(zhì) 1 任意非空二叉樹中 ， 若葉結(jié)點(diǎn)的數(shù)目為 n0， 度為 2的結(jié)點(diǎn)數(shù)目為 n2， 則有關(guān)系： n0= n2+1 證明： 二叉樹的結(jié)點(diǎn)總數(shù) n為 n= n0+n1+n2 n=B+1= n1+2n2+1 所以 n0+n1+n2 = n1+2n2+1 即 n0= n2+1 44 二叉樹的基本性質(zhì) 2 一棵非空二叉樹的第 i層最多有 2 i1個(gè)結(jié)點(diǎn) (i≥ 1) 1 1=20 2 2=21 3 4=22 …… …… i 2 i1 45 二叉樹的基本性質(zhì) 3 高度為 k的二叉樹最多有 2k1個(gè)結(jié)點(diǎn) (k≥ 1) 顯然 ， 高度為 k的二叉樹只有在每一層都達(dá)到最大結(jié)點(diǎn)數(shù)時(shí) ， 整個(gè)二叉樹的結(jié)點(diǎn)數(shù)才能達(dá)到最大 。 遞歸定義為：二叉樹或者是一棵空樹 ， 或者是一棵由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的左子樹和右子樹所組成的非空樹 ， 左子樹和右子樹又同樣都是二叉樹 。 上述敘述就是樹與森林的遞歸 定義 41 二叉樹的定義 二叉樹 (binary tree)是指樹的度為 2的有序樹 。 森林 森林是 m(m≥ 0)棵互不相交的樹的集合 。 樹中結(jié)點(diǎn)的最大層數(shù)稱為樹的深度 (depth)或高度 (height)。 結(jié)點(diǎn)的層數(shù)和樹的高度 樹既是一種遞歸結(jié)構(gòu) ， 也是一種層次結(jié)構(gòu) ， 樹中的每個(gè)結(jié)點(diǎn)都處在一定的層次上 。 39 樹的基本術(shù)語 兒結(jié)點(diǎn) 、 父結(jié)點(diǎn)和兄弟結(jié)點(diǎn) 每個(gè)結(jié)點(diǎn)的子樹的根 ， 或者說每個(gè)結(jié)點(diǎn)的后繼 ，被習(xí)慣地稱作該結(jié)點(diǎn)的 兒結(jié)點(diǎn) (child)， 相應(yīng)地 ，該結(jié)點(diǎn)被稱作 兒結(jié)點(diǎn) 的 父結(jié)點(diǎn) 。 所有結(jié)點(diǎn)的度的最大值被定義為該樹的度 。 由此可見 ， 樹的定義是一個(gè)遞歸定義 。 當(dāng) n＝ 0時(shí)稱為空樹 。 } 程序的運(yùn)行結(jié)果如下： (a,(b,c)) (x,y,((z))) (a,(b,c)) ((a,(b,c))， x,y,((z))) (x,y,((z))) dep=3 34 后記 ? 結(jié)束 35 版權(quán)所有 , 1997 (c) Dale Carnegie amp。 ()。()。 ()。 ()。 ()。 void main( ) {String st1=(a,(b,c)),st2=(x,y,((z)))。 }。 實(shí)例函數(shù) void GList::prnt() { prnt(ls)。 } else coutlsdata。 cout39。 p=ptp。,39。 p=lstp。(39。 if (ls == NULL ) cout()。 (3)重復(fù)過程 (2)的處理 ， 直至所有的成員都處理完 ， 最后再輸出一個(gè) ‘ )’ 。并輸出該廣義表的第一個(gè)成員 。 } 30 建立廣義表的存儲(chǔ)結(jié)構(gòu) 建立廣義表的存儲(chǔ)結(jié)構(gòu) 書寫形式 st=‘(a,b)’ 1 0 b 0 a 1 ? prnt(ls) ls 存儲(chǔ)形式 crtlists(st， ls) 31 打印廣義表 void prnt(GListNode *ls) 其中參數(shù) ls表示已建立存儲(chǔ)結(jié)構(gòu)的廣義表 ， 其類型為廣義表的結(jié)點(diǎn)指針類型 ， 該函數(shù)的功能是以書寫形式輸出廣義表 ls。 GList::GList(GListamp。 } } } 拷貝構(gòu)造函數(shù)涉及到當(dāng)前對(duì)象 ， 所以僅設(shè)置一個(gè)參數(shù) GListamp。 else {copyls(ls1hp, ls2hp )。 ls1tag=ls2tag。ls1,GListNode* ls2) { if (ls2==NULL ) ls1=NULL。 復(fù)制表頭并將新表頭的指針掛在新生結(jié)點(diǎn)的頭指針域上由 copyls(ls1hp, ls2hp)來完成 ， 復(fù)制表尾并將新表尾的指針掛在新生結(jié)點(diǎn)的尾指針域上由 copyls(ls1tp,ls2tp)來完成 。 其處理過程為： (1) 若 ls1為 NULL則 ls2也為 NULL,否則： (2) 創(chuàng)建一個(gè)廣義表結(jié)點(diǎn) ， 并按原表是單元素或列表二種情形分別處理 。ls1,GListNode* ls2) 功能：復(fù)制廣義表 ls2的一個(gè)副本并由 ls1指向該廣義表的頭結(jié)點(diǎn) 。 } 28 廣義表遞歸算法互動(dòng)環(huán)節(jié)： 廣義表復(fù)制 設(shè)計(jì)一個(gè)拷貝構(gòu)造函數(shù) ， 其功能為按一個(gè)指定的廣義表來創(chuàng)建一個(gè)新的廣義表 。 else return(h+1)。 t=depth(lstp)。 else if (lstag==0 ) return(0)。 27 求廣義表的深度 int GList::depth(GListNode *ls) {int h,t。 26 求廣義表的深度 int depth( GListNode *ls ) 其中參數(shù) ls表示指定的廣義表的結(jié)點(diǎn)指針 ， 該函數(shù)的功能為：求由結(jié)點(diǎn)指針 ls 所指向的廣義表的深度 ， 并作為函數(shù)值返回之 。 depth((a,(b,c,d)))=2。 } 25 求廣義表的深度 定義： 對(duì)于廣義表 ls=(a1,a2,… , ai ,… ,an) 當(dāng) ls為單元素時(shí) ， depth(ls)=0； 當(dāng) ls為空表時(shí) ， depth(ls)=1； 否則 ， depth(ls)= max(1=i=n) {depth(ai)} + 1； 可以作簡單的理解： 廣義表的深度定義為廣義表中括號(hào)的層數(shù) 例如： depth(())=1。 bool GList::member(GListamp。 gyb2) 該函數(shù)是判別當(dāng)前廣義表中是否含有與另一個(gè)指定的廣義表相同的成員 ， 所以僅設(shè)置一個(gè)參數(shù) GListamp。 return(b1 || b2)。 else {b1=equal(ls1hp, ls2)。 bool GList::member(GListNode* ls1,GListNode* ls2) { bool b1,b2。 } 23 成員判別 bool member(GListNode* ls1,GListNode* ls2) 功能：判別 ls2是否為 ls1的成員 ， 若是則返回函數(shù)值 true， 否則返回函數(shù)值 false。 bool GList::equal(GListamp。 gyb2。 } } 22 相等比較 實(shí)例函數(shù) 上述 equal函數(shù)是靜態(tài)成員函數(shù) ， 它不涉及當(dāng)前對(duì)象 ， 而 equal函數(shù)的另一種形式是實(shí)例函數(shù) ， 涉及到當(dāng)前對(duì)象 ， 其形式如下： bool equal(GListamp。amp。 b2=equal(ls1tp, ls2tp)。 else return(false)。 else if (ls1tag != ls2tag )return(false)。 ls2==NULL ) return(true)。 if (ls1==NULL amp。 若 tag相等且為 1， 則通過遞歸調(diào)用比較表頭與表尾是否都相同 ， 并返回一個(gè)相應(yīng)的函數(shù)值 。 處理過程： (1)對(duì)一些特殊情形作處理：若兩者都為 NULL， 則返回 true,若一方 NULL而另一方不為 NULL或兩者 tag不相等則返回 false。 (3)若 tag相等且為 0， 則可比較結(jié)點(diǎn)中的 data。 若相等則返回函數(shù)值 true， 否則返回函數(shù)值 false。 歸納項(xiàng)描述了如何實(shí)現(xiàn)從當(dāng)前狀態(tài)到終結(jié)狀態(tài)的轉(zhuǎn)化