二叉搜索树 - c++实现

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

• a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
• b、最多查找高度次，走到到空，还没找到，这个值不存在。

• a. 树为空，则直接新增节点，赋值给root指针
• b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

• a. 要删除的结点无孩子结点
• b. 要删除的结点只有左孩子结点
• c. 要删除的结点只有右孩子结点
• d. 要删除的结点有左、右孩子结点

• 情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除
• 情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除
• 情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题--替换法删除

#pragma once

template<class K>
class BSTreeNode
{
public:
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;

	BSTreeNode(const K& key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}
};

template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	//代码实现

	//插入
	bool Insert(const K& key)
	{
		if (_root == nullptr) //进行判空
		{
			_root = new Node(key);
		}

		Node* cur = _root; //当前节点

		//cur是局部变量，出作用域后会销毁，造成内存泄露的问题，所以需要新增变量进行链接
		Node* parent = nullptr; 

		while (cur)
		{
			if (key > cur->_key)
			{
				parent = cur; //保留cur的指针
				cur = cur->_right;
			}
			else if(key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;   //如果相等 - 不插入 ，避免数据冗余
			}
		}

		cur = new Node(key);

		//链接 - 需要进行判断链接父节点的左右
		if (key > parent->_key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		return true;

	}

	//查找
	bool Find(const K& key)
	{
		if (_root == nullptr) //进行判空
			return false;

		Node* cur = _root; //避免直接修改/访问私有成员

		while (cur)
		{
			if (key > cur->_key)
			{
				cur = cur->_right;
			}
			else if (key < cur->_key)
			{
				cur = cur->_left;
			}
			else
			{
				return true;
			}
		}

		return false;
	}

	//注：叶子节点和叶节点是同一个概念，都指的是树中最底层的节点，即没有子节点的节点。

	//删除 - 分情况讨论
	//1.删除叶子节点 - 左右都为空（直接删除）
	
	//2.删除分支节点 - 左右子树有一方为空
		//a.左子树为空 - 右子树需要与父节点进行链接（直接删除）
		//b.右子树为空 - 左子树需要与父节点进行链接（直接删除）
		
	//3.删除分支节点 - 左右子树都不为空
		//a.取右子树的最小值 - 最左节点（伪删除）
		//b.取左子树的最大值 - 最右节点（伪删除）

	bool Erase(const K& key)
	{
		Node* cur = _root; 
		Node* parent = nullptr;

		//查找要删除的节点
		while (cur)
		{
			if (key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (key < cur->_key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				//1.右子树为空
				if (cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_right == cur)
						{
							parent->_right = cur->_left;
						}
						else
						{
							parent->_left = cur->_left;
						}
					}

					delete cur;
				}
				else if (cur->_left == nullptr) //2.左子树为空
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_right;
						}
						else
						{
							parent->_right = cur->_right;
						}
					}

					delete cur;
				}
				else
				{
					//左右子树都不为空 - 取右子树最小值/取左子树最大值
					Node* PminRight = cur; //删除节点的父节点

					Node* minRight = cur->_right; //删除的节点

					//右子树最小节点一定是最靠近左子树的节点
					while (minRight->_left)
					{
						PminRight = minRight;
						minRight = minRight->_left;
					}

					cur->_key = minRight->_key; //进行赋值

					//链接 - 需要判断
					if (PminRight->_right == minRight)
					{
						PminRight->_right = minRight->_right;
					}
					else
					{
						PminRight->_left = minRight->_right;
					}

					delete minRight;

				}

				return true;
			}
			
		}

		return false;

	}


	//打印 - 子函数
	void _Inorder(Node* root)
	{
		if (root == nullptr)
			return;

		_Inorder(root->_left);
		cout<< root->_key << " ";
		_Inorder(root->_right);
	}
	//打印
	void Inorder()
	{
		_Inorder(_root);
		cout << endl;
	}
	
private:
	Node* _root = nullptr;
};

解析：

①关于插入

②关于查找

③关于删除

3.删除的节点左/右子树都不为空（这里采用的是取右子树的最小值）：

//递归版本
	 
	//查找 - 子函数
	bool _Find_R(Node* root, const K& key)
	{
		if (root == nullptr)
			return false;

		if (key == root->_key)
			return true;

		if (key > root->_key)
		{
			return _Find_R(root->_right, key);
		}
		else
		{
			return _Find_R(root->_left, key);
		}
	}

	//查找
	bool Find_R(const K& key)
	{
		return _Find_R(_root, key);
	}


	//插入- 子函数
	bool _Insert_R(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}

		if (key > root->_key)
		{
			return _Insert_R(root->_right, key);
		}
		else if(key < root->_key)
		{
			return _Insert_R(root->_left, key);
		}
		else
		{
			return false;  //相等 - 避免数据冗余
		}

	}

	//插入
	bool Insert_R(const K& key)
	{
		return _Insert_R(_root, key);
	}

	//删除 - 子函数
	bool _Erase_R(Node*& root, const K& key)
	{
		if (root == nullptr)
			return false;

		if (key > root->_key)
		{
			return _Erase_R(root->_right, key);
		}
		else if (key < root->_key)
		{
			return _Erase_R(root->_left, key);
		}
		else 
		{
			//找到了-开始删除
			
			Node* del = root;

			//1.左子树为空
			if (root->_left == nullptr)
			{
				root = root->_right;
			}
			else if(root->_right == nullptr) //右子树为空
			{
				root = root->_left;
			}
			else
			{
				//左右子树都不为空 - a.取左子树最大值  b.取右子树最小值
		
				Node* maxLeft = root->_left;

				while (maxLeft->_right)
				{
					maxLeft = maxLeft->_right;
				}

				swap(maxLeft->_key, root->_key);

				return  _Erase_R(root->_left, key); //转换成子树去删除
				//注意：这里不能传 _Erase_R(maxLeft, key);
				//虽然这里是传引用，但是maxLeft是局部变量，引用代表着root是这个局部变量的别名
				//而局部变量出作用域后会销毁，所以这里传maxLeft会报错
			}

			delete del;

			return true;
		}
	}

	//删除
	bool Erase_R(const K& key)
	{
		return _Erase_R(_root, key);
	}



	//---------------------------------------------------------------------

	//打印 - 子函数
	void _Inorder(Node* root)
	{
		if (root == nullptr)
			return;

		_Inorder(root->_left);
		cout<< root->_key << " ";
		_Inorder(root->_right);
	}
	//打印
	void Inorder()
	{
		_Inorder(_root);
		cout << endl;
	}

解析：

①关于插入

②.关于删除

1.左/右为空：

2.左右子树都不为空（这里采用的是取左子树的最大值）：

    ~BSTree()
	{
		Destory(_root);
		_root = nullptr;
	}

	void Destory(Node* root)
	{
		if (root == nullptr)
			return;
        
        //后续析构
		Destory(root->_left);
		Destory(root->_right);
		delete root;
	}

	//拷贝构造也属于构造，c++规定 构造函数
	//a.我们不写，编译器默认生成（浅拷贝）
	//b.我们写了，编译器不会生成
	/*BSTree()
		:_root(nullptr)
	{}*/

	BSTree() = default; //指定强制生成默认构造

	BSTree(const BSTree<K>& t)
	{
		_root = Copy(t._root);
	}

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

	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;

		//前序创建 - 后续链接
		Node* newNode = new Node(root->_key);

		newNode->_left = Copy(root->_left);
		newNode->_right = Copy(root->_right);

		return newNode;
	}

#include <iostream>

using namespace std;

#include "BinarySearchTree.h"

void TestBSTree1()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };

	BSTree<int> t;

	for (auto e : a)
	{
		t.Insert(e);
	}

	t.Inorder();
	
	t.Erase(10);
	t.Inorder();

	t.Erase(8);
	t.Inorder();

	t.Erase(13);
	t.Inorder();	

	t.Erase(14);
	t.Inorder();
}

void TestBSTree2()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };

	BSTree<int> t;

	for (auto e : a)
	{
		t.Insert(e);
	}
	t.Inorder();

	t.Erase_R(10);
	t.Inorder();

	t.Erase_R(13);
	t.Inorder();

	t.Erase_R(14);
	t.Inorder();

	t.Erase_R(8);
	t.Inorder();
}

void TestBSTree3()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };

	BSTree<int> t;

	for (auto e : a)
	{
		t.Insert(e);
	}
	t.Inorder();

	BSTree<int> tt(t);
	tt.Inorder();

	BSTree<int> ttt = tt;
	ttt.Inorder();
}


int main()
{
	//TestBSTree1();

	//TestBSTree2();

	TestBSTree3();

	return 0;
}