二叉搜索树又称二叉排序树，具有以下性质：
1.若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2.若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树
注意：二叉搜索树中序遍历的结果是有序的
高度：从根到叶子的单一路径上，大节点个数为高度，H=log(n)
class BST
{struct BSTNode
{ BSTNode* left;
BSTNode* right;
BSTNode* parent;
float value;
BSTNode(float _value, BSTNode* _left = nullptr, BSTNode* _right = nullptr, BSTNode* _parent = nullptr)
:left(_left), right(_right), parent(_parent), value(_value)
{ }
};
BSTNode* root = nullptr;
BSTNode* find(BSTNode* _node, float _value);
void transplant(BSTNode* found, BSTNode* replacement);
BSTNode* predecessor(BSTNode*);
BSTNode* successor(BSTNode*);
bool isALeaf(BSTNode* _node);
BSTNode* splitNode(float _min,float _max);
public:
BST() {}
BST(std::vector_values, const unsigned int _index = 0);
void insert(float _value);
bool find(float _value);
//范围查询
void find(const float _min, const float _max, std::vector& _list);;
bool remove(float _value);
BSTNode* minimun(BSTNode* _node = nullptr);
BSTNode* maximun(BSTNode* _node = nullptr);
bool predecessor(float _value, float& _predecessor);
bool successor(float _value, float& successor);
//前中后序遍历
void preOrderTraves(BSTNode*, std::vector&);
void inOrderTraves(BSTNode*, std::vector&);
void postOrderTraves(BSTNode*, std::vector&);
}; 
void insert(float _value)
{if (!root)
{root = new BSTNode(_value);
return;
}
else
{auto temp = root;
while (temp)
{ if (_value< temp->value)
{ if (temp->left)
temp = temp->left;
else
{temp->left = new BSTNode(_value);
break;
}
}
else
{ if (temp->right)
temp = temp->right;
else
{temp->right = new BSTNode(_value);
break;
}
}
}
}
}void yhaida::BST::preOrderTraves(BSTNode* _node, std::vector& _list)
{if (!_node) return;
_list.push_back(_node->value);
preOrderTraves(_node->left,_list);
preOrderTraves(_node->right, _list);
}
void yhaida::BST::inOrderTraves(BSTNode* _node, std::vector& _list)
{if (!_node) return;
preOrderTraves(_node->left, _list);
_list.push_back(_node->value);
preOrderTraves(_node->right, _list);
}
void yhaida::BST::postOrderTraves(BSTNode* _node, std::vector& _list)
{if (!_node) return;
preOrderTraves(_node->left, _list);
preOrderTraves(_node->right, _list);
_list.push_back(_node->value);
} BST::BSTNode* BST::find(BSTNode* _node, float _value)
{auto current = _node;
while (current && current->value!= _value)
{if (current->value< _value)
current = current->right;
else
current = current->right;
}
return current;
}
bool :BST::find(float _value)
{auto result = find(root, _value);
if (!result)
return false;
return true;
}float BST::minimun(BSTNode* _node)
{if (!_node)
_node = root;
auto temp = _node;
while (temp->left)
temp = temp->left;
return temp->value;
}
float BST::maximun(BSTNode* _node)
{if (!_node)
_node = root;
auto temp = _node;
while (temp->right)
temp = temp->right;
return temp->value;
}private:
BST::BSTNode* BST::predecessor(BSTNode* _node)
{if (_node->left)
return maximun(_node->left);
else
{auto temp = _node;
while (temp->parent&& temp == temp->parent->left)
{ temp = temp->parent;
}
return temp->parent;
}
}
BST::BSTNode* BST::successor(BSTNode* _node)
{if (_node->right)
return minimun(_node->right);
else
{auto temp = _node;
while (temp->parent && temp == temp->parent->right)
{ temp = temp->parent;
}
return temp->parent;
}
return nullptr;
}
public:
bool BST::predecessor(float _value, float& _predecessor)
{auto val_ptr = find(root, _value);
if (!val_ptr)
return false;
auto ret = predecessor(val_ptr);
if (!ret)
return false;
_predecessor = ret->value;
return true;
}
bool BST::successor(float _value, float& _successor)
{auto val_ptr = find(root, _value);
if (!val_ptr)
return false;
auto ret = successor(val_ptr);
if (!ret)
return false;
_successor = ret->value;
return true;
}bool BST::remove(float _value)
{BSTNode* current_node = find(root, _value);
if (current_node)
{BSTNode* current_left = current_node->left;
BSTNode* current_right = current_node->right;
if (isALeaf(current_node))
{ transplant(current_left, nullptr);
}
else if (!current_left)
{ transplant(current_left, current_right);
}
else if (!current_right)
{ transplant(current_left, current_left);
}
else
{ BSTNode* right_min = minimun(current_right);
if (right_min->parent != current_node)
{ transplant(right_min, right_min->right);
right_min->right = current_right;
right_min->right->parent = right_min;
}
transplant(current_node, right_min);
right_min->left = current_left->left;
right_min->left->parent = right_min;
}
}
return false;
}
BST::BSTNode* BST::splitNode(float _min, float _max)
{auto v = root;
while (!isALeaf(v) && (_max<= v->value||_min>=v->value))
{if (_max<= v->value)
v = v->left;
else
v = v->right;
}
return v;
}
//***************************************************************************
void BST::find(const float _min, const float _max, std::vector& _list)
{auto v_split = splitNode(_min, _max);
if (isALeaf(v_split))
{if (v_split->value >= _min && v_split->value< _max)
_list.push_back(v_split->value);
}
else
{//左子树
auto v = v_split->left;
while (!isALeaf(v))
{ if (v->value >= _min)
{ inOrderTraves(v->right, _list);
_list.push_back(v->value);
v = v->left;
}
else
{ v = v->right;
}
}
if (v->value >= _min)
_list.push_back(v->value);
//右子树
auto v = v_split->right;
while (!isALeaf(v))
{ if (v->value<= _max)
{ inOrderTraves(v->left, _list);
_list.push_back(v->value);
v = v->right;
}
else
{ v = v->left;
}
}
if (v->value<= _max)
_list.push_back(v->value);
}
} 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
