【文章內容簡介】 二叉搜索樹 45 12 57 8 20 60 3 11 59 50 二叉搜索樹的作用： 排序 ， 檢索 二叉搜索樹 ifndef BINARY_SEARCH_TREE_CLASS define BINARY_SEARCH_TREE_CLASS include include ifndef NULL const int NULL = 0。 endif // NULL include template class T class BinSTree { TreeNodeT *root, *current。 int size。 TreeNodeT *GetTreeNode(const Tamp。 item, TreeNodeT *lptr,TreeNodeT *rptr)。 void FreeTreeNode(TreeNodeT *p)。 TreeNodeT *CopyTree(TreeNodeT *t)。 void DeleteTree(TreeNodeT *t)。 TreeNodeT *FindNode(const Tamp。 item, TreeNodeT* amp。 parent) const。 public: BinSTree(void)。 BinSTree(const BinSTreeTamp。 tree)。 ~BinSTree(void)。 BinSTreeTamp。 operator= (const BinSTreeTamp。 rhs)。 int Find(Tamp。 item)。 void Insert(const Tamp。 item)。 void Delete(const Tamp。 item)。 void ClearList(void)。 int ListEmpty(void) const。 int ListSize(void) const。 void Update(const Tamp。 item)。 TreeNodeT *GetRoot(void) const。 }。 template class T TreeNodeT *BinSTreeT::GetTreeNode(const Tamp。 item,TreeNodeT *lptr,TreeNodeT *rptr) { TreeNodeT *p。 p = new TreeNodeT (item, lptr, rptr)。 if (p == NULL) { cerr Memory allocation failure!\n。 exit(1)。 } return p。 } // delete the storage occupied by a tree node template class T void BinSTreeT::FreeTreeNode(TreeNodeT *p) { delete p。 } template class T TreeNodeT *BinSTreeT::CopyTree(TreeNodeT *t) { TreeNodeT *newlptr, *newrptr, *newNode。 if (t == NULL) return NULL。 if (tleft != NULL) newlptr = CopyTree(tleft)。 else newlptr = NULL。 if (tright != NULL) newrptr = CopyTree(tright)。 else newrptr = NULL。 newNode = GetTreeNode(tdata, newlptr, newrptr)。 return newNode。 } template class T void BinSTreeT::DeleteTree(TreeNodeT *t) { if (t != NULL) { DeleteTree(tleft)。 DeleteTree(tright)。 FreeTreeNode(t)。 } } template class T TreeNodeT *BinSTreeT::FindNode(const Tamp。 item, TreeNodeT* amp。 parent) const { TreeNodeT *t = root。 parent = NULL。 while(t != NULL) { if (item == tdata) break。 else { parent = t。 if (item tdata) t = tleft。 else t = tright。 } } return t。 } template class T BinSTreeT::BinSTree(void): root(NULL),current(NULL),size(0) { } template class T BinSTreeT::BinSTree(const BinSTreeTamp。 tree) { // copy tree to the current object. assign current and size root = CopyTree()。 current = root。 size = 。 } template class T BinSTreeT::~BinSTree(void) { // just call ClearList ClearList( )。 } template class T BinSTreeTamp。 BinSTreeT::operator= (const BinSTreeTamp。 rhs) { if (this == amp。rhs) return *this。 ClearList( )。 root = CopyTree()。 current = root。 size = 。 return *this。 } template class T int BinSTreeT::Find(Tamp。 item) { TreeNodeT *parent。 current = FindNode (item, parent)。 if (current != NULL) { item = currentdata。 return 1。 } else return 0。 } template class T void BinSTreeT::Insert(const Tamp。 item) {TreeNodeT *t = root, *parent = NULL, *newNode。 while(t != NULL) { parent = t。 if (item tdata) t = tleft。 else t = tright。 } newNode = GetTreeNode(item,NULL,NULL)。 if (parent == NULL) root = newNode。 else if (item parentdata) parentleft = newNode。 else parentright = newNode。 current = newNode。 size++。 } 二叉搜索樹的插入過程 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 二叉搜索樹的刪除過程 先調用函數 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 二叉搜索樹的刪除過程 先調用函數 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。 15 R 15 RPright=R。 二叉搜索樹的刪除過程 先調用函數 FindNode查到要刪除的結點 D(DNodePtr), D的父結點 P(PNodePtr),我們尋找 替換結點 R(RNodePtr). 45 12 57 15 20 60 59 50 1. D是 葉 令 R=NULL。 Pleft=R。即可。 D P 2. D只有左子樹 , Dright=NULL 令 R=Dleft。 Pright=R。 3. D只有右子樹 , Dleft=NULL 令 R=Dright。 Pleft=R。 R 15 20R 57 20 60 8 45 11 3 12 50 59 二叉搜索樹的刪除過程 D P R R Q=D。R=Dleft。 while(Rright){Q=R, R=Rright:} R選擇 D的 左 子樹中 最大 結點 (或 右 子樹中 最小 結點 ) 有兩種情況： 1. Q==D Rright=Dright。 2. Q!=D Qright=Rleft。 再用 R代替 D R 1112 R Q Q R 57 20 60 8 45 3 11 50 59 二叉搜索樹的刪除過程 D P R Q=D。R=Dleft。 while(Rright){Q=R, R=Rright:} 2. Q!=D Qright=Rleft。 再用 R代替 D : Q 有兩種情況： 1. Q==D Rright=Dright。 Rright=Dright。 Rleft=Dleft。 12 R R R 12 最后讓 P指向 R 如果 P==NULL 則 R是根，否則 D在 P左 R在左 template class T void BinSTreeT::Delete(const Tamp。 item) {TreeNodeT *DNodePtr, *PNodePtr, *RNodePtr。 if ((DNodePtr = FindNode (item, PNodePtr)) == NULL) return。 if (DNodePtrright == NULL) RNodePtr = DNodePtrleft。 else if (DNodePtrleft == NULL) RNodePtr = DNodePtrright。 else {TreeNodeT *PofRNodePtr = DNodePtr。 RNodePtr = DNodePtrleft。 while(RNodePtrright != NULL) { PofRNodePtr = RNodePtr。 RNodePtr = RNodePtrright。 } if (PofRNodePtr == DNodePtr) RNodePtrright = DNodePtrright。 else{PofRNode