C++ 二叉搜索樹(BST)的實(shí)現(xiàn)方法
更新時間：2017年04月20日 11:43:16 投稿：mrr
這篇文章主要介紹了C++ 二叉搜索樹(BST)的實(shí)現(xiàn)方法，非常不錯，具有參考借鑒價(jià)值，需要的的朋友參考下
廢話不多說了，直接給大家貼代碼了，具體代碼如下所示：
class BST
{
public:
struct Node
{
int key;//節(jié)點(diǎn)的key
int value;//節(jié)點(diǎn)的value
Node* left;
Node *right;
int N;//節(jié)點(diǎn)的葉子節(jié)點(diǎn)數(shù)目
Node(int _key, int _value, int _N)
{
key = _key;
value = _value;
N = _N;
}
};
BST();
~BST();
void put(int key, int value);
int get(int key);
int deleteKey(int key);
private:
Node* _deleteKey(int key, Node *x);
Node* _deleteMin(Node *x);
int size(Node *x);
int _get(int key, Node* x);
Node * _put(int key, int value,Node *x);
Node * min(Node *x);
Node* root;
};
inline int BST::size(Node * x)
{
if (x == nullptr)return 0;
return x->N;
}
int BST::_get(int key, Node * x)
{
if (x == nullptr)return 0;
if (x->key < key)_get(key, x->right);
else if (x->key > key)_get(key, x->left);
else {
return x->value;
}
return 0;
}
BST::Node* BST::_put(int key, int value, Node * x)
{
if (x == nullptr) {
Node *tmp = new Node(key, value, 1);
return tmp;
}
if (x->key > key) {
x->left=_put(key, value, x->left);
}
else if (x->key < key) {
x->right=_put(key, value, x->right);
}
else x->key = key;
x->N = size(x->left) + size(x->right) + 1;
return x;
}
BST::Node* BST::min(Node * x)
{
if (x->left == nullptr)return x;
return min(x->left);
}
BST::BST()
{
}
BST::~BST()
{
}
void BST::put(int key, int value)
{
root=_put(key, value, root);
}
int BST::get(int key)
{
return _get(key, root);
}
BST::Node* BST::_deleteKey(int key, Node * x)
{
if (x->key > key)x->left = _deleteKey(key, x->left);
else if (x->key < key)x->right = _deleteKey(key, x->right);
else {
if (x->left == nullptr)return x->right;
else if (x->right == nullptr)return x->left;
else {
Node *tmp = x;
x = min(tmp->right);
x->left = tmp->left;
x->right = _deleteMin(tmp->right);
}
}
x->N = size(x->left) + size(x->right) + 1;
return x;
}
BST::Node* BST::_deleteMin(Node * x)
{
if (x->left == nullptr)return x->right;
x->left = _deleteMin(x->left);
x->N = size(x->left) + size(x->right) + 1;
return x;
}
int BST::deleteKey(int key)
{
return _get(key, root);
}
以上所述是小編給大家介紹的C++ 二叉搜索樹(BST)的實(shí)現(xiàn)方法，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復(fù)大家的。在此也非常感謝大家對腳本之家網(wǎng)站的支持！
相關(guān)文章
今天小編就為大家分享一篇關(guān)于C++小知識:用++i替代i++，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2019-01-01
這篇文章主要介紹了C/C++高精度算法的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-02-02
C語言實(shí)現(xiàn)學(xué)生信息管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)學(xué)生信息管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-07-07
C++ const的使用及this指針常方法（面試最愛問的this指針）
這篇文章主要介紹了C++ const的使用，this指針，常方法（面試最愛問的this指針）,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-04-04
這篇文章主要介紹了C++中取余運(yùn)算的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-02-02
一段C語言代碼，在編譯、鏈接和運(yùn)行的各個階段都可能會出現(xiàn)問題,下面這篇文章主要給大家介紹了關(guān)于C++中新手容易犯的十種編程錯誤的相關(guān)資料,需要的朋友可以參考下2021-10-10
access檢查用戶對一個文件的權(quán)限情況，根據(jù)mode的值檢查調(diào)用進(jìn)程對文件pathname是否具有讀、寫、或執(zhí)行的權(quán)限2013-08-08
C語言實(shí)現(xiàn)靜態(tài)版通訊錄的代碼分享
這篇文章主要為大家詳細(xì)介紹了如何利用C語言實(shí)現(xiàn)一個簡單的靜態(tài)版通訊錄，主要運(yùn)用了結(jié)構(gòu)體，一維數(shù)組，函數(shù)，分支與循環(huán)語句等等知識，需要的可以參考一下2023-01-01
future和promise的作用是在不同線程之間傳遞數(shù)據(jù)，這篇文章主要為大家詳細(xì)介紹了C++中future和promise的具體使用，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-05-05
這篇文章主要介紹了如何利用Matlab繪制中國地圖，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)Matlab有一定的幫助，感興趣的小伙伴可以學(xué)習(xí)一下2022-02-02