二叉樹搜索樹又叫二叉排序樹,它還有可能為一個(gè)空樹。搜索二叉樹的性質(zhì)有
目前創(chuàng)新互聯(lián)已為數(shù)千家的企業(yè)提供了網(wǎng)站建設(shè)、域名、虛擬空間、網(wǎng)站托管維護(hù)、企業(yè)網(wǎng)站設(shè)計(jì)、太和網(wǎng)站維護(hù)等服務(wù),公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略,正道將秉承"和諧、參與、激情"的文化,與客戶和合作伙伴齊心協(xié)力一起成長(zhǎng),共同發(fā)展。templatestruct BSTreeNode
{BSTreeNode* _left;
BSTreeNode* _right;
k _key;
BSTreeNode(const k& key)
:_left(nullptr)
, _right(nullptr)
, _key(key)
{}
};
templatestruct BSTree
{typedef BSTreeNodeNode;
public:
BSTree()
:_root(nullptr)
{}
bool Insert(const k& key)
{if (_root == nullptr)
{ _root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* 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;
}
}
cur = new Node(key);
if (parent->_key >key)
{ parent->_left = cur;
}
else
{ parent->_right = cur;
}
return true;
}
bool Find(const k& key)
{if (_root == nullptr)
{ return false;
}
Node* cur = _root;
while (cur)
{ if (cur->_key >key)
{ cur = cur->_left;
}
else if (cur->_key< key)
{ cur = cur->_right;
}
else
{ return true;
}
}
return false;
}
bool Erase(const k& key)
{Node* pertent = nullptr;
Node* cur = _root;
//先找到要?jiǎng)h除的
while (cur)
{ if (cur->_key >key)
{ pertent = cur;
cur = cur->_left;
}
else if (cur->_key< key)
{ pertent = cur;
cur = cur->_right;
}
//找到了
else
{ //開始刪除
//左為空,托孤右
if (cur->_left == nullptr)
{if (pertent == nullptr)
{_root = cur->_right;
}
else
{if (pertent->_left == cur)
{ pertent->left = cur->_right;
}
else
{ pertent->_right = cur->_right
}
}
delete cur;
}
//右為空,托孤左
else if (cur->_right == nullptr)
{if (pertent == nullptr)
{_root->_left;
}
else
{if (pertent->_left == cur)
{ pertent->left = cur->_left;
}
else
{ pertent->_right = cur->_left;
}
}
delete cur;
}
//左右均不為空,替換法刪除
else
{//左子樹的最右節(jié)點(diǎn)
Node* minpertent = cur;
Node* min = cur->_left;
while (min->right)
{minpertent = min;
min = min->_right;
}
cur->_key = min->_key;//交換
if (minpertent->_left == min)
{minpertent->_left = min->_left;
}
else
{minpertent->_right = min->_left;
}
delete min;
}
}
}
return false;
}
void Inorder()
{_Inorder(_root);
}
void _Inorder(Node* root)
{if (root == nullptr)
{ return;
}
_Inorder(root->_left);
cout<< root->_key<< " ";
_Inorder(root->_right);
}
private:
Node* _root;
};
插入要是插入key比這個(gè)根要大,那么就去根的右樹,比根要小,那么就去左樹。直到找到一個(gè)空位置。
查找要是查找key比這個(gè)根要大,那么就去根的右樹,比根要小,那么就去左樹。直到找到,要是找不到就沒有這個(gè)值。
刪除這里的刪除才是最難的,在刪除的時(shí)候我們可以大概分為三種方式
templatestruct BSTreeNode
{BSTreeNode* _left;
BSTreeNode* _right;
k _key;
BSTreeNode(const k& key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
};
templatestruct BSTree
{typedef BSTreeNodeNode;
public:
bool InsertR(const K& key)
{return _InsertR(_root, key);
}
Node* FindR(const K& key)
{return _FindR(_root, key);
}
Node* EraseR(const K& key)
{return _EraseR(_root, key);
}
private:
bool _InsertR(Node*& root, const K& key)
{if (root == nullptr)
{ root = new Node(key);
return true;
}
if (root->_key >key)
{ _InsertR(root->_left, key);
}
if (root->_key< key)
{ _InsertR(root->_right, key);
}
return false;
}
Node* _FindR(Node* root, const K& key)
{if (root == nullptr)
{ return nullptr;
}
if (root->_key >key)
{ _FindR(root->_left, key);
}
else if (root->_key< key)
{ _FindR(root->_right, key);
}
else
{ return root;
}
}
bool _EraseR(Node*& root, const K& key)
{if (root == nullptr)
{ return false;
}
if (root->_key >key)
{ _EraseR(root->_left, key);
}
else if(root->_key< key)
{ _EraseR(root->_right, key);
}
else
{ Node* del = root;
if (root->_left == nullptr)
{ root = root->_right;
}
else if (root->_right == nullptr)
{ root = root->_left;
}
else
{ Node* min = root->_right;
while (min->_left)
{min = min->_left;
}
swap(min->_key, root->_key);
// 遞歸到右子樹去刪除
return _EraseR(root->_right, key);
}
}
delete min;
return true;
}
private:
Node* _root;
};
雖然遞歸刪除查找插入比較簡(jiǎn)單,但是僅僅在代碼量上,要是深度太深時(shí)候還是迭代比較好,不然棧幀就要爆了。
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商?創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源,準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性,企業(yè)級(jí)服務(wù)器適合批量采購(gòu),新人活動(dòng)首月15元起,快前往官網(wǎng)查看詳情吧