578 lines
9.5 KiB
C++
578 lines
9.5 KiB
C++
|
#pragma once
|
|||
|
|
|||
|
#include <iostream>
|
|||
|
#include <stack>
|
|||
|
#include <queue>
|
|||
|
|
|||
|
namespace Lenyiin
|
|||
|
{
|
|||
|
template <class K, class V>
|
|||
|
struct BSTreeNode
|
|||
|
{
|
|||
|
BSTreeNode(const K& key = K(), const V& value = V())
|
|||
|
: _key(key), _value(value), _left(nullptr), _right(nullptr)
|
|||
|
{
|
|||
|
}
|
|||
|
|
|||
|
K _key;
|
|||
|
V _value;
|
|||
|
BSTreeNode<K, V>* _left;
|
|||
|
BSTreeNode<K, V>* _right;
|
|||
|
};
|
|||
|
|
|||
|
template <class K, class V>
|
|||
|
class BSTree
|
|||
|
{
|
|||
|
private:
|
|||
|
typedef BSTreeNode<K, V> Node;
|
|||
|
|
|||
|
Node* _Copy(Node* root)
|
|||
|
{
|
|||
|
if (root == nullptr)
|
|||
|
{
|
|||
|
return nullptr;
|
|||
|
}
|
|||
|
|
|||
|
Node* cur = new Node(root->_key, root->_value);
|
|||
|
cur->_left = _Copy(root->_left);
|
|||
|
cur->_right = _Copy(root->_right);
|
|||
|
|
|||
|
return cur;
|
|||
|
}
|
|||
|
|
|||
|
public:
|
|||
|
// Ĭ<>Ϲ<EFBFBD><CFB9><EFBFBD>
|
|||
|
BSTree()
|
|||
|
: _root(nullptr)
|
|||
|
{}
|
|||
|
|
|||
|
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
BSTree(const BSTree<K, V>& tree)
|
|||
|
{
|
|||
|
_root = _Copy(tree._root);
|
|||
|
}
|
|||
|
|
|||
|
// <20>ǵݹ<C7B5><DDB9><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
//bool Insert(const K& key, const V& value)
|
|||
|
//{
|
|||
|
// // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ϊ<EFBFBD><CEAA>, ֱ<>Ӳ<EFBFBD><D3B2><EFBFBD>
|
|||
|
// if (_root == nullptr)
|
|||
|
// {
|
|||
|
// _root = new Node(key, value);
|
|||
|
// return true;
|
|||
|
// }
|
|||
|
|
|||
|
// // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ϊ<EFBFBD><CEAA>, <20>ҵ<EFBFBD><D2B5><EFBFBD><EFBFBD><EFBFBD>λ<EFBFBD><CEBB>
|
|||
|
// Node* parent = nullptr;
|
|||
|
// Node* cur = _root;
|
|||
|
// while (cur)
|
|||
|
// {
|
|||
|
// if (cur->_key > key)
|
|||
|
// {
|
|||
|
// parent = cur;
|
|||
|
// cur = cur->_left;
|
|||
|
// }
|
|||
|
// else if (cur->_key < key)
|
|||
|
// {
|
|||
|
// parent = cur;
|
|||
|
// cur = cur->_right;
|
|||
|
// }
|
|||
|
// else
|
|||
|
// {
|
|||
|
// return false; // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>, <20><>ʾ<EFBFBD><CABE><EFBFBD>Ѿ<EFBFBD><D1BE><EFBFBD><EFBFBD><EFBFBD>, <20><><EFBFBD><EFBFBD>Ҫ<EFBFBD><D2AA><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
// }
|
|||
|
// }
|
|||
|
|
|||
|
// // <20><><EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD>
|
|||
|
// cur = new Node(key, value);
|
|||
|
// if (parent->_key > key)
|
|||
|
// {
|
|||
|
// parent->_left = cur;
|
|||
|
// }
|
|||
|
// else
|
|||
|
// {
|
|||
|
// parent->_right = cur;
|
|||
|
// }
|
|||
|
|
|||
|
// return true;
|
|||
|
//}
|
|||
|
|
|||
|
// <20>ݹ<EFBFBD><DDB9><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
Node* _insert(Node* root, const K& key, const V& value)
|
|||
|
{
|
|||
|
if (root == nullptr)
|
|||
|
{
|
|||
|
return new Node(key, value);
|
|||
|
}
|
|||
|
if (key < root->_key)
|
|||
|
{
|
|||
|
root->_left = _insert(root->_left, key, value);
|
|||
|
}
|
|||
|
else if (key > root->_key)
|
|||
|
{
|
|||
|
root->_right = _insert(root->_right, key, value);
|
|||
|
}
|
|||
|
return root;
|
|||
|
}
|
|||
|
|
|||
|
// <20><><EFBFBD><EFBFBD>
|
|||
|
void Insert(const K& key, const V& value)
|
|||
|
{
|
|||
|
_root = _insert(_root, key, value);
|
|||
|
}
|
|||
|
|
|||
|
// <20>ǵݹ<C7B5><DDB9><EFBFBD><EFBFBD>ҽڵ<D2BD>
|
|||
|
//Node* Find(const K& key)
|
|||
|
//{
|
|||
|
// Node* cur = _root;
|
|||
|
// while (cur)
|
|||
|
// {
|
|||
|
// if (cur->_key > key)
|
|||
|
// {
|
|||
|
// cur = cur->_left;
|
|||
|
// }
|
|||
|
// else if (cur->_key < key)
|
|||
|
// {
|
|||
|
// cur = cur->_right;
|
|||
|
// }
|
|||
|
// else
|
|||
|
// {
|
|||
|
// return cur;
|
|||
|
// }
|
|||
|
// }
|
|||
|
// return nullptr;
|
|||
|
//}
|
|||
|
|
|||
|
// <20>ݹ<EFBFBD><DDB9><EFBFBD><EFBFBD>ҽڵ<D2BD>
|
|||
|
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
Node* _find(Node* root, const K& key)
|
|||
|
{
|
|||
|
if (root == nullptr || root->_key == key)
|
|||
|
{
|
|||
|
return root;
|
|||
|
}
|
|||
|
if (key < root->_key)
|
|||
|
{
|
|||
|
return _find(root->_left, key);
|
|||
|
}
|
|||
|
else
|
|||
|
{
|
|||
|
return _find(root->_right, key);
|
|||
|
}
|
|||
|
}
|
|||
|
|
|||
|
// <20><><EFBFBD>ҽڵ<D2BD>
|
|||
|
Node* Find(const K& key)
|
|||
|
{
|
|||
|
return _find(_root, key);
|
|||
|
}
|
|||
|
|
|||
|
// <20>ǵݹ<C7B5>ɾ<EFBFBD><C9BE><EFBFBD>ڵ<EFBFBD>
|
|||
|
//bool Erase(const K& key)
|
|||
|
//{
|
|||
|
// // <20>ҵ<EFBFBD>Ҫɾ<D2AA><C9BE><EFBFBD>Ľڵ<C4BD>
|
|||
|
// Node* parent = nullptr;
|
|||
|
// Node* cur = _root;
|
|||
|
// while (cur)
|
|||
|
// {
|
|||
|
// if (cur->_key > key)
|
|||
|
// {
|
|||
|
// parent = cur;
|
|||
|
// cur = cur->_left;
|
|||
|
// }
|
|||
|
// else if (cur->_key < key)
|
|||
|
// {
|
|||
|
// parent = cur;
|
|||
|
// cur = cur->_right;
|
|||
|
// }
|
|||
|
// else
|
|||
|
// {
|
|||
|
// break;
|
|||
|
// }
|
|||
|
// }
|
|||
|
|
|||
|
// // û<>ҵ<EFBFBD>
|
|||
|
// if (cur == nullptr)
|
|||
|
// {
|
|||
|
// return false;
|
|||
|
// }
|
|||
|
|
|||
|
// // <20>ҵ<EFBFBD><D2B5><EFBFBD>
|
|||
|
// // 1. Ҫɾ<D2AA><C9BE><EFBFBD>Ľڵ<C4BD>û<EFBFBD><C3BB><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
// if (cur->_left == nullptr)
|
|||
|
// {
|
|||
|
// if (cur == _root)
|
|||
|
// {
|
|||
|
// _root = cur->_right;
|
|||
|
// }
|
|||
|
// else
|
|||
|
// {
|
|||
|
// if (parent->_left == cur)
|
|||
|
// {
|
|||
|
// parent->_left = cur->_right;
|
|||
|
// }
|
|||
|
// else
|
|||
|
// {
|
|||
|
// parent->_right = cur->_right;
|
|||
|
// }
|
|||
|
// }
|
|||
|
// delete cur;
|
|||
|
// }
|
|||
|
// // 2. Ҫɾ<D2AA><C9BE><EFBFBD>Ľڵ<C4BD>û<EFBFBD><C3BB><EFBFBD>Һ<EFBFBD><D2BA><EFBFBD>
|
|||
|
// else if (cur->_right == nullptr)
|
|||
|
// {
|
|||
|
// if (cur == _root)
|
|||
|
// {
|
|||
|
// _root = cur->_left;
|
|||
|
// }
|
|||
|
// else
|
|||
|
// {
|
|||
|
// if (parent->_left == cur)
|
|||
|
// {
|
|||
|
// parent->_left = cur->_left;
|
|||
|
// }
|
|||
|
// else
|
|||
|
// {
|
|||
|
// parent->_right = cur->_left;
|
|||
|
// }
|
|||
|
// }
|
|||
|
// delete cur;
|
|||
|
// }
|
|||
|
// // 3. <20><><EFBFBD>Ҷ<EFBFBD><D2B6><EFBFBD>Ϊ<EFBFBD><CEAA>, <20><><EFBFBD><EFBFBD>ֱ<EFBFBD><D6B1>ɾ<EFBFBD><C9BE>, ʹ<><CAB9><EFBFBD>滻<EFBFBD><E6BBBB>ɾ<EFBFBD><C9BE>
|
|||
|
// // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD><DAB5><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>С<EFBFBD>ڵ<EFBFBD>ȥ<EFBFBD><C8A5><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
// else
|
|||
|
// {
|
|||
|
// // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>С<EFBFBD>ڵ<EFBFBD>
|
|||
|
// Node* rightMinParent = cur;
|
|||
|
// Node* rightMin = cur->_right;
|
|||
|
// while (rightMin->_left)
|
|||
|
// {
|
|||
|
// rightMinParent = rightMin;
|
|||
|
// rightMin = rightMin->_left;
|
|||
|
// }
|
|||
|
|
|||
|
// // <20>滻ɾ<E6BBBB><C9BE><EFBFBD>Ľڵ<C4BD>
|
|||
|
// std::swap(cur->_key, rightMin->_key);
|
|||
|
// std::swap(cur->_value, rightMin->_value);
|
|||
|
|
|||
|
// // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ת<EFBFBD><D7AA><EFBFBD><EFBFBD>ɾ<EFBFBD><C9BE> rightMin
|
|||
|
// if (rightMinParent->_left == rightMin)
|
|||
|
// {
|
|||
|
// rightMinParent->_left = rightMin->_right;
|
|||
|
// }
|
|||
|
// else
|
|||
|
// {
|
|||
|
// rightMinParent->_right = rightMin->_right;
|
|||
|
// }
|
|||
|
|
|||
|
// delete rightMin;
|
|||
|
// }
|
|||
|
|
|||
|
// return true;
|
|||
|
//}
|
|||
|
|
|||
|
// <20>ݹ<EFBFBD>ɾ<EFBFBD><C9BE><EFBFBD>ڵ<EFBFBD>
|
|||
|
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
Node* _erase(Node* root, const K& key)
|
|||
|
{
|
|||
|
if (root == nullptr)
|
|||
|
{
|
|||
|
return root;
|
|||
|
}
|
|||
|
if (key < root->_key)
|
|||
|
{
|
|||
|
root->_left = _erase(root->_left, key);
|
|||
|
}
|
|||
|
else if (key > root->_key)
|
|||
|
{
|
|||
|
root->_right = _erase(root->_right, key);
|
|||
|
}
|
|||
|
else
|
|||
|
{
|
|||
|
if (root->_left == nullptr)
|
|||
|
{
|
|||
|
Node* ret = root->_right;
|
|||
|
delete root;
|
|||
|
return ret;
|
|||
|
}
|
|||
|
if (root->_right == nullptr)
|
|||
|
{
|
|||
|
Node* ret = root->_left;
|
|||
|
delete root;
|
|||
|
return ret;
|
|||
|
}
|
|||
|
Node* minNode = getMin(root->_right);
|
|||
|
root->_key = minNode->_key;
|
|||
|
root->_right = _erase(root->_right, minNode->_key);
|
|||
|
}
|
|||
|
return root;
|
|||
|
}
|
|||
|
|
|||
|
Node* getMin(Node* node)
|
|||
|
{
|
|||
|
while (node->_left != nullptr)
|
|||
|
{
|
|||
|
node = node->_left;
|
|||
|
}
|
|||
|
return node;
|
|||
|
}
|
|||
|
|
|||
|
// ɾ<><C9BE><EFBFBD>ڵ<EFBFBD>
|
|||
|
void Erase(const K& key)
|
|||
|
{
|
|||
|
_erase(_root, key);
|
|||
|
}
|
|||
|
|
|||
|
// <20>ݹ<EFBFBD><DDB9><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
//void _InOrder(Node* root)
|
|||
|
//{
|
|||
|
// if (root == nullptr)
|
|||
|
// {
|
|||
|
// return;
|
|||
|
// }
|
|||
|
|
|||
|
// _InOrder(root->_left);
|
|||
|
// //std::cout << root->_key << " : " << root->_value << std::endl;
|
|||
|
// std::cout << root->_key << " ";
|
|||
|
// _InOrder(root->_right);
|
|||
|
//}
|
|||
|
|
|||
|
//void InOrder()
|
|||
|
//{
|
|||
|
// _InOrder(_root);
|
|||
|
// std::cout << std::endl;
|
|||
|
//}
|
|||
|
|
|||
|
// <20>ǵݹ<C7B5><DDB9><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
void InOrder()
|
|||
|
{
|
|||
|
std::stack<Node*> stack;
|
|||
|
Node* cur = _root;
|
|||
|
|
|||
|
while (cur != nullptr || !stack.empty()) {
|
|||
|
// <20>ҵ<EFBFBD><D2B5><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ߵĽڵ<C4BD>
|
|||
|
while (cur != nullptr) {
|
|||
|
stack.push(cur);
|
|||
|
cur = cur->_left;
|
|||
|
}
|
|||
|
|
|||
|
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ǰ<EFBFBD>ڵ<EFBFBD>
|
|||
|
cur = stack.top();
|
|||
|
stack.pop();
|
|||
|
std::cout << cur->_key << " ";
|
|||
|
|
|||
|
// ת<><D7AA><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
cur = cur->_right;
|
|||
|
}
|
|||
|
std::cout << std::endl;
|
|||
|
}
|
|||
|
|
|||
|
// <20>ݹ<EFBFBD>ǰ<EFBFBD><C7B0><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
//void _PreOrder(Node* root)
|
|||
|
//{
|
|||
|
// if (root == nullptr)
|
|||
|
// {
|
|||
|
// return;
|
|||
|
// }
|
|||
|
|
|||
|
// std::cout << root->_key << " "; // <20><><EFBFBD>ʸ<EFBFBD><CAB8>ڵ<EFBFBD>
|
|||
|
// _PreOrder(root->_left); // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
// _PreOrder(root->_right); // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
//}
|
|||
|
|
|||
|
//void PreOrder()
|
|||
|
//{
|
|||
|
// _PreOrder(_root);
|
|||
|
// std::cout << std::endl;
|
|||
|
//}
|
|||
|
|
|||
|
// <20>ǵݹ<C7B5>ǰ<EFBFBD><C7B0><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
void PreOrder()
|
|||
|
{
|
|||
|
if (_root == nullptr)
|
|||
|
{
|
|||
|
return;
|
|||
|
}
|
|||
|
|
|||
|
std::stack<Node*> stack;
|
|||
|
stack.push(_root);
|
|||
|
|
|||
|
while (!stack.empty()) {
|
|||
|
Node* cur = stack.top();
|
|||
|
stack.pop();
|
|||
|
std::cout << cur->_key << " "; // <20><><EFBFBD>ʵ<EFBFBD>ǰ<EFBFBD>ڵ<EFBFBD>
|
|||
|
|
|||
|
// <20><>ѹ<EFBFBD><D1B9><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ѹ<EFBFBD><D1B9><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ȷ<EFBFBD><C8B7><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ȴ<EFBFBD><C8B4><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
if (cur->_right != nullptr)
|
|||
|
{
|
|||
|
stack.push(cur->_right);
|
|||
|
}
|
|||
|
if (cur->_left != nullptr) {
|
|||
|
stack.push(cur->_left);
|
|||
|
}
|
|||
|
}
|
|||
|
std::cout << std::endl;
|
|||
|
}
|
|||
|
|
|||
|
// <20>ݹ<EFBFBD><DDB9><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
//void _PostOrder(Node* root) {
|
|||
|
// if (root == nullptr)
|
|||
|
// {
|
|||
|
// return;
|
|||
|
// }
|
|||
|
|
|||
|
// _PostOrder(root->_left); // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
// _PostOrder(root->_right); // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
// std::cout << root->_key << " "; // <20><><EFBFBD>ʸ<EFBFBD><CAB8>ڵ<EFBFBD>
|
|||
|
//}
|
|||
|
|
|||
|
//void PostOrder()
|
|||
|
//{
|
|||
|
// _PostOrder(_root);
|
|||
|
// std::cout << std::endl;
|
|||
|
//}
|
|||
|
|
|||
|
// <20>ǵݹ<C7B5><DDB9><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
void PostOrder()
|
|||
|
{
|
|||
|
if (_root == nullptr)
|
|||
|
{
|
|||
|
return;
|
|||
|
}
|
|||
|
|
|||
|
std::stack<Node*> st;
|
|||
|
Node* cur = _root;
|
|||
|
Node* lastNode = nullptr; // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ʵĽڵ<C4BD>
|
|||
|
while (cur || !st.empty())
|
|||
|
{
|
|||
|
while (cur)
|
|||
|
{
|
|||
|
st.push(cur);
|
|||
|
cur = cur->_left;
|
|||
|
}
|
|||
|
|
|||
|
Node* top = st.top();
|
|||
|
if ((top->_right == nullptr) || (lastNode == top->_right))
|
|||
|
{
|
|||
|
std::cout << top->_key << " ";
|
|||
|
lastNode = top;
|
|||
|
st.pop();
|
|||
|
}
|
|||
|
else {
|
|||
|
cur = top->_right;
|
|||
|
}
|
|||
|
}
|
|||
|
std::cout << std::endl;
|
|||
|
}
|
|||
|
|
|||
|
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
void LevelOrder()
|
|||
|
{
|
|||
|
if (_root == nullptr)
|
|||
|
{
|
|||
|
return;
|
|||
|
}
|
|||
|
|
|||
|
std::queue<Node*> queue;
|
|||
|
queue.push(_root);
|
|||
|
|
|||
|
while (!queue.empty())
|
|||
|
{
|
|||
|
Node* cur = queue.front();
|
|||
|
queue.pop();
|
|||
|
std::cout << cur->_key << " "; // <20><><EFBFBD>ʵ<EFBFBD>ǰ<EFBFBD>ڵ<EFBFBD>
|
|||
|
|
|||
|
if (cur->_left != nullptr) {
|
|||
|
queue.push(cur->_left); // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ѹ<EFBFBD><D1B9><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
}
|
|||
|
if (cur->_right != nullptr) {
|
|||
|
queue.push(cur->_right); // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ѹ<EFBFBD><D1B9><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
|
|||
|
}
|
|||
|
}
|
|||
|
std::cout << std::endl;
|
|||
|
}
|
|||
|
|
|||
|
// <20><><EFBFBD><EFBFBD>ǰ<EFBFBD><C7B0><EFBFBD>ڵ<EFBFBD>
|
|||
|
Node* findMax(Node* node)
|
|||
|
{
|
|||
|
while (node->_right != nullptr)
|
|||
|
{
|
|||
|
node = node->_right;
|
|||
|
}
|
|||
|
return node;
|
|||
|
}
|
|||
|
|
|||
|
Node* FindPredecessor(Node* node)
|
|||
|
{
|
|||
|
if (node->_left != nullptr)
|
|||
|
{
|
|||
|
return findMax(node->_left);
|
|||
|
}
|
|||
|
|
|||
|
Node* cur = _root;
|
|||
|
Node* predecessor = nullptr;
|
|||
|
while (cur != nullptr)
|
|||
|
{
|
|||
|
if (node->_key < cur->_key)
|
|||
|
{
|
|||
|
cur = cur->_left;
|
|||
|
}
|
|||
|
else if (node->_key > cur->_key)
|
|||
|
{
|
|||
|
predecessor = cur;
|
|||
|
cur = cur->_right;
|
|||
|
}
|
|||
|
else
|
|||
|
{
|
|||
|
break;
|
|||
|
}
|
|||
|
}
|
|||
|
return predecessor;
|
|||
|
}
|
|||
|
|
|||
|
// <20><><EFBFBD>Һ<EFBFBD><D2BA>̽ڵ<CCBD>
|
|||
|
Node* findMin(Node* node)
|
|||
|
{
|
|||
|
while (node->_left != nullptr)
|
|||
|
{
|
|||
|
node = node->_left;
|
|||
|
}
|
|||
|
return node;
|
|||
|
}
|
|||
|
|
|||
|
Node* FindSuccessor(Node* node)
|
|||
|
{
|
|||
|
if (node->_right != nullptr)
|
|||
|
{
|
|||
|
return findMin(node->_right);
|
|||
|
}
|
|||
|
|
|||
|
Node* cur = _root;
|
|||
|
Node* successor = nullptr;
|
|||
|
while (cur != nullptr)
|
|||
|
{
|
|||
|
if (node->_key < cur->_key)
|
|||
|
{
|
|||
|
successor = cur;
|
|||
|
cur = cur->_left;
|
|||
|
}
|
|||
|
else if (node->_key > cur->_key)
|
|||
|
{
|
|||
|
cur = cur->_right;
|
|||
|
}
|
|||
|
else
|
|||
|
{
|
|||
|
break;
|
|||
|
}
|
|||
|
}
|
|||
|
return successor;
|
|||
|
}
|
|||
|
|
|||
|
private:
|
|||
|
Node* _root = nullptr;
|
|||
|
};
|
|||
|
}
|