二叉搜索樹
1. 二叉搜索樹的概念和介紹
??二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質(zhì)的二叉樹:
??（1）若它的左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值
??（2）若它的右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值
??（3）它的左右子樹也分別為二叉搜索樹
??二叉搜索樹（Binary Search Tree）的每個(gè)節(jié)點(diǎn)包含三個(gè)屬性：鍵（key）、左孩子（lchild）和右孩子（rchild）。 鍵用于存儲(chǔ)節(jié)點(diǎn)的值，左孩子和右孩子分別指向左子樹和右子樹的根節(jié)點(diǎn)。
??二叉搜索樹的結(jié)構(gòu)類似于一個(gè)倒置的樹，最底層的節(jié)點(diǎn)位于樹的頂部，每個(gè)節(jié)點(diǎn)都有一個(gè)鍵值，并且每個(gè)節(jié)點(diǎn)的左子樹上的所有節(jié)點(diǎn)的鍵值都小于該節(jié)點(diǎn)的鍵值，而右子樹上的所有節(jié)點(diǎn)的鍵值都大于該節(jié)點(diǎn)的鍵值。這種結(jié)構(gòu)使得二叉搜索樹在處理有序數(shù)據(jù)時(shí)非常高效。
??基于以上性質(zhì)，二叉搜索樹在查找、插入和刪除操作上具有較好的效率，時(shí)間復(fù)雜度為O(logn)。
??基于二叉搜索樹的特殊結(jié)構(gòu)，二叉搜索樹的中序遍歷（Inorder Traversal）按照左子樹、根節(jié)點(diǎn)、右子樹的順序遍歷二叉樹，它會(huì)按照從大到小的順序輸出二叉樹中的所有元素。
??以下這顆二叉搜索樹的中序遍歷結(jié)果：1 3 4 6 7 8 10 13 14
?????????????
2. 二叉搜索樹的簡(jiǎn)單實(shí)現(xiàn)
??和之前的二叉樹實(shí)現(xiàn)類似，二叉搜索樹的實(shí)現(xiàn)只需要在二叉樹的實(shí)現(xiàn)基礎(chǔ)上，將左右元素根據(jù)和根節(jié)點(diǎn)的大小，重新考慮排列順序即可。
??定義二叉搜索樹的節(jié)點(diǎn)：
//搜索二叉樹創(chuàng)建節(jié)點(diǎn)
template<class K>
struct BSTreeNode
{
//左右節(jié)點(diǎn)和節(jié)點(diǎn)值key
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
//二叉樹節(jié)點(diǎn)構(gòu)造函數(shù)
BSTreeNode(const K& key)
:_left(nullptr)
, _right(nullptr)
, _key(key)
{}
};
??定義二叉搜索樹類：
//創(chuàng)建二叉搜索樹
template<class K>
class BSTree
{
//便于書寫B(tài)Node節(jié)點(diǎn)
typedef BSTreeNode<K> BNode;
public:
//二叉搜索樹構(gòu)造函數(shù)
BSTree()
:_root(nullptr)
{}
private:
BNode* _root;
};
?????????????文章來源地址http://www.zghlxwxcb.cn/news/detail-704090.html
2.1二叉搜索樹的插入
??二叉搜索樹的插入過程可以分為以下步驟：
??（1）如果二叉搜索樹為空，創(chuàng)建一個(gè)新的節(jié)點(diǎn)，并將待插入關(guān)鍵字放入新節(jié)點(diǎn)的數(shù)據(jù)域。將新節(jié)點(diǎn)作為根節(jié)點(diǎn)，左右子樹均為空。
??（2）如果二叉搜索樹非空，將待查找關(guān)鍵字與根節(jié)點(diǎn)關(guān)鍵字進(jìn)行比較。如果小于根節(jié)點(diǎn)關(guān)鍵字，則將待查找關(guān)鍵字插入左子樹中；如果大于根節(jié)點(diǎn)關(guān)鍵字，則將待查找關(guān)鍵字插入右子樹中。
??重復(fù)上述步驟，直到找到合適的位置插入待插入的關(guān)鍵字。
??在插入過程中，需要保持二叉搜索樹的性質(zhì)：任意節(jié)點(diǎn)的左子樹的所有節(jié)點(diǎn)的值都小于該節(jié)點(diǎn)的值，右子樹的所有節(jié)點(diǎn)的值都大于該節(jié)點(diǎn)的值。如果插入后破壞了這種性質(zhì)，需要進(jìn)行調(diào)整。
?
??非遞歸的實(shí)現(xiàn)：
//二叉樹插入節(jié)點(diǎn)
bool BSInsert(const K& key)
{
//如果該樹為空樹，直接創(chuàng)建節(jié)點(diǎn)
if (_root == nullptr)
{
_root = new BNode(key);
return true;
}
//找到二叉樹所在的節(jié)點(diǎn)
BNode* parent = nullptr;
BNode* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
//插入節(jié)點(diǎn)
cur = new BNode(key);
if (parent->_key > key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
?
??遞歸的實(shí)現(xiàn)：
bool _BSInsertR(BNode*& root, const K& key)//這里傳&,直接可以得到地址
{
if (root == nullptr)
{
root = new BNode(key);
return true;
}
if (root->_key < key)
{
_BSInsertR(root->_right, key);
}
else if (root->_key > key)
{
_BSInsertR(root->_left, key);
}
else
{
return false;
}
}
?????????????
2.2二叉搜索樹的查找
??二叉搜索樹的查找實(shí)現(xiàn)過程可以分為以下步驟：
??（1）將待查找關(guān)鍵字與根節(jié)點(diǎn)關(guān)鍵字進(jìn)行比較。如果相等，則找到了目標(biāo)關(guān)鍵字，查找結(jié)束。
??（2）如果待查找關(guān)鍵字小于根節(jié)點(diǎn)關(guān)鍵字，則將待查找關(guān)鍵字放入左子樹中繼續(xù)查找。
??（3）如果待查找關(guān)鍵字大于根節(jié)點(diǎn)關(guān)鍵字，則將待查找關(guān)鍵字放入右子樹中繼續(xù)查找。
??重復(fù)上述步驟，直到找到目標(biāo)關(guān)鍵字，或者搜索到了空節(jié)點(diǎn)（表示未找到目標(biāo)關(guān)鍵字）。
??在查找過程中，由于二叉搜索樹是基于二分的思想，所以每次比較都可以排除一半的搜索空間，因此時(shí)間復(fù)雜度為O(logn)。
?
??非遞歸實(shí)現(xiàn)：
//查找二叉樹的節(jié)點(diǎn)
bool BSFind(const K& key)
{
BNode* cur = _root;
while (cur)
{
if (cur->_key > key)
{
cur = cur->_left;
}
else if (cur->_key < key)
{
cur = cur->_right;
}
else
{
return true;
}
}
return false;
}
??遞歸實(shí)現(xiàn)：
bool _BSFindR(BNode* root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (root->_key < key)
{
return _BSFindR(root->_right, key);
}
else if (root->_key > key)
{
return _BSFindR(root->_left, key);
}
else
{
return true;
}
}
?????????????
2.3二叉搜索樹的遍歷
??二叉搜索樹常使用中序遍歷，而不是前序遍歷和后序遍歷。
??因?yàn)橹行虮闅v的特點(diǎn)是先訪問左子樹，然后訪問根節(jié)點(diǎn)，最后訪問右子樹。 在訪問左子樹時(shí)，先訪問左子樹的左子樹，再訪問左子樹的右子樹；在訪問右子樹時(shí)，先訪問右子樹的左子樹，再訪問右子樹的右子樹。
??二叉搜索樹中序遍歷的結(jié)果是按照從小到大的順序輸出二叉搜索樹中的所有元素。
??二叉搜索樹的中序遍歷過程可以分為以下步驟：
??（1）首先遍歷左子樹，訪問左子樹中的所有節(jié)點(diǎn)，并按照中序遍歷的順序遞歸地訪問它們的右子樹。
??（2）然后訪問根節(jié)點(diǎn)。
??（3）最后遍歷右子樹，訪問右子樹中的所有節(jié)點(diǎn)，并按照中序遍歷的順序遞歸地訪問它們的左子樹。
??遞歸實(shí)現(xiàn)：
void _BSInOrder(BNode* root)
{
if (root == nullptr)
{
return;
}
_BSInOrder(root->_left);
printf("%d ", root->_key);
_BSInOrder(root->_right);
}
?????????????
2.4二叉搜索樹的刪除
??二叉搜索樹的刪除操作可以按照以下步驟實(shí)現(xiàn)：
??（1）首先，找到要?jiǎng)h除的節(jié)點(diǎn)?？梢酝ㄟ^中序遍歷或者二分查找等方式找到要?jiǎng)h除的節(jié)點(diǎn)。
??（2）如果要?jiǎng)h除的節(jié)點(diǎn)是葉子節(jié)點(diǎn)（沒有子節(jié)點(diǎn)），直接將該節(jié)點(diǎn)從二叉搜索樹中刪除即可。
??（3）如果要?jiǎng)h除的節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)，將該節(jié)點(diǎn)的子節(jié)點(diǎn)與其父節(jié)點(diǎn)相連，刪除該節(jié)點(diǎn)即可。
??（4）如果要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，需要找到該節(jié)點(diǎn)的左子樹中的最大節(jié)點(diǎn)（或者右子樹中的最小節(jié)點(diǎn)），用該節(jié)點(diǎn)代替要?jiǎng)h除的節(jié)點(diǎn)的位置，然后刪除該最小（或最大）節(jié)點(diǎn)。
??在實(shí)現(xiàn)刪除操作時(shí)，需要注意保持二叉搜索樹的性質(zhì)，即任意節(jié)點(diǎn)的左子樹的所有節(jié)點(diǎn)的值都小于該節(jié)點(diǎn)的值，右子樹的所有節(jié)點(diǎn)的值都大于該節(jié)點(diǎn)的值。同時(shí)，刪除操作可能會(huì)導(dǎo)致二叉搜索樹的平衡被破壞，需要進(jìn)行相應(yīng)的調(diào)整操作。
??（1）當(dāng)沒有葉子結(jié)點(diǎn)，或者只有一個(gè)子節(jié)點(diǎn)的情況：
??（2）當(dāng)左右都有子節(jié)點(diǎn)的情況：
?
??非遞歸實(shí)現(xiàn)：
//刪除二叉樹中的節(jié)點(diǎn)
bool BSErase(const K& key)
{
BNode* cur = _root;
BNode* parent = nullptr;
//先要找到所刪除的節(jié)點(diǎn)
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else//找到了所要?jiǎng)h除的節(jié)點(diǎn)
{
if (cur->_left == nullptr)//當(dāng)左節(jié)點(diǎn)為空節(jié)點(diǎn)
{
if (cur == _root)//cur為根節(jié)點(diǎn)
{
_root = cur->_right;
}
else//cur不為空節(jié)點(diǎn)
{
if (parent->_right == cur)
{
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}
}
}
else if(cur->_right==nullptr)//當(dāng)右節(jié)點(diǎn)為空節(jié)點(diǎn)
{
if (cur == _root)//cur為空節(jié)點(diǎn)
{
_root = cur->_left;
}
else//cur不為空節(jié)點(diǎn)
{
if (parent->_right == cur)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
}
else//當(dāng)左右節(jié)點(diǎn)都不為空節(jié)點(diǎn)
{
//找代替節(jié)點(diǎn)
BNode* parent = cur;
BNode* leftMax = cur->_left;
while (leftMax->_right)
{
parent = leftMax;
leftMax = leftMax->_right;
}
swap(cur->_key, leftMax->_key);
if (parent->_left == leftMax)
{
parent->_left = leftMax->_left;
}
else
{
parent->_right = leftMax->_left;
}
cur=leftMax;
}
delete cur;
return true;
}
}
return false;
}
??遞歸實(shí)現(xiàn)：
bool _BSEraseR(BNode* &root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (root->_key < key)
{
_BSEraseR(root->_right, key);
}
else if (root->_key > key)
{
_BSEraseR(root->_left, key);
}
else
{
BNode* del = root;
//1.左為空
//2.右為空
//3.左右都不為空
if (root->_left == nullptr)
{
root = root->_right;
}
else if (root->_right == nullptr)
{
root = root->_left;
}
else
{
BNode* leftMax = root->_left;
while (leftMax->_right)
{
leftMax = leftMax->_right;
}
swap(root->_key, leftMax->_key);
return _BSEraseR(root->_left, key);
}
delete del;
return true;
}
}
?????????????
2.5完整代碼和測(cè)試
??完整代碼：
#pragma once
//搜索二叉樹創(chuàng)建節(jié)點(diǎn)
template<class K>
struct BSTreeNode
{
//左右節(jié)點(diǎn)和節(jié)點(diǎn)值key
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
//二叉樹節(jié)點(diǎn)構(gòu)造函數(shù)
BSTreeNode(const K& key)
:_left(nullptr)
, _right(nullptr)
, _key(key)
{}
};
//創(chuàng)建搜索二叉樹
template<class K>
class BSTree
{
//便于書寫B(tài)Node節(jié)點(diǎn)
typedef BSTreeNode<K> BNode;
public:
//搜索二叉樹構(gòu)造函數(shù)
BSTree()
:_root(nullptr)
{}
//二叉樹插入節(jié)點(diǎn)
bool BSInsert(const K& key)
{
//如果該樹為空樹，直接創(chuàng)建節(jié)點(diǎn)
if (_root == nullptr)
{
_root = new BNode(key);
return true;
}
//找到二叉樹所在的節(jié)點(diǎn)
BNode* parent = nullptr;
BNode* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
//插入節(jié)點(diǎn)
cur = new BNode(key);
if (parent->_key > key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
//查找二叉樹的節(jié)點(diǎn)
bool BSFind(const K& key)
{
BNode* cur = _root;
while (cur)
{
if (cur->_key > key)
{
cur = cur->_left;
}
else if (cur->_key < key)
{
cur = cur->_right;
}
else
{
return true;
}
}
return false;
}
//刪除二叉樹中的節(jié)點(diǎn)
bool BSErase(const K& key)
{
BNode* cur = _root;
BNode* parent = nullptr;
//先要找到所刪除的節(jié)點(diǎn)
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else//找到了所要?jiǎng)h除的節(jié)點(diǎn)
{
if (cur->_left == nullptr)//當(dāng)左節(jié)點(diǎn)為空節(jié)點(diǎn)
{
if (cur == _root)//cur為根節(jié)點(diǎn)
{
_root = cur->_right;
}
else//cur不為空節(jié)點(diǎn)
{
if (parent->_right == cur)
{
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}
}
}
else if(cur->_right==nullptr)//當(dāng)右節(jié)點(diǎn)為空節(jié)點(diǎn)
{
if (cur == _root)//cur為空節(jié)點(diǎn)
{
_root = cur->_left;
}
else//cur不為空節(jié)點(diǎn)
{
if (parent->_right == cur)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
}
else//當(dāng)左右節(jié)點(diǎn)都不為空節(jié)點(diǎn)
{
//找代替節(jié)點(diǎn)
BNode* parent = cur;
BNode* leftMax = cur->_left;
while (leftMax->_right)
{
parent = leftMax;
leftMax = leftMax->_right;
}
swap(cur->_key, leftMax->_key);
if (parent->_left == leftMax)
{
parent->_left = leftMax->_left;
}
else
{
parent->_right = leftMax->_left;
}
cur=leftMax;
}
delete cur;
return true;
}
}
return false;
}
//二叉樹的中序遍歷
void BSInOrder()
{
_BSInOrder(_root);
cout << endl;
}
//遞歸實(shí)現(xiàn)二叉樹的查找
bool BSFindR(const K& key)
{
return _BSFindR(_root, key);
}
//遞歸實(shí)現(xiàn)二叉樹的插入節(jié)點(diǎn)
bool BSInsertR(const K& key)
{
return _BSInsertR(_root, key);
}
//遞歸實(shí)現(xiàn)二叉樹的刪除節(jié)點(diǎn)
bool BSEraseR(const K& key)
{
return _BSEraseR(_root, key);
}
private:
//遞歸二叉樹刪除的封裝實(shí)現(xiàn)
bool _BSEraseR(BNode* &root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (root->_key < key)
{
_BSEraseR(root->_right, key);
}
else if (root->_key > key)
{
_BSEraseR(root->_left, key);
}
else
{
BNode* del = root;
//1.左為空
//2.右為空
//3.左右都不為空
if (root->_left == nullptr)
{
root = root->_right;
}
else if (root->_right == nullptr)
{
root = root->_left;
}
else
{
BNode* leftMax = root->_left;
while (leftMax->_right)
{
leftMax = leftMax->_right;
}
swap(root->_key, leftMax->_key);
return _BSEraseR(root->_left, key);
}
delete del;
return true;
}
}
//遞歸二叉樹插入的封裝實(shí)現(xiàn)
bool _BSInsertR(BNode*& root, const K& key)//這里傳&,直接可以得到地址
{
if (root == nullptr)
{
root = new BNode(key);
return true;
}
if (root->_key < key)
{
_BSInsertR(root->_right, key);
}
else if (root->_key > key)
{
_BSInsertR(root->_left, key);
}
else
{
return false;
}
}
//遞歸二叉樹查找的封裝實(shí)現(xiàn)
bool _BSFindR(BNode* root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (root->_key < key)
{
return _BSFindR(root->_right, key);
}
else if (root->_key > key)
{
return _BSFindR(root->_left, key);
}
else
{
return true;
}
}
//為了遞歸實(shí)現(xiàn)，進(jìn)行一層封裝
void _BSInOrder(BNode* root)
{
if (root == nullptr)
{
return;
}
_BSInOrder(root->_left);
printf("%d ", root->_key);
_BSInOrder(root->_right);
}
private:
BNode* _root;
};
?
??簡(jiǎn)單測(cè)試：
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include"BinarySearchTree.h"
void BSTree_test1()
{
BSTree<int> t;
t.BSInsert(5);
t.BSInsert(8);
t.BSInsert(6);
t.BSInsert(1);
t.BSInsert(3);
t.BSInsert(2);
t.BSInsert(4);
t.BSInOrder();
cout << "是否存在二叉樹的值為1:";
if (t.BSFind(1))cout << "存在";
else cout << "不存在";
cout << endl;
int arr[] = { 5,3,1,2,4,9,8,6,7,10 };
BSTree<int> t1;
for (auto e : arr)
{
t1.BSInsert(e);
}
t1.BSInOrder();
t1.BSErase(3);
t1.BSInOrder();
cout << "是否存在二叉樹的值為1:";
if (t1.BSFindR(1))cout << "存在";
else cout << "不存在";
cout << endl;
t1.BSInsertR(11);
t1.BSInOrder();
t1.BSEraseR(11);
t1.BSInOrder();
}
int main()
{
BSTree_test1();
return 0;
}
這里就是數(shù)據(jù)結(jié)構(gòu)中二叉搜索樹的基本介紹了??
如有錯(cuò)誤?望指正，最后祝大家學(xué)習(xí)進(jìn)步?天天開心???文章來源：http://www.zghlxwxcb.cn/news/detail-704090.html
?????????????
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】二叉搜索樹——二叉搜索樹的概念和介紹、二叉搜索樹的簡(jiǎn)單實(shí)現(xiàn)、二叉搜索樹的增刪查改的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
