【二叉樹(shù)】二叉搜索樹(shù)
二叉搜索樹(shù)：
創(chuàng)新互聯(lián)是一家專(zhuān)業(yè)提供興海企業(yè)網(wǎng)站建設(shè),專(zhuān)注與網(wǎng)站設(shè)計(jì)制作、做網(wǎng)站、html5、小程序制作等業(yè)務(wù)。10年已為興海眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專(zhuān)業(yè)的建站公司優(yōu)惠進(jìn)行中。
1.每個(gè)節(jié)點(diǎn)都有一個(gè)關(guān)鍵碼（key）作為搜索依據(jù)，關(guān)鍵碼互不相同。
2.左子樹(shù)的所有關(guān)鍵碼都小于根節(jié)點(diǎn)的關(guān)鍵碼。
3.右子樹(shù)的所有關(guān)鍵碼都大于根節(jié)點(diǎn)的關(guān)鍵碼。
4.左右子樹(shù)都是二叉搜索樹(shù)。
刪除key：左為空，右為空，左右都不空
1）左為空：cur的右樹(shù)鏈到父節(jié)點(diǎn)
2）右為空：cur的左樹(shù)鏈到父節(jié)點(diǎn)
3）左右都不空：找右樹(shù)最左節(jié)點(diǎn)或左樹(shù)最右節(jié)點(diǎn)，將找到的節(jié)點(diǎn)與cur交換后刪除它。
二叉搜索樹(shù)的增、刪、查（非遞歸及遞歸）程序代碼如下：
#pragma once
#include<string>
////注意：考慮邊界問(wèn)題_root 、左右子樹(shù)問(wèn)題（非遞歸、遞歸）、記住判空處理
template<class K,class V>
struct BSTNode
{
BSTNode<K, V>* _left; //左子數(shù)
BSTNode<K, V>* _right; //右子樹(shù)
K _key;
V _value;
//構(gòu)造函數(shù)
BSTNode(const K& key, const V& value)
:_left(NULL)
, _right(NULL)
, _key(key)
, _value(value)
{}
};
template<class K, class V>
class BSTree
{
typedef BSTNode<K, V> 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小，插入左子樹(shù)
{
if(cur->_left == NULL)
cur->_left = new Node(key, value);
else
cur = cur->_left;
}
else if(key > cur->_key) //key大，插入右子樹(shù)
{
if(cur->_right == NULL)
cur->_right = new Node(key, value);
else
cur = cur->_right;
}
else //key關(guān)鍵碼互不相同
return false;
}
return true;
}
////////////////刪除//////////////
////邊界條件判斷（無(wú)節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)）
////找key值，記錄parent。
////刪除key，分三種情況(左為空，右為空，左右都不為空)
////左右節(jié)點(diǎn)都存在，找到右樹(shù)的最左節(jié)點(diǎn)或者左樹(shù)的最右節(jié)點(diǎn)，
////將找到的節(jié)點(diǎn)與cur交換后再刪除找到的節(jié)點(diǎn)
bool Remove(const K& key)
{
//無(wú)節(jié)點(diǎn)
if(_root == NULL)
return false;
//一個(gè)節(jié)點(diǎn) _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的右子樹(shù)鏈到父節(jié)點(diǎn)
{
//注意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的左子樹(shù)鏈到父節(jié)點(diǎn)
{
if(parent == NULL)
{
_root = cur->_left;
}
else
{
if(cur = parent->_left)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
}
}
////左右節(jié)點(diǎn)都存在，找到右樹(shù)的最左節(jié)點(diǎn)或者左樹(shù)的最右節(jié)點(diǎn)
////將找到的節(jié)點(diǎn)與cur交換后再刪除找到的節(jié)點(diǎn)
else
{
parent = cur;
//右樹(shù)的最左節(jié)點(diǎn)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;
//因?yàn)樽笥夜?jié)點(diǎn)都存在，所以parent不為空
//firstLeft 左節(jié)點(diǎn)為空，右節(jié)點(diǎn)可能存在
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) //在左子樹(shù)查找
{
cur = cur->_left;
}
else if(key>cur->_key) //在右子樹(shù)查找
{
cur = cur->_right;
}
else
{
return cur;
}
}
return NULL;
}
/////////////////////遞歸實(shí)現(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é)點(diǎn)都不為空
else
{
//右子樹(shù)的最左節(jié)點(diǎn)
Node* firstLeft = root->_right;
while(firstLeft->_left)
{
firstLeft = firstLeft->_left;
}
swap(firstLeft->_key, root->_key);
swap(firstLeft->_value, root->_value);
//_Remove_R(firstLeft, key);//錯(cuò)誤，firstLeft是臨時(shí)變量不能作為遞歸的參數(shù)
_Remove_R(root->_right, key);
}
}///刪除key end
return false;
}
protected:
Node* _root;
}; 測(cè)試代碼：
void TestBSTree()
{
BSTree<int, int> 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 << "此二叉搜索樹(shù)為空" << endl;
bst.InOrder();
}
void TestBSTree_R() //遞歸
{
BSTree<int, int> 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 << "此二叉搜索樹(shù)為空" << endl;
bst.InOrder();
}
void TestBSTree_string() // int string
{
BSTree<int, string> 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 << "此二叉搜索樹(shù)為空" << endl;
bst.InOrder();
}
文章標(biāo)題：【二叉樹(shù)】二叉搜索樹(shù)
網(wǎng)頁(yè)網(wǎng)址：http://muchs.cn/article8/ijciop.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供動(dòng)態(tài)網(wǎng)站、網(wǎng)站設(shè)計(jì)公司、定制網(wǎng)站、網(wǎng)站排名、微信公眾號(hào)、商城網(wǎng)站
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)
- 網(wǎng)站維護(hù)中如何讓自己的網(wǎng)站更具營(yíng)銷(xiāo)力 2016-11-01
- 給網(wǎng)站進(jìn)行網(wǎng)站維護(hù)的作用都有哪些？ 2016-11-13
- 手機(jī)端微官網(wǎng)怎么做 2016-01-22
- 做好網(wǎng)站維護(hù)需要具備哪些知識(shí)？ 2015-07-22
- 小程序案例分析：無(wú)印良品（MUJI）的智慧零售策略 2014-04-29
- 中小企業(yè)建站應(yīng)該找什么樣公司 2014-10-31
- 網(wǎng)站維護(hù)是做什么的？ 2016-10-07
- 細(xì)節(jié)決定成敗在企業(yè)網(wǎng)站制作里也很適用 2014-07-30
- 企業(yè)網(wǎng)站維護(hù)三大事項(xiàng)及挑選公司兩大技巧 2022-08-19
- 商貿(mào)公司網(wǎng)站內(nèi)容維護(hù)，網(wǎng)站維護(hù)服務(wù)，供應(yīng)商比選文件參考 2019-11-05
- 做一個(gè)手機(jī)網(wǎng)站需要多少費(fèi)用？ 2016-08-13
- APP開(kāi)發(fā)需要多少錢(qián)呢 2016-08-26