二叉搜索樹或是一顆空二叉樹, 或是具有以下性質的二叉樹: 1.若左子樹不為空, 則左子樹上所有結點的關鍵字值均小于根結點的關鍵字值. 2.若右子樹不為空,?則右子樹上所有結點的關鍵字值均大于根結點的關鍵字值. 3.左右子樹也分別是二叉搜索樹. 性質: 若以中序遍歷一顆二叉搜索樹, 將得到一個以關鍵字值遞增排列的有序序列. 1.搜索實現: 若二叉樹為空, 則搜索失敗. 否則, 將x與根結點比較. 若x小于該結點的值, 則以同樣的方法搜索左子樹, 不必搜索右子樹. 若x大于該結點的值, 則以同樣的方法搜索右子樹, 而不必搜索左子樹. 若x等于該結點的值, 則搜索成功終止. search()為遞歸搜索, search1()為迭代搜索. 2.插入實現: 插入一個新元素時, 需要先搜索新元素的插入位置. 如果樹種有重復元素, 返回Duplicate. 搜索達到空子樹, 則表明樹中不包含重復元素. 此時構造一個新結點p存放新元素x, 連至結點q, 成為q的孩子, 則新結點p成為新二叉樹的根. 3.刪除實現: 刪除一個元素時, 先搜索被刪除結點p, 并記錄p的雙親結點q. 若不存在被刪除的元素, 返回NotPresent.? (1)若p有兩顆非空子樹, 則搜索結點p的中序遍歷次序下的直接后繼結點, 設為s. 將s的值復制到p中.? (2)若p只有一顆非空子樹或p是葉子, 以結點p的唯一孩子c或空子樹c = NULL取代p. (3)若p為根結點, 刪除后結點c成為新的根. 否則若p是其雙親確定左孩子, 則結點c也應成為q的左孩子, 最后釋放結點p所占用的空間. 實現代碼: ~~~ #include "iostream" #include "cstdio" #include "cstring" #include "algorithm" #include "cmath" #include "utility" #include "map" #include "set" #include "vector" using namespace std; typedef long long ll; const int MOD = 1e9 + 7; enum ResultCode{ Underflow, Overflow, Success, Duplicate, NotPresent }; // 賦值為0, 1, 2, 3, 4, 5 template <class T> class DynamicSet { public: virtual ~DynamicSet() {} virtual ResultCode Search(T &x) const = 0; virtual ResultCode Insert(T &x) = 0; virtual ResultCode Remove(T &x) = 0; /* data */ }; template <class T> struct BTNode { BTNode() { lChild = rChild = NULL; } BTNode(const T &x) { element = x; lChild = rChild = NULL; } BTNode(const T &x, BTNode<T> *l, BTNode<T> *r) { element = x; lChild = l; rChild = r; } T element; BTNode<T> *lChild, *rChild; /* data */ }; template <class T> class BSTree : public DynamicSet<T> { public: explicit BSTree() { root = NULL; } // 只可顯示轉換 virtual ~BSTree() { Clear(root); } ResultCode Search(T &x) const; ResultCode Search1(T &x) const; ResultCode Insert(T &x); ResultCode Remove(T &x); protected: BTNode<T> *root; private: void Clear(BTNode<T> *t); ResultCode Search(BTNode<T> *p, T &x) const; /* data */ }; template <class T> void BSTree<T>::Clear(BTNode<T> *t) { if(t) { Clear(t -> lChild); Clear(t -> rChild); cout << "delete" << t -> element << "..." << endl; delete t; } } template< class T> ResultCode BSTree<T>::Search(T &x) const { return Search(root, x); } template <class T> ResultCode BSTree<T>::Search(BTNode<T> *p, T &x) const { if(!p) return NotPresent; if(x < p -> element) return Search(p -> lChild, x); if(x > p -> element) return Search(p -> rChild, x); x = p -> element; return Success; } template <class T> ResultCode BSTree<T>::Search1(T &x) const { BTNode<T> *p = root; while(p) { if(x < p -> element) p = p -> lChild; else if(x > p -> element) p = p -> rChild; else { x = p -> element; return Success; } } return NotPresent; } template <class T> ResultCode BSTree<T>::Insert(T &x) { BTNode<T> *p = root, *q = NULL; while(p) { q = p; if(x < p -> element) p = p -> lChild; else if(x > p -> element) p = p -> rChild; else { x = p -> element; return Duplicate; } } p = new BTNode<T>(x); if(!root) root = p; else if(x < q -> element) q -> lChild = p; else q -> rChild = p; return Success; } template <class T> ResultCode BSTree<T>::Remove(T &x) { BTNode<T> *c, *s, *r, *p = root, *q = NULL; while(p && p -> element != x) { q = p; if(x < p -> element) p = p -> lChild; else p = p -> rChild; } if(!p) return NotPresent; x = p -> element; if(p -> lChild && p -> rChild) { s = p -> rChild; r = p; while(s -> lChild) { r = s; s = s -> lChild; } p -> element = s -> element; p = s; q = r; } if(p -> lChild) c = p -> lChild; else c = p -> rChild; if(p == root) root = c; else if(p == q -> lChild) q -> lChild = c; else q -> rChild = c; delete p; return Success; } int main(int argc, char const *argv[]) { BSTree<int> bst; int x = 28; bst.Insert(x); x = 21; bst.Insert(x); x = 25; bst.Insert(x); x = 36; bst.Insert(x); x = 33; bst.Insert(x); x = 43; bst.Insert(x); return 0; } ~~~