【C++】搜索二叉树

1. 二叉搜索树

a. 二叉搜索树的概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

1. 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2. 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
3. 它的左右子树也分别为二叉搜索树
4. 它的中序遍历是得到的结果是升序

b. 二叉搜索树的实现

1. 搜索二叉树的构建

代码

template<class K>
struct BinNode
{
	BinNode(K key)
		:_key(key)
	{}
	K  _key;
	BinNode* left = nullptr;
	BinNode* right = nullptr;
};
template<class K>
class BinNodeTree
{
public:
	typedef BinNode<K> node;
private:
	node* _root = nullptr;
};

2. 二叉树的插入 

循环实现思路

返回类型是 bool ，判断能否插入传入的值（二叉搜索树不存相同的值）

跟节点比较，如果 插入的值 key > 节点的值，则走节点的右子树 ; 如果插入的值 key < 节点的值，则走左子树 ; 如果等于，返回 false ;如果结点为空 ，结束循环 ，new 一个新的结点，需要空节点的父节点去链接新结点，所以我们一定要定义一个父节点

注意：

1. 由于不知道新结点应该是父节点的左子树还是右子树，这里链接就需要判断一下，如果空结点是父结点的左子树，那么就链接左边，反之亦然
2. 一开始的根节点为空，所以这里需要特殊处理一下，让根节点成为插入的第一个值构造的新节点

代码

bool insert(const K &key)
{
	if (_root == nullptr)
	{
		_root = new node(key);
		return true;
	}
	node* prev = _root;
	node* cur = _root;
	while (cur)
	{
		if (key > cur->_key)
		{
			prev = cur;
			cur = cur->right;
		}
		else if (key < cur->_key)
		{
			prev = cur;
			cur = cur->left;
		}
		else
		{
			return false;
		}
	}
	cur = new node(key);
	if (key > prev->_key)
	{
		prev->right = cur;
	}
	else
	{
		prev->left = cur;
	}
	return true;
}

 递归实现思路

大体思路和循环的思路差不多，但是略有不同

1. 由于递归函数一定需要结点的地址（可以走左右子树）和 需要插入的值，给这个递归函数传入的结点的地址一定是根节点，但是根节点在类里面不能访问，所以这里我们就弄一层包装，一个函数是传根节点的地址的，另一个函数用来递归实现（都在类里面）
2. 这里我们同样需要判断插入的值 key 和 结点的值的关系，但是这里可以不需要父节点，我们在递归函数的形参上面跟之前有所不同，这里的形参用了引用，使得可以直接让空结点存新结点的地址

代码

bool Insert(const K& key)
{
	return _Insert(_root, key);
}
bool _Insert(node*& root, const K& key)
{
	if (root == nullptr)
	{
		root = new node(key);
		return true;
	}
	if (key == root->_key)
	{
		return false;
	}
	else if (key > root->_key)
	{
		_Insert(root->right, key);
	}
	else
	{
		_Insert(root->left, key);
	}
}

   3. 二叉树的查找

循环实现思路

跟节点比较，如果 插入的值 key > 节点的值，则走节点的右子树 ; 如果插入的值 key < 节点的值，则走左子树 ; 如果结点为空 return false；

代码

bool find(const K& key)
{
	node* cur = _root;
	if (cur == nullptr)
	{
		return false;
	}
	while (cur)
	{
		if (key > cur->_key)
		{
			cur = cur->right;
		}
		else if(key < cur->_key)
		{
			cur = cur->left;
		}
		else
		{
			return true;
		}
	}
	return false;
}

 

递归实现思路

和插入的递归思路有一点相同，都要封装一层

剩下的思路和循环是一样的

代码

bool Find(const K& key)
{
	return _Find(_root, key);
}
bool _Find(node* root, const K& key)
{
	if (root == nullptr)
	{
		return false;
	}
	if (key == root->_key)
	{
		return true;
	}
	else if (key > root->_key)
	{
		_Find(root->right, key);
	}
	else
	{
		_Find(root->left, key);
	}
}

4. 二叉树的删除

循环实现思路

大体上遇到的情况分三种情况：

1. 删除的结点左右子树为空
2. 删除的结点左子树或者右子树为空
3. 删除的结点左右子树都不为空

第一种情况：

实际上，第一种情况的操作可以归到第二种里面

第二种情况：

如果删除的结点左子树为空，那么我们需要这个结点的 父节点的左子树或者右子树（根据删除结点是父节点的左子树还是右子树进行判断） 是删除结点的右子树

如果删除结点是父节点的左子树，那么父节点左边链接，反之则相反

如图：

如果删除的结点右子树为空，那么我们需要这个结点的 父节点的 左子树或者右子树 （根据删除结点是父节点的左子树还是右子树进行判断）是删除结点的左子树

如果删除结点是父节点的左子树，那么父节点左边链接，反之则相反

如图：

前者我们说了，如果删除节点两边都为空，则也归到第二种，此时只要判断删除节点是父节点的左子树还是右子树就好了，无需管链接删除节点的左子树还是右子树

如图：

第三种情况：

由于两边都不为空，我们不好直接删除，这时候，我们需要把删除节点当根节点（同样构成搜索二叉树），找这个搜索二叉树的某个节点的值，既可以比左边节点的值大（除根节点外），也可以比右边节点的值小，有两个答案：这个搜索二叉树的左子树的最大值和右子树的最小值

如图：

如何找右子树的最小值呢？先得到右子树的地址，再一直往左走，直到节点为空，则它的父节点就是我们要找的，所以我们需要定义一个父节点，让删除节点存父节点的值，由于父节点的左子树为空，那么删除节点要链接父节点的右子树，跟之前第二种情况一样，要知道父节点是上一个父节点的左子树还是右子树（避免删除节点就是根节点的情况导致的错误），再删除父节点

找左子树的最大值相同道理

注意事项：

1. 第二种情况有特例，可能删除的是根节点，并且左子树或者右子树为空

如果左子树为空，这个时候我们只需要直接让根节点存右子树的地址，释放原来的节点

反之则相反（如果同样为左右子树都为空，同样适用）

如图：

1. 第三种情况一定要注意本来定义的两个指针(一前一后)，最开始初始化时，都指向删除节点的地址，不要其中一个置空（防止删除的节点是父节点，而导致置空节点不能进入循环发生的一系列错误）

代码

bool erase(const K &key)
{
	node* parent = _root;
	node* cur = _root;
	while (cur)
	{
		if (key > cur->_key)
		{
			parent = cur;
			cur = cur->right;
		}
		else if (key < cur->_key)
		{
			parent = cur;
			cur = cur->left;
		}
		else
		{
			if (cur->left == nullptr)
			{
				if (cur == _root)
				{
					_root = cur->right;
				}
				if (parent->left == cur)
				{
					parent->left = cur->right;
				}
				else
				{
					parent->right = cur->right;
				}
				delete cur;
			}
			else if (cur->right == nullptr)
			{
				if (cur == _root)
				{
					_root = cur->left;
				}
				if (parent->left == cur)
				{
					parent->left = cur->left;
				}
				else
				{
					parent->right = cur->left;
				}
				delete cur;
			}
			else
			{
				node* MinRight = cur->right;
				node* pMinRight = cur;
				while (MinRight->left)
				{
					pMinRight = MinRight;
					MinRight = MinRight->left;
				}
				cur->_key = MinRight->_key;
				if (pMinRight->left == MinRight)
				{
					pMinRight->left = MinRight->right;
				}
				else
				{
					pMinRight->right = MinRight->right;
				}
				delete MinRight;
			}
			
			return true;
		}
	}
	return false;
}

 递归实现思路

和插入的递归思路有些一样，都需要包装，都需要传指针的引用

第一种情况和第二种情况和循环思路很像，由于是引用，这里我们不需要判断是左子树还是右子树，直接赋值即可

第三种情况前面还是一样，找到左子树的最大值或者右子树的最小值

如果找左子树的最大值：

最大值我们可以在通过循环来找，找到之后，可以选择交换删除节点的值和最大值，再次进行递归，删除的值key不变

或者是只让删除节点的值换成最大值，其它不变，递归时，传的根节点就是删除节点的左子树，删除的值key就是最大值

注意：

第三种情况递归时，不可以直接传存最大值的节点（那个最大值节点是局部变量，而引用接收局部变量会出很大问题）

代码

bool Erase(const K& key)
{
	return _Erase(_root,key);
}
bool _Erase(node*& root,const K& key)
{
	if (root == nullptr)
	{
		return false;
	}
	if (key > root->_key)
	{
		_Erase(root->right, key);
	}
	else if(key < root->_key)
	{
		_Erase(root->left, key);
	}
	else
	{
		node* cur = root;
		if (root->left == nullptr)
		{
			root = root->right;
			delete cur;
		}
		else if (root->right == nullptr)
		{
			root = root->left;
			delete cur;
		}
		else
		{
			cur = cur->left;
			while (cur->right)
			{
				cur = cur->right;
			}
			int k = root->_key = cur->_key;
			_Erase(root->left, k);
		}
		return true;
	}
}

5.  二叉树的销毁

代码

~BinNodeTree()
{
	_BinNodeTree(_root);
}
void _BinNodeTree(node* root)
{
	if (root == nullptr)
	{
		return;
	}
	_BinNodeTree(root->left);
	_BinNodeTree(root->right);
	delete root;
}

后序遍历即可 

6.  二叉树的拷贝构造

代码

BinNodeTree(const BinNodeTree<K>& t)
{
	_root = copy(t._root,_root);
}
node* copy(node* t1, node* t2)
{
	if (t1 == nullptr)
	{
		return nullptr;
	}
	t2 = new node(t1->_key);
	t2->left = copy(t1->left, t2->left);
	t2->right = copy(t1->right, t2->right);
	return t2;
}

2. 二叉搜索树的应用

1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到

的值

如：查找一个单词是否拼写正确

    2. KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对，该种方

式在现实生活中非常常见

如：单词中英文查找 ， 统计单词出现次数