【正文】 //left pointer point to its self either else { thrtleft=tree。thrt, ThreadNodeT* tree) { ThreadNodeT *pre。 Postorder(root,print)。 item) {coutitem。 item)) {QueueTreeNodeT* Q。 CreateTree(l)。 DeleteTree(tRight())。 if (t == NULL) return NULL。 tRight( ) == NULL) count++。 item)) { // the recursive scan terminates on a empty subtree if (t != NULL) { Postorder (tLeft( ), visit)。 // descend right } } A B C D E F G I H Preorder(root,print)。 p3=GetTreeNode(‘+’,a,p2)。 a = GetTreeNode(39。F39。)。 A B C D E F G I H case 2: g = GetTreeNode(39。 c = GetTreeNode(39。E39。)。,b, c)。 b = GetTreeNode(39。 } void MakeCharTree(TreeNodechar* amp。 } // method Left allows the user //to reference the right child template class T TreeNodeT* TreeNodeT::Right(void) const { // return the private member value right return right。 TreeNodeT* Left(void) const。 SqBiTree bt。第四層 樹的 深度 為 4 A B C D E F G H I J 每個(gè)結(jié)點(diǎn)至多有兩棵子樹 ,1度或 2度 深度為 k，結(jié)點(diǎn)至多 2k1個(gè) 第 i層結(jié)點(diǎn)至多 2i1個(gè) 設(shè)有 n2個(gè) 2度點(diǎn) 則有 n2+1個(gè)葉片 A B C D E F G H I J A B C D E F G H I J 滿二叉樹 K L M N O 深度為 k,結(jié)點(diǎn)數(shù) 2k1,每層結(jié)點(diǎn)數(shù)都最大 滿二叉樹 滿二叉樹去掉最下層最右邊若干結(jié)點(diǎn) 滿二叉樹也是完全二叉樹 完全二叉樹 A B C D E F G H I J K L M N O A B C D E F G H I J 完全二叉樹 K L M n個(gè)結(jié)點(diǎn) ,深度 k=[log2n] +1 n個(gè)結(jié)點(diǎn) ,深度為 k: 2k11＜ n≤2k1 2k1 ≤ n ＜ 2k k1 ≤ log2n ＜ k k1 = [log2n] k = [log2n] +1 1個(gè)結(jié)點(diǎn)深度為 1 23個(gè)結(jié)點(diǎn)深度為 2 47個(gè)結(jié)點(diǎn)深度為 3 815個(gè)結(jié)點(diǎn)深度為 4 1 2 3 4 5 6 7 8 9 10 完全二叉樹 11 12 13 結(jié)點(diǎn) i的左子結(jié)點(diǎn)是 2i 右子結(jié)點(diǎn)是 2i+1 結(jié)點(diǎn) i的父結(jié)點(diǎn)是 [i/2] 二叉樹的存儲(chǔ) 1. 完全二叉樹的順序存儲(chǔ) define MaxTreeSize 100 typedef TElemType SqBiTree[MaxTreeSize]。 virtual ~TreeNode(void)。 item, TreeNodeT *lptr, TreeNodeT *rptr): data(item), left(lptr), right(rptr) {} // method Left allows the user // to reference the left child template class T TreeNodeT* TreeNodeT::Left(void) const { // return the private member value left return left。 } 建立一個(gè)結(jié)點(diǎn) 撤銷一個(gè)結(jié)點(diǎn) template class T void FreeTreeNode(TreeNodeT *p) { delete p。)。A39。H39。 e = GetTreeNode(39。,d, e)。 break。I39。 f = GetTreeNode(39。,e, f)。 p2=GetTreeNode(‘*’,b,p1)。 // descend left Preorder (tRight( ), visit)。 // descend right } } A B C D E F G I H DBGEACHFI 后序遍歷 template class T void Postorder (TreeNodeT *t, void visit(Tamp。amp。 } template class T TreeNodeT *CopyTree(TreeNodeT *t) { TreeNodeT *newlptr, *newrptr, *newnode。 } template class T void DeleteTree(TreeNodeT *t) { if (t != NULL) { DeleteTree(tLeft())。 else{t=GetTreeNode(ch)。 // root now NULL } endif // TREE_LIBRARY_FUNCTIONS 層次遍歷 —— 廣度優(yōu)先法遍歷樹 ABCDEFGHI template class T void LevelScan(TreeNodeT*t,void visit(Tamp。 } } A B C D E F G I H 測試 include include include void print(charamp。 CreateTree(root)。 ThreadNode(const T item):data(item), left(NULL),right(NULL),LTag(0),RTag(0) { } } template class T void InOrderThreading(ThreadNodeT*amp。 //right pointer point to its self if(tree==NULL) thrtleft=thrt。 if(pleft==NULL) { pLTag=Thread。 while(p!=t) { while(pLTag==Link) p=pleft。 endif // NULL include template class T class BinSTree { TreeNodeT *root, *current。 item, TreeNodeT* amp。 rhs)。 int ListEmpty(void) const。 p = new TreeNodeT (item, lptr, rptr)。 else newlptr = NULL。 } } template class T TreeNodeT *BinSTreeT::FindNode(const Tamp。 } } return t。 rhs) { if (this == amp。 item) { TreeNodeT *parent。 if (item tdata) t = tleft。 } 二叉搜索樹的插入過程 45 12 8 57 60 20 11 59 50 3 45 12 57 8 20 60 3 11 59 50 57 20 8 45 60 59 3 12 50 11 57 20 60 8 45 11 3 12 50 59 二叉搜索樹的刪除過程 先調(diào)用函數(shù) FindNode查到要?jiǎng)h除的結(jié)點(diǎn) D(DNodePtr), D的父結(jié)點(diǎn) P(PNodePtr),我們尋找 替換結(jié)點(diǎn) R(RNodePtr). 45 12 57 15 20 60 59 50 1. D是 葉 令 R=NULL。 二叉搜索樹的刪除過程 先調(diào)用函數(shù) FindNode查到要?jiǎng)h除的結(jié)點(diǎn) D(DNodePtr), D的父結(jié)點(diǎn) P(PNodePtr),我們尋找 替換結(jié)點(diǎn) R(RNodePtr). 45 12 57 15 20 60 59 50 1. D是 葉 令 R=NULL。R=Dleft。 Rleft=Dleft。 while(RNodePtrright != NULL) { PofRNodePtr = RNodePtr。 else PNodePtrright = RNodePtr。 } template class T int BinSTreeT::ListSize(void) const { return size。 } endif // BINARY_SEARCH_TREE_CLASS 測試練習(xí) 1。 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, 則 B2(x)=b0b0+ (b0 b1+b1b0)x+(b0b2+b1b1+b2b0)x2+(1/2－ (n－ 1))(4)n/n! 設(shè) f(x)=√14x =(14x)1/2 f(x) =a0+a1x+a2x2++(1)n122n1C1/2nxn1+ T GetData( )。 int PTreeSize( )。 template class T struct CTNode { T data。 CSNodeT *firstChild, *nextSibling。 void FreeCSNode(CSNodeT *p)。 tree)。 item)。 CSNodeT *GetRoot(void) const。,T1m}轉(zhuǎn)換成的二叉樹； RB是森林 F’={T2,T3, 2。 PreOrderTraverse(tnextSibling,visit)。 int heapsize。 // copy constructor ~Heap(void)。 int ListFull(void) const。 } template class T void HeapT::FilterDown (int i) { int currentpos, childp