【正文】 Ptrright = RNodePtrleft。 RNodePtrleft = DNodePtrleft。 RNodePtrright = DNodePtrright。} } if (PNodePtr == NULL) root = RNodePtr。 else if (DNodePtrdata PNodePtrdata) PNodePtrleft = RNodePtr。 else PNodePtrright = RNodePtr。 FreeTreeNode(DNodePtr)。 size。 } template class T void BinSTreeT::ClearList(void) { DeleteTree(root)。 root = NULL。 current = NULL。 size = 0。 } template class T int BinSTreeT::ListEmpty(void) const { return root == NULL。 } template class T int BinSTreeT::ListSize(void) const { return size。 } // assign node value to item 。 // otherwise, insert item in tree template class T void BinSTreeT::Update(const Tamp。 item) { if (current != NULL amp。amp。 currentdata == item) currentdata = item。 else Insert(item)。 } template class T TreeNodeT *BinSTreeT::GetRoot(void) const { return root。 } endif // BINARY_SEARCH_TREE_CLASS 測試練習(xí) 1。用二叉搜索樹為一個數(shù)列排序， 分別用前序和后序再輸出。 2。鍵盤輸入若干個字符串，排序后輸出。 3。在輸入的字符串中刪除兩個串，再輸出。 練習(xí) 一 . 畫出以下輸入所對應(yīng)二叉搜索樹： 1） R,O,T,A,R,Y,C,L,U,B 2） 60， 25， 7， 99， 15， 3， 10 38， 59， 62， 34 二 . 分別給出這兩棵樹的前序，中序， 后序遍歷輸出 練習(xí) 一棵二叉樹，先序序列為 EBADCFHGIKJ 中序序列為 ABCDEFGHIJK 畫出這棵樹 五、樹的計數(shù) 有 n個結(jié)點的不同形態(tài)的二叉樹有多少？ 不考慮結(jié)點的數(shù)據(jù)的異同 樹 T和 T’相似： T和 T’都是空樹或兩者都不是空樹且 左右子樹分別相似。 設(shè) n個結(jié)點互不相似的二叉樹的數(shù)目為 bn 則 b0=1, b1=1, b2=2。 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。 √14x )/2x 由 limx→0 B(x)=b0=1 B(x)=(1－ √14x )/2x B(x)=(1－ √14x )/2x 設(shè) f(x)=√14x =(14x)1/2 f(x)的戴勞展開式 f(x) =a0+a1x+a2x2++anxn+ an=f(n)(0)/n! a0=1 a1=(1/2)(4) a2=(1/2)(1/2－ 1)(4)2/2! an=(1/2)(1/2－ 1)(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－ (n－ 1))(4)n/n!, n≥1 記 C1/2k= (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)n22nC1/2nxn+ B(x)=(1－ √14x )/2x ＝２ C1/21－ 23C1/22x ++(1)n122n1C1/2nxn1+ B(x)=b0+ b1x+b2x2++bnxn+ 比較系數(shù)得到 b0=1, b1=－ 23C1/22, bn1=(1)n122n1C1/2n, bn=(1)n22n+1C1/2n+1. B(x)＝２ C1/21－ 23C1/22x ++(1)n122n1C1/2nxn1+ bn=(1)n22n+1C1/2n+1 b0=1, b1=(1)23C1/22=(1)23(1/2)(1/2－ 1)/2!=1 b2=(1)225C1/23=25(1/2)(1/2－ 1)(1/2－ 2)/3! =25(1/2)(1/2)(3/2)/3!=22*1*3/3!=2 b3=(1)327C1/24=27(1/2)(1/2)(3/2)(5/2)/4!=5 =23*1*3*5/4!=(1/4)(23*1*3*5*1*2*3)/(3!*3!) =(1/4)(1*3*5*2*4*6)/(3!*3!) =(1/4)6!/(3!*3!)=1/4*C63 bn=(1)n22n+1C1/2n+1 =(1)n22n+1 2 1 ( 2 1 － 1) ( 2 1 － 2) ( 2 1 － n) (n+1)! =2n 1*3*5**(2n1) (n+1)n! *n! *n! = n+1 1 n!n! (2n)! = n+1 1 C2nn n+1 1 C2nn bn= b3= 4 1 C63 = 4 6! *3!*3! =5 b4= 5 1 C84 = 5 8! *4!*4! =14 b5= 6 1 C105 = 6 10! *5!*5! =42 b6= 7 1 C126 = 7 12! *6!*6! = 8*9*10*11*12 1*2*3*4*5*6 =132 n+1 1 C2nn bn= C2nn－ C2nn1= (2n)! n!*n! － (2n)! (n1)!*(n+1)! = (2n)! n!*(n+1)! C2nn n+1 1 C2nn = n+1 1 C2nn bn= =C2nn－ C2nn1 樹的計數(shù) 樹可以轉(zhuǎn)換成唯一的二叉樹 即不同的樹轉(zhuǎn)換成不同的二叉樹 不同的二叉樹也可以轉(zhuǎn)換成不同的樹 只要根結(jié)點沒有左子樹 因此 n個結(jié)點的樹與 n1個結(jié)點的二叉樹 的數(shù)目相同 tn=bn1 t1=1 t2=1 t3=2 t4=b3 n個元素進棧，有多少不同的出棧方法 記 n個元素進棧有 bn種出棧法 設(shè) n個元素為 a1,a2,,an ak+1 a3 a2 a1 設(shè) a1在第 k+1個元素出棧 ai1ai2aika1aj1aj2ajnk1 a1前 k個元素有 bk種排法 a1后 nk1個元素有 bnk1種排法，共有 bk*bnk1種排法 得到遞推關(guān)系 bn=Σbkbnk1 k=0 n1 n個元素進棧，有多少不同的出棧方法 記 n個元素進棧有 bn種出棧法 bn=Σbkbnk1 k=0 n1 n+1 1 C2nn bn= =C2nn－ C2nn1 六、樹和森林 若干棵樹組成森林 樹的存儲結(jié)構(gòu) ?雙親表示法 ?孩子表示法 ?孩子兄弟表示法 雙親表示法 用 數(shù)組 存儲樹的結(jié)點 每個結(jié)點中附設(shè)一個字段 指示其父結(jié)點的位置 A B C D E F G H I J 0 1 2 3 4 5 6 7 8 9 A 1 B 0 C 0 D 0 E 1 F 1 G 3 H 6 I 6 J 6 雙親表示法結(jié)點定義 define MAX_TREE_SIZE 100 template class T class PNode { T data。 int Parent。 public: PNode(T item, int pr)。 T GetData( )。 int GetParent( )。 } } 樹的雙親表示法定義 template class T class PTree { PNodeT nodes[MAX_TREE_SIZE]。 int n。 //number of nodes public: PTree( int m=0)。 PNodeT operator[ ](int i)。 int PTreeInsert(T item, int pr)。 T PTreeDelete(int i)。 int PTreeSize( )。 } 孩子表示法 1. k叉樹結(jié)點表示 (固定長結(jié)點） A B C D E F G H I data child1 child2 childk A B C D E F G H I 孩子表示法 1. k叉樹結(jié)點表示 (固定長結(jié)點） A B C D E F G H I J 2. 變長結(jié)點表示 data degree child1 child2 childk A 3 B 2 C 0 D 1 E 0 F 0 G 2 H 0 I 0 孩子表示法 1. k叉樹結(jié)點表示 (固定長結(jié)點） A B C D E F G H I 2. 變長結(jié)點表示 3. 孩子鏈表表示 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 孩子鏈表表示結(jié)點類的定義 struct ChildNode //child node { int child。 ChildNod