二叉查找樹（BinarySearch Tree，也叫二叉搜尋樹，或稱二叉排序樹Binary Sort Tree）或者是一棵空樹，或具有如下性質：
- 每個節點都有一個作為搜尋依據的關鍵碼（key），所有節點的關鍵碼互不相同。
- 左子樹上所有節點的關鍵碼（key）都小于根節點的關鍵碼（key）。
- 右子樹上所有節點的關鍵碼（key）都大于根節點的關鍵碼（key）。
- 左右子樹都是二叉搜尋樹。
二叉搜尋樹相關操作：
（1）插入：新節點
在二叉查找樹中插入新結點，要保證插入新結點後仍能滿足二叉查找樹的性質。插入過程如下：
a、若二叉查找樹root為空，則使新結點為根；
b、若二叉查找樹root不為空，則查找該節點應插入的位置。若新結點的關鍵字小于插入點的關鍵字，則将新結點插入到插入點的左子樹中，大于則插入到插入點的右子樹中。否則，不插入，傳回失敗。
（2）查找：關鍵碼的節點
a.從根節點開始查找，若關鍵字小于目前節點的關鍵字，則到目前節點的左子樹中查詢；若關鍵字大于目前節點的關鍵字，則到目前節點的右子樹中查詢；否則，查找成功，傳回目前節點。
b.若到空還沒找到，則查找失敗。
（3）、删除
删除某個結點後依然要保持二叉查找樹的特性。删除過程如下：
a、若删除點是葉子結點，則設定其雙親結點的對應指針為空。
b、若删除點隻有左子樹，或隻有右子樹，則設定其雙親結點的指針指向左子樹或右子樹。
c、若删除點的左右子樹均不為空，則：采用替代删除法
1）查詢删除點的右子樹中的非空最小節點（即最左節點），交換要删除節點與右最小節點的關鍵碼與值，删除右最小節點。
或
#include<iostream>
using namespace std;
//搜尋二叉樹
template<class K,class V>
struct BSTreeNode
{
K _key;
V _val;
BSTreeNode<K,V>* _left;
BSTreeNode<K,V>* _right;
BSTreeNode(K& key,V& val)
:_key(key)
, _val(val)
, _left(NULL)
, _right(NULL)
{}
};
template<class K,class V>
class BSTree
{
typedef BSTreeNode<K, V> Node;
public:
BSTree()
:_root(NULL)
{}
~BSTree()
{
_Destroy(_root);
_root = NULL;
}
bool Insert(K& key, V& val)
{
if (_root == NULL)
{
_root = new Node(key, val);
return true;
}
else
{
Node* parent = NULL;
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
cur = new Node(key, val);
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
}
Node* Find(const K& key)
{
if (_root == NULL)
return NULL;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
cur = cur->_right;
else if (cur->_key>key)
cur = cur->_left;
else
return cur;
}
return NULL;
}
bool Remove(const K& key)
{
if (_root == NULL)
return false;
Node* cur = _root;
Node* parent = NULL;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key>key)
{
parent = cur;
cur = cur->_left;
}
else
{
Node* del = NULL;
if (cur->_left == NULL)
{
del = cur;
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
}
else if (cur->_right == NULL)
{
del = cur;
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
}
else//左右都不為空
{
Node* rightMin = cur->_right;
parent = cur;
while (rightMin->_left)
{
parent = rightMin;
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;
cur->_val = rightMin->_val;
del=rightMin;
if (parent->_left == rightMin)
parent->_left = NULL;
else
parent->_right = NULL;
}
delete del;
return true;
}
}
return false;
}
void InOrder()
{
if (_root == NULL)
return;
_InOrder(_root);
cout << endl;
}
bool InsertR(K& key, V& val)
{
return _InsertR(_root, key, val);
}
Node* FindR(const K& key)
{
return _FindR(_root, key);
}
bool RemoveR(K key)
{
return _RemoveR(_root, key);
}
protected:
void _Destroy(Node* root)
{
if (root == NULL)
return;
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
}
bool _InsertR(Node*& root, K& key, V& val)
{
if (root == NULL)
{
root = new Node(key, val);
return true;
}
if (root->_key > key)
return _InsertR(root->_left, key, val);
else if (root->_key < key)
return _InsertR(root->_right, key, val);
else
return false;
}
Node* _FindR(Node* root, const K& key)
{
if (root == NULL)
return NULL;
if (root->_key < key)
return _FindR(root->_right, key);
else if (root->_key>key)
return _FindR(root->_left, key);
else
return root;
}
bool _RemoveR(Node*& root, K& key)
{
if (root == NULL)
return false;
if (root->_key < key)
return _RemoveR(root->_right, key);
else if (root->_key>key)
return _RemoveR(root->_left, key);
else
{
Node* del = root;
if (root->_left == NULL)
{
root = root->_right;
}
else if (root->_right == NULL)
{
root = root->_left;
}
else
{
Node* rightMin = root->_right;
Node* parent = root;
while (rightMin->_left)
{
parent = rightMin;
rightMin = rightMin->_left;
}
root->_key = rightMin->_key;
root->_val = rightMin->_val;
del = rightMin;
if (parent->_left == rightMin)
parent->_left = NULL;
else
parent->_right = NULL;
}
delete del;
return true;
}
}
protected:
void _InOrder(Node* root)
{
if (root == NULL)
return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
private:
Node* _root;
};
void Test1()
{
int a[] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };
BSTree<int, int> t;
for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
{
t.Insert(a[i], i);
}
for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
{
cout<<"是否存在"<<a[i]<<" "<<t.Find(a[i])->_key<<endl;
}
t.InOrder();
cout << 5 << t.Remove(5) << endl;
cout << 8 << t.Remove(8) << endl;
cout << 2 << t.Remove(2) << endl;
cout << 1 << t.Remove(1) << endl;
cout << 3 << t.Remove(3) << endl;
cout << 7 << t.Remove(7) << endl;
t.InOrder();
}
void Test2()
{
int a[] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };
BSTree<int, int> t;
for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
{
t.InsertR(a[i], i);
}
for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
{
cout << "是否存在" << a[i] << " " << t.FindR(a[i])->_key << endl;
}
t.InOrder();
cout << 5 << t.RemoveR(5) << endl;
cout << 8 << t.RemoveR(8) << endl;
cout << 2 << t.RemoveR(2) << endl;
cout << 1 << t.RemoveR(1) << endl;
cout << 3 << t.RemoveR(3) << endl;
cout << 7 << t.RemoveR(7) << endl;
cout << 9 << t.RemoveR(9) << endl;
cout << 0 << t.RemoveR(0) << endl;
cout << 4 << t.RemoveR(4) << endl;
cout << 6 << t.RemoveR(6) << endl;
cout << 5 << t.RemoveR(5) << endl;
cout << 6 << t.RemoveR(6) << endl;
t.InOrder();
}
#include"SBTree.h"
int main()
{
//Test1();
Test2();
system("pause");
return 0;
} ![真二叉樹重構(Proper Rebuild)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)