当前位置：首页 > article >正文

二叉搜索树（附源码C++）

article 2024/11/15 14:05:29

游凡/搜索二叉树https://gitee.com/you-fan-a/search-binary-tree

一、什么是二叉搜索树？

若它的左子树不空，则左子树上所有结点的值均小于它根结点的值。
若它的右子树不空，则右子树上所有结点的值均大于它根结点的值。
它的左、右树又分为⼆叉排序树

简记：“左小，右大”

举例：

此我们对这棵树进行中序遍历，就可以得到：1、3、6、8、10

二叉树的插入代码：

bool Insert(const K& key, const V& value)
{
	if (_root == nullptr)
	{
		_root = new Node(key, value);
	}
	else
	{
		Node* parent = _root;
		Node* child = _root;
		while (child)
		{
			if (key < child->_key)
			{
				parent = child;
				child = parent->_left;
			}
			else if(key>child->_key)
			{
				parent = child;
				child = parent->_right;
			}
			else
			{
				return false;
			}
		}
		
		child = new Node(key, value);
		if (key < parent->_key)
		{
			parent->_left = child;
		}
		else if(key>parent->_key)
		{
			parent->_right = child;
		}
	}
	return true;
}

二、二叉树的查找

二叉树的查找也十分简单，就是比大小：

代码：

Node* Find(const K& key)
{
	Node* parent = _root;
	Node* child = _root;
	while (child)
	{
		if (key < child->_key)
		{
			parent = child;
			child = parent->_left;
		}
		else if (key > child->_key)
		{
			parent = child;
			child = parent->_right;
		}
		else
		{
			return child;
		}
	}
	return nullptr;
}