二叉搜索树C++实现-创新互联

二叉搜索树又称二叉排序树，具有以下性质：

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元起，快前往官网查看详情吧