【数据结构】二叉搜索树

二叉搜索树，又叫二叉排序树，二叉查找树。它有以下特点：

左子树的值小于根节点的值，右子树的值大于根节点的值；二叉搜索树中序遍历的结果

就是一个升序序列。

当然，空树也是一个二叉搜索树。

全局满足二叉搜索树的性质，局部也应该满足。

既然有以上性质，那么二叉树的查找是相当方便的，当然插入和删除，复杂度也会明显

降低。

查找：从根节点开始，如果要插入的key小于根节点的key，则向左走，否则向右走，找

到了直接返回，如果已经走到空了，还没找到，说明要查找的key不存在。下边给出实现

代码：

bool FindNonR(const K& key)
	{
		if (NULL == _root)
			return false;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else
				return true;
		}
		return false;
	}

递归版本比较简单，这里就不给出实现了。

插入：找到合适的空位置，插入元素，如果要插入的值，在原来的搜索二叉树中已将存

在则不能进行插入。下边画图说明：

根据上边的图解，写出如下代码：

bool InsertNonR(const K& key)
	{
		if (NULL == _root)//空树
		{
			_root = new Node(key);
			return true;
		}
		//不是空树
		Node* cur = _root;
		Node* parent = NULL;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else//已经存在的值
			{
				return false;
			}
		}
		Node* NewNode = new Node(key);
		if (key < parent->_key)
			 parent->_left = NewNode ;
		else
			parent->_right = NewNode;
		return true;
	}

从上边的图中，我们可以看出，插入元素必须记住父节点，否则无法实现连接操作。

二叉搜索树也可以递归实现：下边给出实现代码：

bool _InsertR(Node*& root,const K& key)
	{
		if (root == NULL)
		{
			root = new Node(key);
			return true;
		}
		Node* cur = root;
		if (cur->_key < key)
		{
			_InsertR(cur->_right,key);
		}
		else if (cur->_key > key)
		{
			_InsertR(cur->_left,key);
		}
		else
			return false; 
	}

这段代码中，我们可以看出：形参中我们采用的是引用传参，这样巧妙的利用了引用的

性质：变量的别名，两者同时被修改。

当原来的树就是空树（_root == NULL），root的改变就直接影响了_root的改变；

当原来的树中已经有一些元素,（利用上图的例子，插入3）

（前边一些查找步骤省略）4的left是空，走到函数第一个if，创建一个新的结点，连在

root上，此时的root是4的left的别名，所以两者都改变了，起到了连接的作用。

删除：找到要删除的元素，进行删除，这个比较复杂，图解：

下边给出代码实现：

bool RemoveNonR(const K& key)
	{
		if (NULL == _root)
			return false;
		Node* cur = _root;
		Node* parent = NULL;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				Node* del = NULL;
				//叶子节点直接删除
				if (cur->_left == NULL && cur->_right == NULL)
				{
					if (parent && cur == parent->_left)
					{
						parent->_left = NULL;
						del = cur;
					}

					else if (parent && cur == parent->_right)
					{
						parent->_right = NULL;
						del = cur;
					}
					else
					{
						del = cur;
						_root = NULL;
					}
				}
				//只有一个孩子的结点
				else if (cur->_left == NULL || cur->_right == NULL)
				{
					//只有左孩子
					if (cur->_left != NULL)
					{
						if (parent == NULL)
						{
							_root = parent->_left;
							del = cur;
						}
						else if (parent->_left == cur)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}
					//只有右孩子
					else
					{
						if (parent == NULL)
						{
							_root = cur->_right;
							del = cur;
						}
						else if (parent->_right == cur)
						{
							parent->_right = cur->_right;
						}
						else//cur是parent的左孩子
						{
							parent->_left = cur->_right;
						}
					}
				}
				else//有两个孩子的结点
				{
					Node* tmp = cur->_right;//查找右子树的最左结点
					while (tmp && tmp->_left)
					{
						parent = tmp;
						tmp = tmp->_left;
					}
					swap(cur->_key,tmp->_key);
					//删除tmp结点
					//tmp是叶子节点 ，tmp只有一个孩子结点
					if (tmp == parent->_left)
					{
						parent->_left = tmp->_right;
					}
					else
					{
						parent->_right = tmp->_right;
					}
					del = tmp;
				}
				delete del;
				del = NULL;
				return true;
			}
		}
		//没有找到要删除的值
		return false;
	}

对于删除操作，也可以用递归实现：

代码：

bool _RemoveR(Node*& root,const K& key)
	{
		if (root == NULL)
			return false;
		
		if (root->_key < key)
		{
			_RemoveR(root->_right,key);
		}
		else if (root->_key > key)
		{
			_RemoveR(root->_left,key);
		}
		else
		{
			Node* del = root;
			Node* parent = root;
			if (root->_left == NULL)//仅有右孩子
			{
				root = root->_right;
			}
			else if (root->_right ==NULL)
			{
				root = root->_left;
			}
			else
			{
				Node* minRight = root->_right;
				//找右子树的最左结点
				while (minRight->_left)
				{
					parent = minRight;
					minRight = minRight->_left;
				}
				root->_key = minRight->_key;

				if (minRight == parent->_right)
				{
					parent->_right = minRight->_right;
				}
				else
				{
					parent->_left = minRight->_right;
				}
				del = minRight;
			}
			delete del;
		}
		return true;
	}

这段代码中，找要删除的结点是递归操作。找到之后，如果该节点只有一个孩子或者没

有孩子，直接将指向当前结点的指针指向其孩子结点或者空，利用引用，很好的连接了

起来。如果当前结点有左右孩子，利用非递归中的处理办法解决。

【完整代码】

#pragma once
#include<iostream>
using namespace std;
#include<stack>

template<typename K>
struct SearchBinaryTreeNode
{
	K _key;
	SearchBinaryTreeNode<K>* _left;
	SearchBinaryTreeNode<K>* _right;
	SearchBinaryTreeNode(const K& key)
		:_key(key),_left(NULL),_right(NULL)
	{}
};

template<typename K>
class SearchBinaryTree
{
	typedef SearchBinaryTreeNode<K> Node;
public:
	SearchBinaryTree()
		:_root(NULL)
	{}

	void InorderNonR()
	{
		_InorderNonR(_root);
	}
	void InsertR(const  K& key)
	{
		_InsertR(_root,key);
	}

	void InOrderR()
	{
		_InOrderR(_root);
		cout << endl;
	}

	void RemoveR(const K& key)
	{
		_RemoveR(_root,key);
	}
	bool RemoveNonR(const K& key)
	{
		if (NULL == _root)
			return false;
		Node* cur = _root;
		Node* parent = NULL;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				Node* del = NULL;
				//叶子节点直接删除
				if (cur->_left == NULL && cur->_right == NULL)
				{
					if (parent && cur == parent->_left)
					{
						parent->_left = NULL;
						del = cur;
					}

					else if (parent && cur == parent->_right)
					{
						parent->_right = NULL;
						del = cur;
					}
					else
					{
						del = cur;
						_root = NULL;
					}
				}
				//只有一个孩子的结点
				else if (cur->_left == NULL || cur->_right == NULL)
				{
					//只有左孩子
					if (cur->_left != NULL)
					{
						if (parent == NULL)
						{
							_root = parent->_left;
							del = cur;
						}
						else if (parent->_left == cur)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}
					//只有右孩子
					else
					{
						if (parent == NULL)
						{
							_root = cur->_right;
							del = cur;
						}
						else if (parent->_right == cur)
						{
							parent->_right = cur->_right;
						}
						else//cur是parent的左孩子
						{
							parent->_left = cur->_right;
						}
					}
				}
				else//有两个孩子的结点
				{
					Node* tmp = cur->_right;//查找右子树的最左结点
					while (tmp && tmp->_left)
					{
						parent = tmp;
						tmp = tmp->_left;
					}
					swap(cur->_key,tmp->_key);
					//删除tmp结点
					//tmp是叶子节点 ，tmp只有一个孩子结点
					if (tmp == parent->_left)
					{
						parent->_left = tmp->_right;
					}
					else
					{
						parent->_right = tmp->_right;
					}
					del = tmp;
				}
				delete del;
				del = NULL;
				return true;
			}
		}
		//没有找到要删除的值
		return false;
	}
	bool FindNonR(const K& key)
	{
		if (NULL == _root)
			return false;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else
				return true;
		}
		return false;
	}

	bool InsertNonR(const K& key)
	{
		if (NULL == _root)//空树
		{
			_root = new Node(key);
			return true;
		}
		//不是空树
		Node* cur = _root;
		Node* parent = NULL;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else//已经存在的值
			{
				return false;
			}
		}
		Node* NewNode = new Node(key);
		if (key < parent->_key)
			 parent->_left = NewNode ;
		else
			parent->_right = NewNode;
		return true;
	}
protected:
	bool _RemoveR(Node*& root,key);
		}
		else
		{
			Node* del = root;
			Node* parent = root;
			if (root->_left == NULL)//仅有右孩子
			{
				root = root->_right;
			}
			else if (root->_right ==NULL)
			{
				root = root->_left;
			}
			else
			{
				Node* minRight = root->_right;
				//找右子树的最左结点
				while (minRight->_left)
				{
					parent = minRight;
					minRight = minRight->_left;
				}
				root->_key = minRight->_key;

				if (minRight == parent->_right)
				{
					parent->_right = minRight->_right;
				}
				else
				{
					parent->_left = minRight->_right;
				}
				del = minRight;
			}
			delete del;
		}
		return true;
	}
	void _InOrderR(Node* root)
	{
		if (root == NULL)
			return;
		_InOrderR(root->_left);
		cout << root->_key << " ";
		_InOrderR(root->_right);
	}
	bool _InsertR(Node*& root,key);
		}
		else
			return false; 
	}
	void _InorderNonR(Node* root)
	{
		if (NULL != root)
		{
			Node* cur = root;
			stack<Node*> s;
			while (cur || !s.empty())
			{
				while (cur)
				{
					s.push(cur);
					cur = cur->_left;
				}
				Node* top = s.top();
				s.pop();
				cout << top->_key << " ";
				cur = top->_right;
			}
		}
		cout << endl;
	}
private:
	Node* _root;
};
void TestBinaySearchNonR()
{
	SearchBinaryTree<int> bs;
	//int array[] = { 2,4,1,3,6,5 };
	int array[] = {5,7,8,2,9};
	for (size_t i = 0; i < 10; ++i)
	{
		bs.InsertNonR(array[i]);
	}
	bs.InorderNonR();
	bs.FindNonR(3);

	bs.RemoveNonR(0);
	bs.InorderNonR();
	bs.RemoveNonR(1);
	bs.RemoveNonR(2);
	bs.RemoveNonR(3);
	bs.RemoveNonR(4);
	bs.RemoveNonR(5);
	bs.RemoveNonR(6);
	bs.RemoveNonR(7);
	bs.RemoveNonR(8);
	bs.RemoveNonR(9);
	bs.InorderNonR();
}

void TestBinaySearchR()
{
	SearchBinaryTree<int> bs;
	int array[] = { 5,9 };
	for (size_t i = 0; i < 10; ++i)
	{
		bs.InsertR(array[i]);
	}
	bs.InOrderR();
	cout <<bs.FindNonR(3)<<endl;
	bs.RemoveR(0);
	bs.InorderNonR();
	bs.RemoveR(1);
	bs.RemoveR(2);
	bs.RemoveR(3);
	bs.InorderNonR();
	bs.RemoveR(4);
	bs.RemoveR(5);
	bs.RemoveR(6);
	cout << bs.FindNonR(3) << endl;
	bs.RemoveR(7);
	bs.RemoveR(8);
	bs.RemoveR(9);
	bs.InOrderR();
}

二叉搜索树的实现就到这里~~~