【正文】 DeleteTree(root)。 } template class T int BinSTreeT::ListEmpty(void) const { return root == NULL。 item) { if (current != NULL amp。 } template class T TreeNodeT *BinSTreeT::GetRoot(void) const { return root。鍵盤輸入若干個(gè)字符串，排序后輸出。 設(shè) n個(gè)結(jié)點(diǎn)互不相似的二叉樹的數(shù)目為 bn 則 b0=1, b1=1, b2=2。 √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+ an=f(n)(0)/n! a0=1 a1=(1/2)(4) a2=(1/2)(1/2－ 1)(4)2/2! (1/2－ (n－ 1))(4)n/n!, n≥1 記 C1/2k= (1/2)(1/2－ 1) B(x)=(1－ √14x )/2x ＝２ C1/21－ 23C1/22x ++bnxn+ 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) ,an ak+1 a3 a2 a1 設(shè) a1在第 k+1個(gè)元素出棧 ai1ai2 public: PNode(T item, int pr)。 int n。 T PTreeDelete(int i)。 childk A B C D E F G H I 孩子表示法 1. k叉樹結(jié)點(diǎn)表示 (固定長(zhǎng)結(jié)點(diǎn)） A B C D E F G H I J 2. 變長(zhǎng)結(jié)點(diǎn)表示 data degree child1 child2 }。 template class T class CTree { CTNodeT node[MAX_TREE_SIZE]。 template class T class CSNode { public: T data。 }。 item, CSNodeT *fcptr,CSNodeT *nsptr)。 CSNodeT *FindNode(const Tamp。 CSTree(const CSTreeTamp。 operator= (const CSTreeTamp。 void Insert(const Tamp。 void ClearList(void)。 item)。,Tm}轉(zhuǎn)換成的二叉樹。Tm}， (1) B是空樹，則 F空； (2) B非空， 則 m≠0, T1的根 =root ， T1去掉根后的子樹組成的 森林 F1={T11,T12, 先根遍歷 先訪問根結(jié)點(diǎn)， 再先根遍歷根的每一棵子樹。 PreOrderTraverse(tfirstChild,visit)。 13 49 27 97 65 76 38 用一維數(shù)組表示極小堆 0 1 2 3 4 5 6 13 49 27 97 65 38 76 13 49 27 97 65 76 38 A[i] ≤A[2i+1], A[i] ≤A[2i+1+1], 堆排序 堆排序的過程 ， 2. 輸出頂點(diǎn)元素后，調(diào)整并重建堆， 3. 重復(fù) 。 // max number allowed and current size of heap int maxheapsize。 void FilterUp(int i)。 H)。 rhs)。 int ListEmpty(void) const。 T Delete(void)。 exit(1)。 target = hlist[i]。 (hlist[childpos+1] = hlist[c。 while (childpos heapsize) // check for end of list { if ((childpos+1 heapsize) amp。 T target。 }。 void Insert(const Tamp。 operator[](int i)。 // destructor // overloaded operators: =, [], T* HeapTamp。 // create empty heap Heap(T arr[],int n)。 // identifies end of list // error message utility function void error(char errmsg[])。 76 13 76 76 7627 27 76 76 76 38 7638第一步 建堆 從最末一個(gè)非葉結(jié)點(diǎn) A[n1/2]開始 向下過濾 直至堆頂 49 38 65 97 76 27 13 49 49971365 13 494927include include template class T class Heap {private: T *hlist。 } } 森林的遍歷 先序遍歷森林 若森林非空 先訪問第一棵樹的根結(jié)點(diǎn)， 再先序遍歷第一棵樹根的子森林， 再先序遍歷除去第一棵樹后剩余 的子森林。 后根遍歷 先后根遍歷根的每一棵子樹， 再訪問根。,Tm} 是 RB轉(zhuǎn)換成的。Tm}是森林， 可以轉(zhuǎn)換成二叉樹 B={root, LB, RB} (1) F空， m=0, 則 B是空樹； (2) F非空， m≠0, 則 root=T1的根， LB是 T1去掉根后的子樹組成的森林 F1={T11,T12, }。 int ListSize(void) const。 void Delete(const Tamp。 int Find(Tamp。 ~CSTree(void)。 pre) const。 CSNodeT *CopyTree(CSNodeT *t)。 int size。 CSNode( T item=0, CSNodeT*fc=NULL, CSNodeT*ns=NULL)。 ……}。 ChildNode *firstChild。 childk A 3 B 2 C 0 D 1 E 0 F 0 G 2 H 0 I 0 孩子表示法 1. k叉樹結(jié)點(diǎn)表示 (固定長(zhǎng)結(jié)點(diǎn)） A B C D E F G H I 2. 變長(zhǎng)結(jié)點(diǎn)表示 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é)點(diǎn)類的定義 struct ChildNode //child node { int child。 } 孩子表示法 1. k叉樹結(jié)點(diǎn)表示 (固定長(zhǎng)結(jié)點(diǎn)） A B C D E F G H I data child1 child2 PNodeT operator[ ](int i)。 int GetParent( )。ajnk1 a1前 k個(gè)元素有 bk種排法 a1后 nk1個(gè)元素有 bnk1種排法，共有 bk*bnk1種排法 得到遞推關(guān)系 bn=Σbkbnk1 k=0 n1 n個(gè)元素進(jìn)棧，有多少不同的出棧方法 記 n個(gè)元素進(jìn)棧有 bn種出棧法 bn=Σbkbnk1 k=0 n1 n+1 1 C2nn bn= =C2nn－ C2nn1 六、樹和森林 若干棵樹組成森林 樹的存儲(chǔ)結(jié)構(gòu) ?雙親表示法 ?孩子表示法 ?孩子兄弟表示法 雙親表示法 用 數(shù)組 存儲(chǔ)樹的結(jié)點(diǎn) 每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)字段 指示其父結(jié)點(diǎn)的位置 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é)點(diǎn)定義 define MAX_TREE_SIZE 100 template class T class PNode { T data。*(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 樹的計(jì)數(shù) 樹可以轉(zhuǎn)換成唯一的二叉樹 即不同的樹轉(zhuǎn)換成不同的二叉樹 不同的二叉樹也可以轉(zhuǎn)換成不同的樹 只要根結(jié)點(diǎn)沒有左子樹 因此 n個(gè)結(jié)點(diǎn)的樹與 n1個(gè)結(jié)點(diǎn)的二叉樹 的數(shù)目相同 tn=bn1 t1=1 t2=1 t3=2 t4=b3 n個(gè)元素進(jìn)棧，有多少不同的出棧方法 記 n個(gè)元素進(jìn)棧有 bn種出棧法 設(shè) n個(gè)元素為 a1,a2, 比較系數(shù)得到 b0=1, b1=－ 23C1/22, bn1=(1)n122n1C1/2n, bn=(1)n22n+1C1/2n+1. B(x)＝２ C1/21－ 23C1/22x + B(x)=b0+ b1x+b2x2+ + (1)n22nC1/2nxn+ an=(