C++實現搜索二叉樹

二叉查找樹（英語：Binary Search Tree），也稱二叉搜索樹、有序二叉樹（英語：ordered binary tree），排序二叉樹（英語：sorted binary tree），是指一棵空樹或者具有下列性質的二叉樹：

• 任意節點的左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
• 任意節點的右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；
• 任意節點的左、右子樹也分別為二叉查找樹；
• 沒有鍵值相等的節點。

#pragma once

template<class K, class V>
struct BSTreeNode
{
K _key;
V _value;
BSTreeNode<K, V>* _left;
BSTreeNode<K, V>* _right;

BSTreeNode(const K& key, const V& value)
:_key(key)
,_value(value)
,_left(NULL)
,_right(NULL)
{}
};

template<class K, class V>
class BSTree
{
typedef BSTreeNode<K, V> Node;
public:
BSTree()
:_root(NULL)
{}

bool Insert(const K& key, const V& value)
{
if (NULL == _root)//若為空樹
{
_root = new Node(key, value);
return true;
}

Node* parent = NULL;
Node* cur = _root;

//確定插入節點的位置
while (cur)
{
if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else//已經存在key
{
return false;
}
}

//插入節點
if (key > parent->_key)
parent->_right = new Node(key, value);
else
parent->_left = new Node(key, value);
}

//Insert遞歸寫法
bool InsertR(const K& key, const V& value)
{
return _InsertR(_root, key, value);
}

bool _InsertR(Node*& root, const K& key, const V& value)
{
if (NULL == root)
{
root = new Node(key, value);
return true;
}

if (key > root->_key)
return _InsertR(root->_right, key, value);
else if (key < root->_key)
return _InsertR(root->_left, key, value);
else
return false;
}

Node* Find(const K& key)
{
Node* cur = _root;

while (cur)
{
if (key > cur->_key)
cur = cur->_right;
else if (key < cur->_key)
cur = cur->_left;
else
return cur;
}

return NULL;
}

//Find遞歸寫法
Node* FindR(const K& key)
{
return _FindR(_root, key);
}

Node* _FindR(Node* root, const K& key)
{
if (NULL == root)
return NULL;

if (key > root->_key)
return _FindR(root->_right, key);
else if (key < root->_key)
return _FindR(root->_left, key);
else
return root;
}

bool Remove(const K& key)
{
Node* parent = NULL;
Node* cur = _root;

//確定刪除節點的位置
while (cur)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else
{
break;
}
}

if (NULL == cur)//沒有該節點
{
return false;
}

Node* del;
if (NULL == cur->_left)//刪除節點的左孩子為空
{
del = cur;

//刪除的節點為根節點
if (NULL == parent)
{
_root = _root->_right;
}
else
{
if (cur == parent->_left)
parent->_left = cur->_right;
else
parent->_right = cur->_right;
}
}
else if (NULL == cur->_right)//刪除節點的右孩子為空
{
del = cur;

if (NULL == parent)
{
_root = _root->_left;
}
else
{
if (cur == parent->_left)
parent->_left = cur->_right;
else
parent->_right = cur->_left;
}
}
else//刪除節點的左右孩子都不為空，找右子樹最左節點代替該節點刪除
{
parent = cur;

Node* leftmost = cur->_right;
while (leftmost->_left)
{
parent = leftmost;
leftmost = leftmost->_left;
}

del = leftmost;

cur->_key = leftmost->_key;
cur->_value = leftmost->_value;

if (leftmost == parent->_left)
parent->_left = leftmost->_right;
else
parent->_right = leftmost->_right;
}

return true;
}

//Remove遞歸寫法
bool RemoveR(const K& key)
{
return _RemoveR(_root, key);
}

bool _RemoveR(Node*& root, const K& key)
{
if (NULL == root)
return false;

if (key > root->_key)
{
return _RemoveR(root->_right, key);
}
else if (key < root->_key)
{
return _RemoveR(root->_left, key);
}
else
{
Node* del = root;

if (NULL == root->_left)
{
root = root->_right;
}
else if (NULL == root->_right)
{
root = root->_left;
}
else
{
Node* leftmost = root->_right;
while (leftmost->_left)
{
leftmost = leftmost->_left;
}

swap(root->_key, leftmost->_key);
swap(root->_value, leftmost->_value);

return _RemoveR(root->_right, key);
}

delete del;
}

return true;
}

//中序遍歷遞歸寫法
void InOrder()
{
_InOrder(_root);
}

void _InOrder(Node* root)
{
if (NULL == root)
return;

_InOrder(root->_left);
cout<<root->_key<<" ";
_InOrder(root->_right);
}

protected:
Node* _root;
};


void Test()
{
BSTree<int, int> t;
int a[] = {5, 3, 4, 1, 7, 8, 2, 6, 0, 9};
for (size_t i = 0; i < sizeof(a)/sizeof(a[0]);++i)
{
t.InsertR(a[i], i);
}

cout<<t.FindR(8)->_key<<endl;
cout<<t.FindR(5)->_key<<endl;
cout<<t.FindR(9)->_key<<endl;

t.RemoveR(8);
t.RemoveR(7);
t.RemoveR(9);
t.RemoveR(6);
t.RemoveR(5);
t.RemoveR(3);
t.RemoveR(1);
t.RemoveR(4);
t.RemoveR(0);
t.RemoveR(2);

t.InOrder();
}