【正文】 57 15 20 60 59 50 1. D是 葉 令 R=NULL。即可。 Pright=R。 Pleft=R。R=Dleft。 2. Q!=D Qright=Rleft。R=Dleft。 再用 R代替 D : Q 有兩種情況： 1. Q==D Rright=Dright。 Rleft=Dleft。 item) {TreeNodeT *DNodePtr, *PNodePtr, *RNodePtr。 if (DNodePtrright == NULL) RNodePtr = DNodePtrleft。 else {TreeNodeT *PofRNodePtr = DNodePtr。 while(RNodePtrright != NULL) { PofRNodePtr = RNodePtr。 } if (PofRNodePtr == DNodePtr) RNodePtrright = DNodePtrright。 RNodePtrleft = DNodePtrleft。} } if (PNodePtr == NULL) root = RNodePtr。 else PNodePtrright = RNodePtr。 size。 root = NULL。 size = 0。 } template class T int BinSTreeT::ListSize(void) const { return size。 // otherwise, insert item in tree template class T void BinSTreeT::Update(const Tamp。amp。 else Insert(item)。 } endif // BINARY_SEARCH_TREE_CLASS 測(cè)試練習(xí) 1。 2。 3。 練習(xí) 一 . 畫(huà)出以下輸入所對(duì)應(yīng)二叉搜索樹(shù)： 1） R,O,T,A,R,Y,C,L,U,B 2） 60， 25， 7， 99， 15， 3， 10 38， 59， 62， 34 二 . 分別給出這兩棵樹(shù)的前序，中序， 后序遍歷輸出 練習(xí) 一棵二叉樹(shù)，先序序列為 EBADCFHGIKJ 中序序列為 ABCDEFGHIJK 畫(huà)出這棵樹(shù) 五、樹(shù)的計(jì)數(shù) 有 n個(gè)結(jié)點(diǎn)的不同形態(tài)的二叉樹(shù)有多少？ 不考慮結(jié)點(diǎn)的數(shù)據(jù)的異同 樹(shù) T和 T’相似： T和 T’都是空樹(shù)或兩者都不是空樹(shù)且 左右子樹(shù)分別相似。 b1=1 b2=2 b3=5=b2*b0+b1*b1+b0*b2 b0=1 , b1=b0*b0=1, b2=b0*b1+b1*b0=2, b3=b0*b2+b1*b1+b2*b0=5, b4=b0*b3+b1*b2+b2*b1+b3*b0 =1*5+1*2+2*1+5*1=14, b5= b0*b4+b1*b3+b2*b2+b3*b1+b4b0 =1*14+1*5+2*2+5*1+14*1=42 , 遞推關(guān)系 bn=Σbibni1 i=0 n1 b0, b1,b2,bn, 定義： B(x)=b0+ b1x+b2x2++bnxn+ 則 B2(x)=b0b0+ (b0 b1+b1b0)x+(b0b2+b1b1+b2b0)x2+ = b1+b2x+b3x2+ xB2(x)= b1x+b2x2+b3x3+ xB2(x) =B(x)1 xB2(x) =B(x)1 xB2(x) B(x)+1=0 解方程 B(x)=(1177。(1/2－ (n－ 1))(4)n/n! 設(shè) f(x)=√14x =(14x)1/2 f(x) =a0+a1x+a2x2++anxn+ an=(1/2)(1/2－ 1)(1/2－ (k－ 1))/k! an= C1/2n(4)n=(1)n22nC1/2n f(x) =1－ 4C1/21x+ 24C1/22x2++(1)n122n1C1/2nxn1++(1)n122n1C1/2nxn1+ ( 2 1 － n) (n+1)! =2n 1*3*5*aika1aj1aj2 int Parent。 T GetData( )。 } } 樹(shù)的雙親表示法定義 template class T class PTree { PNodeT nodes[MAX_TREE_SIZE]。 //number of nodes public: PTree( int m=0)。 int PTreeInsert(T item, int pr)。 int PTreeSize( )。 ChildNode *next。 template class T struct CTNode { T data。}。 int n。 帶雙親的 A B C D E F G H I 0 1 2 3 4 5 6 7 8 A B C ^ D E ^ F ^ G H ^ I ^ 1 2 3 7 8 4 5 6 0 1 2 3 4 5 6 7 8 1 0 0 0 1 1 3 5 5 孩子表示法 孩子兄弟表示法（ 二叉樹(shù)表示法 ） 結(jié)點(diǎn) : 數(shù)據(jù) 孩子 兄弟 A B C D E F G H I data firstchild nextsibling A B C D E F G H I 孩子兄弟表示法（ 二叉樹(shù)表示法 ） 結(jié)點(diǎn) : 數(shù)據(jù) 孩子 兄弟 A B C D E F G H I data firstchild nextsibling A B C D E F G H I //孩子兄弟表示 結(jié)點(diǎn)類(lèi)的定義 template class T CSTree。 CSNodeT *firstChild, *nextSibling。 friend class T CSTree。 //孩子兄弟表示 類(lèi)的定義 template class T class CSTree { CSNodeT *root, *current。 CSNodeT *GetCSNode(const Tamp。 void FreeCSNode(CSNodeT *p)。 void DeleteTree(CSNodeT *t)。 item, CSNodeT* amp。 public: CSTree(void)。 tree)。 CSTreeTamp。 rhs)。 item)。 item)。 item)。 int ListEmpty(void) const。 void Update(const Tamp。 CSNodeT *GetRoot(void) const。 森林與二叉樹(shù)的轉(zhuǎn)換 A B C D E F G H I J A B C D E F G H I J 森林與二叉樹(shù)的轉(zhuǎn)換的形式定義 ?森林 轉(zhuǎn)換成 二叉樹(shù) 的 規(guī)則： 設(shè) F={T1,T2,T1m}轉(zhuǎn)換成的二叉樹(shù)； RB是森林 F’={T2,T3, 二叉樹(shù) 轉(zhuǎn)換成 森林 的規(guī)則： （遞歸定義） 設(shè) B={root, LB, RB}是二叉樹(shù) 可以轉(zhuǎn)換成森林 F={T1,T2,T1m} 是 LB轉(zhuǎn)換成的； 森林 F’={T2,T3, 樹(shù)的遍歷 （與二叉樹(shù)不同） 深度優(yōu)先 1。 2。 二叉樹(shù)的先根遍歷就是先序遍歷 后根遍歷就是后序遍歷 廣度優(yōu)先 ?先訪問(wèn)根結(jié)點(diǎn) ?再依次訪問(wèn)第一層所有結(jié)點(diǎn) ?再依次訪問(wèn)第二層所有結(jié)點(diǎn) 直到訪問(wèn)完所有結(jié)點(diǎn) 先根遍歷 ABEFCDGHI A B C D E F G H I 后根遍歷 EFBCHIGDA 廣度優(yōu)先 ABCDEFGHI 先根遍歷的算法 void PreOrderTraverse(CSNodeT*t,void visit(T item)) { if(t!=NULL) { visit(tdata)。 PreOrderTraverse(tnextSibling,visit)。 轉(zhuǎn)換成二叉樹(shù)后 與二叉樹(shù)的先序遍歷相同 中序遍歷森林 若森林非空 中序遍歷第一棵樹(shù)根的子森林 訪問(wèn)第一棵樹(shù)的根 中序遍歷去掉第一棵樹(shù)后剩余的子森林 轉(zhuǎn)換成二叉樹(shù)后與二叉樹(shù)的中序遍歷相同 后序遍歷森林 若森林非空 后序遍歷第一棵樹(shù)根的子森林 后序遍歷去掉第一棵樹(shù)后剩余的子森林 訪問(wèn)第一棵樹(shù)的根 轉(zhuǎn)換成二叉樹(shù)后與二叉樹(shù)的后序遍歷相同 先序遍歷 A B C D E F G H I J ABCDEFGHIJ 中序遍歷 BCDAFEHJIG 后序遍歷 DCBFJIHGEA A B C D E F G H I J 先序遍歷 ABCDEFGHIJ 中序遍歷 BCDAFEHJIG 后序遍歷 DCBFJIHGEA 七、堆 Heap (改進(jìn)了的樹(shù)型排序） （極?。?堆的定義： n個(gè)元素的完全二叉樹(shù)，每個(gè)結(jié)點(diǎn)都小于其子結(jié)點(diǎn)。 先作第二步：輸出并調(diào)整重建堆 13 49 27 97 65 76 38 輸出堆頂元素 13，用堆末元素取代， 將元素 76下移與子結(jié)點(diǎn)中較小的一個(gè)交換， 向下過(guò)濾， 直至葉結(jié)點(diǎn)，重復(fù)第 2步直至全部輸出。 int inArray。 int heapsize。 // utility functions for Delete/Insert to restore heap void FilterDown(int i)。 public: Heap(int maxsize)。 // heapify arr Heap(const HeapTamp。 // copy constructor ~Heap(void)。 operator= (const HeapTamp。 const Tamp。 // list methods int ListSize(void) const。 int ListFull(void) const。 item)。 void ClearList(void)。 // print error message and terminate the program template class T void HeapT::error(char errmsg[]) { cerr errmsg endl。 } template class T void HeapT::FilterDown (int i) { int currentpos, childpos。 // start at i and set its value as the target currentpos = i。 childpos = 2 * i + 1。a