目录

性质

实现

结点和树的构造

插入

中序遍历

二叉搜索树的查找

递归查找

删除

1.缺少孩子时

2.满孩子时：

拷贝构造

析构函数--销毁树

 赋值

插入的递归写法

删除的递归写法

---

性质

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

它的左右子树也分别为二叉搜索树

实现

结点和树的构造

使用模板参数来替换内置类型，结点有左右子树；

初始化列表初始化结点；

构造树时直接头结点置空；

template <class k>
struct BSTreeNode
{
	BSTreeNode* _left;
	BSTreeNode* _right;
 
	k _key;
	BSTreeNode(const k& key)
		:_left(nullptr)
		, _right(nullptr)
		, _key(key)
	{}
};
 
template <class k>
class BSTree
{
	typedef BSTreeNode Node;
public:
private:
	Node* _root=nullptr;
};

插入

插入一个值，必须要确保比结点小的，存在左树；比结点大的，存在右树。

插入结点时，要连接新结点和其父亲结点，那么要注意保留父亲结点

cur：来找结点将要插入的位置

parent：保留父亲结点，方便连接

bool Insert(const k& key)
	{
		//空树时
		if (_root==nullptr)
		{
			_root = new Node(key);
			return true;
		}
 
		//刚开始父亲就等于根节点
		//cur--确定插入结点位置
		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
			{
				//相等不能插入
				returnf false;
			}
		}
		//找到位置后，创建结点，进行连接
		cur = new Node(key);
		if (key > parent->_key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		return true;
	}

中序遍历

遍历我们使用递归调用

推荐将调用函数封装一层，这样在类外调用时，省去了传参那一步骤，若不封装，直接是public，调用遍历时涉及到传根结点的地址，地址为成员私有，不方便获取。

public:
	//中序遍历
	void InOrder()
	{
		_InOrder(_root);
	}
 
private:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}
	Node* _root=nullptr;
};

二叉搜索树的查找

平衡搜索二叉树中查找一个数的时间复杂度为 O(N)，从它最坏情况->退化成单链表，就可以体现出来。

查找一个值：确定一个指针来找，比较指针位置结点与要查找值；

小值走左树，大值走右树，相等返回真，找不到返回假。

 
	//查找
	void Find(const k& key)
	{
		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;
	}

递归查找

只要是递归，就要在外封装一层，因为涉及到传地址，地址私有，封装一层不需要我们手动去传地址，更加方便。

public:
	//查找递归
	bool FindR(const k& key)
	{
		return _FindR(_root, key);
	}
 
 
private:
	//查找递归
	bool _FindR(Node* root, const k& key)
	{
		if (root == nullptr)
			return false;
		if (key > root->_key)
		{
			return _FindR(root->_right, key);
		}
		else if (key < root->_key)
		{
			return _FindR(root->_left, key);
		}
		else
		{
			return true;
		}
	}

删除

删除有以下三种情况：

1.缺少孩子时

a.删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点
b.删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点

2.满孩子时：

c.在它的右子树中寻找最小的结点，用它的值填补到被删除节点中，再来处理该结点的删除问题

//删除
	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==parent->_left)
					{
						parent->_left = cur->_right;
					}
					else
					{
						parent->_right = cur->_right;
					}
 
					delete cur;
				}
				else if (cur->_right == nullptr)
				{
					if (cur == parent->_left)
					{
						parent->_left = cur->_left;
					}
					else
					{
						parent->_right = cur->_left;
					}
 
					delete cur;
				}
				else  //两孩子都不为空
				{
					//找右树最小结点（左树最大结点）
					//还要找到其父亲，替换后删minright，其右子树可能不为空，要连接父亲结点
					Node* minParent = cur;
					Node* minRight = cur->_right;
					while (minRight->_left)
					{
						minParent = minRight;
						minRight = minRight->_left;
					}
					//值代替删除节点的值
					//cur->_key = minRight->_key;
					swap(minRight->_key, cur->_key);
					//连接父亲结点和删除节点的右孩子
					if (minParent->_left==minRight)
					{
						minParent->_left = minRight->_right;
					}
					else
					{
						minParent->_right = minRight->_right;
					}
 
					delete minRight;
				}
 
				return true;
			}
		}
		//没找到
		return false;
	}

拷贝构造

注意，结点属于内置类型，若没有写拷贝构造的话，赋值时，默认是浅拷贝，若显示写了析构函数，会出现野指针的问题，同一个位置被析构两次。

这里递归构造树：

private:
	//复制结点构造树
	Node* CopyTree(Node* root)
	{
		if (root==nullptr)
		{
			return nullptr;
		}
		Node* copyNode = new Node(root->_key);
		copyNode->_left = CopyTree(root->_left);
		copyNode->_right = CopyTree(root->_right);
 
		return copyNode;
	}
public:
 
    BSTree()
    {}
 
	//拷贝构造
	BSTree(const BSTree& t)		//写了拷贝构造，就不会默认生成构造函数,手动创建
	{
		_root = CopyTree(t._root);
	}

析构函数--销毁树

private:
	//销毁树
	void DestoryTree(Node* root)
	{
		if (root==nullptr)
		{
			return;
		}
		DestoryTree(root->_left);
		DestoryTree(root->_right);
		delete root;
	}
 
public:
 
	//析构
	~BSTree()
	{
		DestoryTree(_root);
		_root = nullptr;
	}

 赋值

自定义类型的赋值，默认也是调用构造拷贝的，这里我们用现代写法：

参数传参是拷贝构造，生成临时变量，交换后返回即可：

	//赋值，现代写法
	BSTree& operator=(BSTree t)
	{
		swap(_root, t._root);
		return *this;
	}

插入的递归写法

非递归插入--之前是保留父节点，cur找到位置后，创建结点与父结点连接
递归插入--这里直接用根节点的引用依次递归就能解决问题

public:
	//递归插入
	bool InsertR(const k& key)
	{
		return _InsertR(_root, key);
	}
 
 
private:
	
	bool _InsertR(Node*& root, const k& key)
	{
		//等于空的时候插入
		if (root==nullptr)
		{
			root = new Node(key);
			return true;
		}
		if (key > root->_key)
			return _InsertR(root->_right, key);
		else if (key < root->_key)
			return _InsertR(root->_left, key);
		else
			return false;
	}

删除的递归写法

这里和插入一样，都是传指针的引用；

先查找，找到的话判断左右孩子是否为空，有空则将另一边给root

root是上一结点左树或右树的引用，直接获得连接关系

如果两边都不为空，则用替换法，找到要删除结点的右子树的最小值

最小结点值与被删结点互换，保留的搜索二叉树的结构

转换为要删除最小节点(最小节点的左肯定为空) 

递归去删除：从原先要删结点的右子树开始，查找删除最小节点

public:
	//递归删除
	bool EraseR(const k& key)
	{
		return _EraseR(_root,key);
	}
 
private:
 
	//递归删除
	bool _EraseR(Node*& root, const k& key)
	{
		//等于空则找不到
		if (root == nullptr)
		{
			return false;
		}
		if (key > root->_key)
			return _EraseR(root->_right, key);
		else if (key < root->_key)
			return _EraseR(root->_left, key);
		else   //相等--开始删除
		{
			//保存要删除的代码，方便删除
			Node* del = root;
			if (root->_left==nullptr)
			{
				root = root->_right;
			}
			else if (root->_right == nullptr)
			{
				root = root->_left;
			}
			else
			{
				Node* minRight = root->_right;
				while (minRight->_left)
				{
					minRight = minRight->_left;
				}
 
				swap(root->_key, minRight->_key);
 
				//递归删除，已经互换了值，在子树中删除，左一定为空
				return _EraseR(root->_right, key);
			}
			delete del;
			return true;
		}
	}