二叉排序樹（Binary Sort Tree）又稱二叉查找樹,它的特點是: （1）若左子樹不空，則左子樹上所有結點的值均小於它的根結點的值; （2）若右子樹不空，則右子樹上所有結點的值均大於它的根結點的值; （3）左、右子樹也分別為二叉排序樹； 但你看到定義可能會奇怪,如果出現相等元素咋整啊.這裡我們就假設右子樹的結點值大於或等於根結點得了. 在這裡我們實現二叉樹的如下簡單功能:(二叉樹結點類為BTreeNode<T>) void Insert(T val); //往二叉樹中插入數據,自然要保證插入數據後仍然是二叉樹 BTreeNode<T>* Search(T val); //查找值為val的結點 BTreeNode<T>* SearchMinVal(); //查找值最小的結點 BTreeNode<T>* SearchMaxVal();//查找值最大的結點 void Delete(T val); //刪除任意節點 1.先定義一個二叉樹的結點類 template<class T> class BTreeNode{ public: T val; BTreeNode<T>* left; //指向左孩子的指針 BTreeNode<T>* right; BTreeNode<T>* parent; //指向父結點的指針 BTreeNode(T tVal){ val = tVal; left = right = parent = NULL; } bool operator==(BTreeNode<T>* bt){ //重載操作符比較兩結點是否相等 return bt.val == val ? true: false; } }; 2.定義二叉查找樹的類BSortTree #include "BTreeNode.h" template<class T> class BSortTree{ private: BTreeNode<T>* root; //根結點指針 int size; //樹中元素總個數 public: BSortTree(void){ root = NULL; size = 0; } ~BSortTree(void){} int Size() { return size;} void Insert(T val){ //插入結點元素 if(root == NULL){ //樹為空 BTreeNode<T>* pNode = new BTreeNode<T>(val); root = pNode; size++; return; } InsertTree(root, val); //樹不為空時插入元素 } BTreeNode<T>* Search(T val){ //查找結點 return SearchTree(root, val); } BTreeNode<T>* SearchMinVal(){ //查找最小值元素 SearchTreeMinVal(root); } BTreeNode<T>* SearchMaxVal(){ //查找最大值元素 SearchTreeMaxVal(root); } void Delete(T val){ //刪除任意結點 DeleteTreeNode(root, val); } private: //刪除節點分4種情況 //1.如果是葉子,則直接刪除 //2.如果只有左子樹,則刪除結點後左子樹上移即可 //3.如果只有右子樹,則刪除結點後右子樹上移即可 //4.如果左右子樹都有,則查找要刪除結點(p)的左子樹中的最大結點(m),把m的結點值賦給p,然後刪除m. void DeleteTreeNode(BTreeNode<T>* pRoot, T val){ //刪除結點 BTreeNode<T>* node = Search(val); //要刪除的結點 if(node == NULL) //要刪除的結點不存在 return; //1.被刪結點是葉子,直接刪 if(node->left==NULL && node->right==NULL){ if(node->parent == NULL){ //只有一個結點的樹 size = 0; root = NULL; } else if(node->parent->left == node)//被刪結點是左孩子 node->parent->left = NULL; else //結點是右孩子 node->parent->right = NULL; delete node; size--; return; } //2.被刪結點只有左子樹 if(node->left !=NULL && node->right==NULL){ node->left->parent = node->parent; if(node->parent == NULL) //被刪結點是根結點 root = node->left; else if(node->parent->left == node)//被刪結點是左孩子 node->parent->left = node->left; else //被刪結點是右孩子 node->parent->right = node->right; delete node; size--; return; } //3.被刪結點只有右子樹 if(node->right !=NULL && node->left==NULL){ node->right->parent = node->parent; if(node->parent == NULL) //被刪結點是根結點 root = node->right; else if(node->parent->left == node)//被刪結點是左孩子 node->parent->left = node->left; else //被刪結點是右孩子 node->parent->right = node->right; delete node; size--; return; } //4.被刪結點左右孩子都有 if(node->left !=NULL && node->right != NULL){ BTreeNode<T>* replaceNode = SearchTreeMinVal(node->right); //也可以替換成查找左子樹最大值 node->val = replaceNode->val; DeleteTreeNode(root, replaceNode->val); } } void InsertTree(BTreeNode<T>* pRoot,T val) { BTreeNode<T>* pNode = new BTreeNode<T>(val); if(pRoot->left == NULL && val < pRoot->val){ pRoot->left = pNode; pNode->parent = pRoot; size++; return; } if(pRoot->right == NULL && val >= pRoot->val){ pRoot->right = pNode; pNode->parent = pRoot; size++; return; } if(val < pRoot->val) InsertTree(pRoot->left,val); else InsertTree(pRoot->right,val); } BTreeNode<T>* SearchTree(BTreeNode<T>* pRoot,T val){ if(pRoot == NULL) return NULL; else if(val == pRoot->val) return pRoot; else if(val < pRoot->val) return SearchTree(pRoot->left,val); else return SearchTree(pRoot->right, val); } BTreeNode<T>* SearchTreeMinVal(BTreeNode<T>* pRoot){ if(pRoot==NULL) return NULL; else if(pRoot->left == NULL) return pRoot; elsewww.2cto.com return SearchTreeMinVal(pRoot->left); } BTreeNode<T>* SearchTreeMaxVal(BTreeNode<T>* pRoot){ if(pRoot==NULL) return NULL; else if(pRoot->right == NULL) return pRoot; else return SearchTreeMinVal(pRoot->right); }
