【正文】 I H 為代數(shù)式 a+b*(cd)e/f 建一棵樹 使 a,b,c,d,e,f為葉，兩個數(shù)之間的運算符為根 . — + / a * e f b — c d a=GetTreeNode(‘a(chǎn)’,(TreeNodechar)NULL, (TreeNodechar)NULL)。 p2=GetTreeNode(‘*’,b,p1)。 p4=GetTreeNode(‘/’,e,f)。 root=p5。 item)) { // the recursive scan terminates on a empty subtree if (t != NULL) { visit(tdata)。 // descend left Preorder (tRight( ), visit)。 ABDEGCFHI void print(charamp。} 中序遍歷 template class T void Inorder (TreeNodeT *t, void visit(Tamp。 // descend left visit(tdata)。 // descend right } } A B C D E F G I H DBGEACHFI 后序遍歷 template class T void Postorder (TreeNodeT *t, void visit(Tamp。 // descend left Postorder (tRight( ), visit)。 // visit the node } } A B C D E F G I H DGEBHIFCA template class T void CountLeaf (TreeNodeT *t, intamp。 CountLeaf(tRight( ), count)。amp。 } } 二叉樹的運算 template class T int Depth (TreeNodeT *t) { int depthLeft, depthRight, depthval。 else { depthLeft= Depth(tLeft( ))。 depthval = 1 + (depthLeft depthRight?depthLeft:depthRight)。 } template class T TreeNodeT *CopyTree(TreeNodeT *t) { TreeNodeT *newlptr, *newrptr, *newnode。 if (tLeft( ) = NULL) newlptr = NULL。 if (tRight( ) = NULL) newrptr = NULL。 newnode = GetTreeNode(tdata, newlptr, newrptr)。 } template class T void DeleteTree(TreeNodeT *t) { if (t != NULL) { DeleteTree(tLeft())。 FreeTreeNode(t)。t ) {TreeNodeT*l,*r。 cinch。 else{t=GetTreeNode(ch)。 tGetLeft(l)。tGetRight(r)。t) { DeleteTree(t)。 // root now NULL } endif // TREE_LIBRARY_FUNCTIONS 層次遍歷 —— 廣度優(yōu)先法遍歷樹 ABCDEFGHI template class T void LevelScan(TreeNodeT*t,void visit(Tamp。 TreeNodeT * p。 while(!( )) { p=( )。 if(pLeft( )!=NULL)(pLeft( ))。 } } A B C D E F G I H 測試 include include include void print(charamp。} void main(void) { TreeNodechar *root。 int leafCount = 0。 cout Number of leaf nodes is leafCount endl。 CreateTree(root)。 } 三、線索二叉樹 帶 線索 的二叉樹，即每個結點都帶有 指向其前驅和后繼的指針 的二叉樹 lchild ltag data rtag rchild ltag=0 lchild 指向左子結點 =1 前驅 rtag=0 rchild 指向右子結點 =1 后繼 優(yōu)點： 遍歷查找方便快捷，從任何結點可 以向前向后搜索 用途 ：需要反復遍歷和查找的二叉樹 中序線索化樹 lchild ltag data rtag rchild A B C D E 0 A 0 1 B 0 0 C 1 1 D 1 1 E 1 1 1 線索二叉樹的結點類 include include typedef enum { Link, Thread //Link==0。 }PointerTag。 //pointer PointerTag LTag, RTag。 ThreadNode(const T item):data(item), left(NULL),right(NULL),LTag(0),RTag(0) { } } template class T void InOrderThreading(ThreadNodeT*amp。 thrt=new ThreadNodeT。 exit(1)。 thrtRTag=Thread。 //right pointer point to its self if(tree==NULL) thrtleft=thrt。 pre=thrt。 preRTag=Thread。 thrtright=pre。 if(pleft==NULL) { pLTag=Thread。 } if(preright==NULL) { preRTag=Thread。 } pre=p。 } } template class T void InOrderTravers(ThreadNodeT*t , void visit(T item)) { ThreadNode *p。 while(p!=t) { while(pLTag==Link) p=pleft。 while(pRTag==Threadamp。pright!=t) { p=pright。 } p = pright。 endif // NULL include template class T class BinSTree { TreeNodeT *root, *current。 TreeNodeT *GetTreeNode(const Tamp。 void FreeTreeNode(TreeNodeT *p)。 void DeleteTree(TreeNodeT *t)。 item, TreeNodeT* amp。 public: BinSTree(void)。 tree)。 BinSTreeTamp。 rhs)。 item)。 item)。 item)。 int ListEmpty(void) const。 void Update(const Tamp。 TreeNodeT *GetRoot(void) const。 template class T TreeNodeT *BinSTreeT::GetTreeNode(const Tamp。 p = new TreeNodeT (item, lptr, rptr)。 exit(1)。 } // delete the storage occupied by a tree node template class T void BinSTreeT::FreeTreeNode(TreeNodeT *p) { delete p。 if (t == NULL) return NULL。 else newlptr = NULL。 else newrptr = NULL。 return newNode。 DeleteTree(tright)。 } } template class T TreeNodeT *BinSTreeT::FindNode(const Tamp。 parent) const { TreeNodeT *t = root。 while(t != NULL) { if (item == tdata) break。 if (item tdata) t = tleft。 } } return t。 tree) { // copy tree to the current object. assign current and size root = CopyTree()。 size = 。 } template class T BinSTreeTamp。 rhs) { if (this == amp。 ClearList( )。 current = root。 return *this。 item) { TreeNodeT *parent。 if (current != NULL) { item = currentdata。 } else return 0。 item) {TreeNodeT *t = root, *parent = NULL, *newNode。 if (item tdata) t = tleft。 } newNode = GetTreeNode(item,NULL,NULL)。 else if (item parentdata) parentleft = newNode。 current = newNode。 } 二叉搜索樹的插入過程 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 二叉搜索樹的刪除過程 先調用函數(shù) FindNode查到要刪除的結點 D(DNodePtr), D的父結點 P(PNodePtr),我們尋找 替換結點 R(RNodePtr). 45 12 57 15 20 60 59 50 1. D是 葉 令 R=NULL。即可。 Pleft=R。 D P R 2. D只有左子樹 令 R=Dleft。 二叉搜索樹的刪除過程 先調用函數(shù) FindNode查到要刪除的結點 D(DNodePtr), D的父結點 P(PNodePtr),我們尋找 替換結點 R(RNodePtr). 45 12