概述

二叉搜索樹(shù)又稱(chēng)二叉排序樹(shù)，具有以下性質(zhì)：

創(chuàng)新互聯(lián)公司是一家專(zhuān)注于成都網(wǎng)站制作、成都做網(wǎng)站與策劃設(shè)計(jì),東至網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)公司做網(wǎng)站,專(zhuān)注于網(wǎng)站建設(shè)10年,網(wǎng)設(shè)計(jì)領(lǐng)域的專(zhuān)業(yè)建站公司;建站業(yè)務(wù)涵蓋:東至等地區(qū)。東至做網(wǎng)站價(jià)格咨詢:028-86922220

1.若它的左子樹(shù)不為空，則左子樹(shù)上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值
2.若它的右子樹(shù)不為空，則右子樹(shù)上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值
它的左右子樹(shù)也分別為二叉搜索樹(shù)

注意：二叉搜索樹(shù)中序遍歷的結(jié)果是有序的

高度：從根到葉子的單一路徑上，大節(jié)點(diǎn)個(gè)數(shù)為高度，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;
				}
			}
		}
	}
}

前序、中序、后續(xù)遍歷

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;
}

前驅(qū)點(diǎn)、后驅(qū)點(diǎn)

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;
}

delete

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
	{//左子樹(shù)
		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);

		//右子樹(shù)
		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);
	}
}

你是否還在尋找穩(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)查看詳情吧

本文名稱(chēng)：二叉搜索樹(shù)C++實(shí)現(xiàn)-創(chuàng)新互聯(lián)
轉(zhuǎn)載來(lái)于：http://weahome.cn/article/jjghj.html