二叉搜索树

概念

二叉搜索树又称为二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：
若它的左子树不为空，则左子树上所有结点的值都小于根结点的值。
若它的右子树不为空，则右子树上所有结点的值都大于根结点的值。
它的左右子树也分别是二叉搜索树。

int a[]={5,3,4,1,7,8,2,6,0,9}

二叉搜索树的查找

定义一个树节点
节点中包括三个值：节点值，左指针，右指针
节点类当中只需实现一个构造函数即可，用于构造指定节点值的节点。

	struct BSTreeNode
	{
		K _key;          //节点值
		BSTreeNode<K>* _left;   //左指针 
		BSTreeNode<K>* _right;  //右指针

		//构造函数
		BSTreeNode(const K& key = 0)
			:_key(key)
			, _left(nullptr)
			, _right(nullptr)
		{}
	};
1
2
3
4
5
6
7
8
9
10
11
12
13

插入函数

分两种情况：
1.树是空树的时候，直接创建新的节点
2.当树不是空树的时候需要进行以下步骤：
首先先创建一个指针指向根节点，为了避免不知道在哪里插入，我们要定义一个父亲指针指向当前指针的上一位，先让其指向空。
当找到插入位置的时候，如果节点值大于父亲的节点值，放到右边，小于的话插到左边，等于的话则插入失败。
非递归

	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_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;
			}
			cur = new Node(key);
			if (parent->_key < key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}
			return true;
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

递归

	bool _InsertR(Node*& root, const K& key)
	{
		if (root == NULL)
		{
			root = new Node(key);
			return true;
		}
		if (root->_key < key)
		{
			return _InsertR(root->_right, key);
		}
		else(root->_key > key)
		{
			return _InsertR(root->_left, key);
		}
		else
		{
		    return false;
	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

查找函数

非递归
查找一个节点的数其实非常简单，最多查高度次，用二叉搜索树的性质直接可以查找出来。

	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				cur = cur->_right;

			}
			else if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}
		return NULL;
	}
	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

递归

	Node* _FindR(Node* root, const K& key)
	{
		if (root == nullptr)
		{
			return nullptr;
		}
		if (root->_key < key)
		{
			return _FindR(root->_right, key);
		}
		else if (root->_key > key)
		{
			return _FindR(root->_left, key);
		}
		else
		{
			return root;
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

删除函数

删除一个值等于Key的节点，分情况分析：
1.要删除的是6、9、0…，非常好处理，特征：叶子节点
方法：删除自己，父亲指向自己位置的指针置空
2.要删除的节点的8、1…也还行。特征只有一个孩子
方法：删除节点，把孩子交给父亲顶替自己的位置
3.要删除的是5、7…，不好处理。特征：有两个孩子
方法：替换法删除。去孩子里面找一个值能替换自己的节点，替换自己删除
替换的特征：左子树的最大节点（最右节点）或者右子树的最小节点（最左节点）
这两个节点替换后，都符合特征2，可以直接删除

再分析一下：特征1，可以当成特征2的情况去梳理
非递归：

	bool Erase(const K& key)
	{
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				//找到了，准备开始删除
				if (cur->_left == nullptr)
				{
					if (parent->_left == cur)
					{
						parent->_left = cur->_right;
					}
					else
					{
						parent->right = cur->_right;
					}
					delete cur;
				}
				else if (cur->_right == nullptr)
				{
					if (parent->_left == cur)
					{
						parent->_left = cur->_left;
					}
					else
					{
						parent->_right = cur->_left;
					}
				}
				else//左右都不为空，替换法删除
				{
					//找到右子树的最小节点去替换
					Node* minRight = cur->_right;
					Node* minParent = cur;
					while (minRight->_left)
					{
						minRight = minRight->_left;
					}
					//保存替换节点的值
					cur->_key = minRight->_key;
					//删除替换节点
					if (minParent->_left = minRight)
					{
						minParent > _left = minRight->right;
					}
					else
					{
						minParent->_right = minRight->_right;
			        }
					delete minRight;
				}
				return true;
			}
		}
		return false;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

递归：

	bool EraseR(Node*& root, const K& key)
	{
		if (root == NULL)
		{
			return;
		}
		if (root->_key < key)
		{
			return EraseR(root->_right, key);
		}
		else if (root->_key > key)
		{
			return EraseR(root->_left, key);
		}
		else
		{
			//找到了,root就是要删除的节点
			Node* minRight = root->_right;
			while (minRight->_left)
			{
				minRight = minRight->_left;
			}
			
			K min = minRight->_key;
			//转换成在root的右子树删除min
			_EraseR(root->_right, min);
			root->_key = min;
		}
		return true;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

构造函数

构造一个空树即可

BSTree()
		:_root(nullptr)
	{}
1
2
3

拷贝构造函数

这里我们用到深拷贝，拷贝一个与原来树相同的树

	Node* _Copy(Node* root)
	{
		if (root == nullptr)
		{
			return nullptr;
		}
		Node* copyNode = new Node(root->_key);
		copyNode->_left = _Copy(root->_left);
		copyNode->_right = _Copy(root->_right);
	}
	BSTree(const BSTree<K>& t)
	{
		_root = _Copy(t._root);
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

赋值运算符重载

这个写法的好处在于函数参数没有用引用，传入右值的时候会直接调用拷贝构造函数完成拷贝构造，创建一个新空间，我们只需将这个拷贝构造出来的对象与this对象进行交换，就相当于完成了赋值操作，而拷贝构造出来的对象会在该赋值运算符重载调用结束时自动析构。

	BSTree<K>& operator=(BSTree<K> t)
	{
		swap(_root, t._root);
		return* this;
	}
1
2
3
4
5

析构函数

直接对树进行析构即可

void _Destory(Node* root)
	{
		if (root == NULL)
		{
			return;
		}
		_Destory(root->_left);
		_destory(root->_right);
		delete root;
	}
	~BSTree()
	{
		_Destory(_root);
		_root = nullptr;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15