二叉搜索樹：
創(chuàng)新互聯(lián)是一家專業(yè)提供興海企業(yè)網(wǎng)站建設(shè),專注與網(wǎng)站設(shè)計制作、做網(wǎng)站、html5、小程序制作等業(yè)務(wù)。10年已為興海眾多企業(yè)、政府機構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)的建站公司優(yōu)惠進行中。
1.每個節(jié)點都有一個關(guān)鍵碼（key）作為搜索依據(jù)，關(guān)鍵碼互不相同。
2.左子樹的所有關(guān)鍵碼都小于根節(jié)點的關(guān)鍵碼。
3.右子樹的所有關(guān)鍵碼都大于根節(jié)點的關(guān)鍵碼。
4.左右子樹都是二叉搜索樹。
刪除key：左為空，右為空，左右都不空
1）左為空：cur的右樹鏈到父節(jié)點
2）右為空：cur的左樹鏈到父節(jié)點
3）左右都不空：找右樹最左節(jié)點或左樹最右節(jié)點，將找到的節(jié)點與cur交換后刪除它。
二叉搜索樹的增、刪、查（非遞歸及遞歸）程序代碼如下：
#pragma once
#include
////注意：考慮邊界問題_root 、左右子樹問題（非遞歸、遞歸）、記住判空處理
template
struct BSTNode
{
BSTNode* _left; //左子數(shù)
BSTNode* _right; //右子樹
K _key;
V _value;
//構(gòu)造函數(shù)
BSTNode(const K& key, const V& value)
:_left(NULL)
, _right(NULL)
, _key(key)
, _value(value)
{}
};
template
class BSTree
{
typedef BSTNode Node;
public:
BSTree()
:_root(NULL)
{}
public:
//bool Insert(const K& key, const V& value);
//bool Remove(const K& key);
//Node* Find(const K& key);
//bool Insert_R(const K& key, const V& value);
//bool Remove_R(const K& key, const V& value);
//Node* Find_R(const K& key);
bool Insert(const K& key, const V& value)
{
if(_root == NULL)
_root = new Node(key, value);
Node* cur = _root;
while(cur)
{
if(key < cur->_key) //key小，插入左子樹
{
if(cur->_left == NULL)
cur->_left = new Node(key, value);
else
cur = cur->_left;
}
else if(key > cur->_key) //key大，插入右子樹
{
if(cur->_right == NULL)
cur->_right = new Node(key, value);
else
cur = cur->_right;
}
else //key關(guān)鍵碼互不相同
return false;
}
return true;
}
////////////////刪除//////////////
////邊界條件判斷（無節(jié)點，一個節(jié)點）
////找key值，記錄parent。
////刪除key，分三種情況(左為空，右為空，左右都不為空)
////左右節(jié)點都存在，找到右樹的最左節(jié)點或者左樹的最右節(jié)點，
////將找到的節(jié)點與cur交換后再刪除找到的節(jié)點
bool Remove(const K& key)
{
//無節(jié)點
if(_root == NULL)
return false;
//一個節(jié)點 _root
if(_root->_left == NULL&&_root->_right == NULL)
{
if(key == _root->_key)
{
delete _root;
_root = NULL;
return true;
}
else
return false;
}
Node* cur = _root;
Node* parent = NULL;
while(cur)
{ //找key值，記錄parent
if(key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else if(key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
////刪除key，分三種情況(左為空，右為空，左右都不為空)
else
{
Node*del=cur;
if(cur->_left == NULL) //將cur的右子樹鏈到父節(jié)點
{
//注意parent可能為空
if(parent == NULL)
{
_root = cur->_right;
}
else
{
if(cur = parent->_left)
parent->_left = cur->_right;
else
parent->_right = cur->_right;
}
}
else if(cur->_right == NULL) //將cur的左子樹鏈到父節(jié)點
{
if(parent == NULL)
{
_root = cur->_left;
}
else
{
if(cur = parent->_left)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
}
}
////左右節(jié)點都存在，找到右樹的最左節(jié)點或者左樹的最右節(jié)點
////將找到的節(jié)點與cur交換后再刪除找到的節(jié)點
else
{
parent = cur;
//右樹的最左節(jié)點firstLeft
Node* firstLeft = cur->_right;
while(firstLeft->_left)
{
parent = firstLeft;
firstLeft = firstLeft->_left;
}
swap(firstLeft->_key, cur->_key);
swap(firstLeft->_value, cur->_value);
del = firstLeft;
//因為左右節(jié)點都存在，所以parent不為空
//firstLeft 左節(jié)點為空，右節(jié)點可能存在
if(firstLeft == parent->_left)
parent->_left = firstLeft->_right;
else
parent->_right = firstLeft->_right;
} /*找到firstLeft代替del*/
delete del;
return true;
}
}//while end
return false;
}
//查找
Node* Find(const K& key)
{
if(_root == NULL)
return NULL;
Node* cur = _root;
while(cur)
{
if(key < cur->_key) //在左子樹查找
{
cur = cur->_left;
}
else if(key>cur->_key) //在右子樹查找
{
cur = cur->_right;
}
else
{
return cur;
}
}
return NULL;
}
/////////////////////遞歸實現(xiàn)增刪查
bool Insert_R(const K& key, const V& value)
{
return _Insert_R(_root, key, value);
}
bool Remove_R(const K& key)
{
return _Remove_R(_root, key);
}
Node* Find_R(const K& key)
{
return _Find_R(_root, key);
}
//中序遍歷
void InOrder()
{
return _InOrder(_root);
}
bool Empty()
{
if(_root == NULL)
{
return true;
}
return false;
}
protected:
void _InOrder(Node* root)
{
if(root == NULL)
return;
_InOrder(root->_left);
//cout << root->_key << " " << endl;
cout << "key:" << root->_key << " ,value:" << root->_value<< endl;
_InOrder(root->_right);
}
////注意：root參數(shù)應(yīng)為引用& 每次遞歸的root即為上一次的root->_left或者root->_right
bool _Insert_R(Node*& root, const K& key, const V& value)
{
if(root == NULL)
{
root = new Node(key, value);
return true;
}
if(key < root->_key)
{
return _Insert_R(root->_left, key, value);
}
else if(key>root->_key)
{
return _Insert_R(root->_right, key, value);
}
else
{
return false;
}
}
//查找
Node* _Find_R(Node*& root, const K& key)
{
if(root == NULL)
return NULL;
if(key < root->_key)
{
return _Find_R(root->_left, key);
}
else if(key>root->_key)
{
return _Find_R(root->_right, key);
}
else
{
return root;
}
}
//刪除
bool _Remove_R(Node*& root, const K& key)
{
if(root == NULL)
return false;
if(key < root->_key)
{
return _Remove_R(root->_left, key);
}
else if(key > root->_key)
{
return _Remove_R(root->_right, key);
}
///刪除key
////以引用root作參數(shù)，root相當(dāng)于上一層的root->_left或者root->_right
else
{
Node*del = root;
if(root->_left == NULL)
{
root = root->_right;
delete del;
return true;
}
else if(root->_right == NULL)
{
root = root->_left;
delete del;
return true;
}
///左右節(jié)點都不為空
else
{
//右子樹的最左節(jié)點
Node* firstLeft = root->_right;
while(firstLeft->_left)
{
firstLeft = firstLeft->_left;
}
swap(firstLeft->_key, root->_key);
swap(firstLeft->_value, root->_value);
//_Remove_R(firstLeft, key);//錯誤，firstLeft是臨時變量不能作為遞歸的參數(shù)
_Remove_R(root->_right, key);
}
}///刪除key end
return false;
}
protected:
Node* _root;
};
測試代碼：
void TestBSTree()
{
BSTree bst;
bst.Insert(5, 1);
bst.Insert(3, 1);
bst.Insert(4, 1);
bst.Insert(1, 1);
bst.Insert(7, 1);
bst.Insert(8, 1);
bst.Insert(2, 1);
bst.Insert(6, 1);
bst.Insert(0, 1);
bst.Insert(9, 1);
bst.InOrder();
cout << "? " << bst.Find(1)->_key<< endl;
cout << "? " << bst.Find(8)->_key<< endl;
cout << "? " << bst.Find(22)<< endl;
bst.Remove(1);
bst.Remove(2);
bst.Remove(3);
bst.Remove(4);
bst.Remove(5);
bst.Remove(6);
bst.Remove(7);
bst.Remove(8);
bst.Remove(9);
bst.Remove(0);
if(bst.Empty())
cout << "此二叉搜索樹為空" << endl;
bst.InOrder();
}
void TestBSTree_R() //遞歸
{
BSTree bst;
bst.Insert_R(5, 1);
bst.Insert_R(3, 1);
bst.Insert_R(4, 1);
bst.Insert_R(1, 1);
bst.Insert_R(7, 1);
bst.Insert_R(8, 1);
bst.Insert_R(2, 1);
bst.Insert_R(6, 1);
bst.Insert_R(0, 1);
bst.Insert_R(9, 1);
bst.InOrder();
cout << "? " << bst.Find(1)->_key << endl;
cout << "? " << bst.Find(8)->_key << endl;
cout << "? " << bst.Find(22) << endl;
/*
bst.Remove_R(1);
bst.Remove_R(2);
bst.Remove_R(3);
bst.Remove_R(4);
*/
bst.Remove_R(5);
bst.Remove_R(6);
bst.Remove_R(7);
bst.Remove_R(8);
bst.Remove_R(9);
bst.Remove_R(0);
if(bst.Empty())
cout << "此二叉搜索樹為空" << endl;
bst.InOrder();
}
void TestBSTree_string() // int string
{
BSTree bst;
bst.Insert(5, "zhou");
bst.Insert(3, "sun");
bst.Insert(4, "li");
bst.Insert(1, "zhao");
bst.Insert(7, "zheng");
bst.Insert(8, "wang");
bst.Insert(2, "qian");
bst.Insert(6, "wu");
bst.Insert(0, "baijiaxing");
bst.Insert(9, "feng");
bst.InOrder();
cout << "? " << bst.Find(1)->_key << endl;
cout << "? " << bst.Find(8)->_key << endl;
cout << "? " << bst.Find(22) << endl;
//bst.Remove(0);
//bst.Remove(1);
//bst.Remove(2);
//bst.Remove(3);
//bst.Remove(4);
bst.Remove(5);
bst.Remove(6);
bst.Remove(7);
bst.Remove(8);
bst.Remove(9);
if(bst.Empty())
cout << "此二叉搜索樹為空" << endl;
bst.InOrder();
}
本文名稱：【二叉樹】二叉搜索樹
轉(zhuǎn)載源于：
http://weahome.cn/article/ijciop.html
重慶分公司
重慶分公司
