二叉树进阶之二叉搜索树：一切的根源

标签：Node 进阶 cur nullptr 之二 right 二叉树 root left

前言：

在学完了简单的容器与C++面向对象的三大特性之后，我们首先接触的就是map与set两大容器，但是这两个容器底层实现的原理是什么呢？我们不而知，今天，主要来为学习map与set的底层原理而打好基础，而二叉搜索树，则是一切的开端......

一、二叉搜索树的定义与性质

1.1、什么是二叉搜索树：

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

1.2、二叉搜索树的性质：

节点值关系: 对于每个节点 N，其左子树中所有节点的值都小于 N，右子树中所有节点的值都大于 N。
中序遍历的顺序: 对二叉搜索树进行中序遍历（左-根-右）时，节点的值按升序排列。
平均时间复杂度: 在平均情况下，查找、插入和删除操作的时间复杂度都是 O(log n)。
最坏时间复杂度: 在最坏情况下（树退化为链表），查找、插入和删除操作的时间复杂度是 O(n)。

二、二叉搜索树的模拟实现

初步了解性质之后，我们就根据这些特点与所学二叉树的知识模拟实现一个简单的二叉搜索树结构。首先我们创建一个头文件，取名为BSTree.h

1、节点结构

结点是组成一个二叉树的基础，我们要写一个二叉树，首先就是定义好一个的节点结构，由于是二叉树，所以一个结点会有两个子节点，我们分别以right与left表示左右子节点。随后就是值了，我们用val来表示（注意：一般来说会有key与key-val两种模型，分别象征之后的set与map两种容器，我们这里先以简单的key模型为例子）。

template<class T>
struct BSTNode
{
	BSTNode(const T&data=T())
		:_val(data)
		,left(nullptr)
		,right(nullptr)
	{}
	BSTNode<T>* right;
	BSTNode<T>* left;
	T _val;
};

再这样一串代码中，我们先定义一个结点结构，用之前学的模板知识将结点改造为一个模板。对与结点的默认构造，我们选择调用所存储数据类型的默认结构在初始化列表中给val值进行初始化，并且，给左右子节点的指针全部指向空。（data值直接调用的T这个数据类型自己的默认构造：包括内置类型与自定义类型）

2、二叉树的创建

随后，我们就在继续创建一个BSTree结构体模板，为了方便，先将结点进行重命名，随后将必要的构造函数，参数写上。一个BSTree参数只需要一个根节点就行。构造函数也只需要对根节点指针指向空就行。

template<class T>
class BSTree
{
	typedef BSTNode<T> Node;
public:
	BSTree()
		:_root(nullptr)
	{}
	
private:
	Node* _root;
};

3、二叉树的查找

在实现插入这个接口之前得先实现查找，因为要插入一个节点，我们就需要先找到相应的位置。

倘若找不到这个节点，就返回nullptr,找到了，就返回指向这个结点的指针。

Node* Find(const T& data)
{
	Node* cur = _root;
	while (cur)
	{
		if (cur->_val == data)
		{
			return cur;
		}
		else if (cur->_val > data)
		{
			cur = cur->right;
		}
		else
		{
			cur = cur->left;
		}
	}
	return nullptr;
}

4、二叉树的插入

接下来就是实现插入这个重要接口，由于二叉搜索树的独特性质，不能插入相同的元素，为了知道是否插入成功，我们需要给这个接口的返回值返回一个bool类型

bool Insert(const T& data)
{
	if (_root == nullptr)//如果是一个空树，就创建一个结点随后返回真，并把_root指向新创建的结点
	{
		_root = new Node(data);
		return true;
	}
	Node* cur == _root;
	Node* parent = nullptr;//记录cur的父节点
	while (cur)
	{
		parent = cur;
		if (cur->_val > data)
		{
			cur = cur->left;
		}
		else if (cur->_val < data)
		{
			cur = cur->right;
		}
		else
		{
			return false;
		}
	}
	cur = new Node(data);
	if (cur->_val > parent->_val)
	{
		parent->right = cur;
	}
	else
	{
		parent->left = cur;
	}
	return true;
}

5、二叉树的删除

在二叉搜索树中，删除节点的操作是最复杂的。删除操作需要保持二叉搜索树的性质，即在删除一个节点后，仍然能够保持左子树的所有节点值小于当前节点值，右子树的所有节点值大于当前节点值。如果我们想要删除的节点为叶子，那还比较轻松，但如果我们想要删除的节点仍然拥有子节点，那就麻烦许多了。

日常我们有两种思路解决，二者大同小异，一个是寻找左子树的最最右节点，一个是找右子树的最左节点，这里我就以右子树的最左节点为例。

bool Erase(const T& data)
{
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)//查找是否有这个节点
	{
		if (cur->_val > data)
		{
			parent = cur;
			cur = cur->left;
		}
		else if (cur->_val < data)
		{
			parent = cur;
			cur = cur->right;
		}
		else
		{
			break;
		}
	}

	if (cur == nullptr)//没有这个节点直接返回
	{
		return false;
	}

	if (cur->left == nullptr)//左为空或者右为空，或者都为空的情况下
	{
		if (cur == _root)
		{
			_root = _root->right;
		}
		if (cur == parent->left)
		{
			parent->left = cur->right;
		}
		else  
		{
			parent->right = cur->right;
		}
		delete cur;
		cur = nullptr;
		return true;
	}

	if (cur->right == nullptr)
	{
		if (cur == _root)
		{
			_root = _root->left;
		}
	
		if (cur == parent->left)
		{
			parent->left = cur->left;
		}
		else
		{
			parent->right = cur->left;
		}
		delete cur;
		cur = nullptr;
		return true;
	}

	Node* pparent = cur;//两个子节点都在的情况下，需要找到右子树的最小节点，将两个的值进行交换，再删除右子树的最小节点，此时又是一个0/1子树的选择情况
	Node* pcur = cur->right;
	while (pcur->left)
	{
		pparent = pcur;
		pcur = pcur->left;
	}
	cur->_val = pcur->_val;

	Node* p = pcur->right;
	if (pparent->left == pcur)
	{
		pparent->left = p;
	}
	else
	{
		pparent->right = p;
	}
	delete pcur;
	pcur = nullptr;
	return true;
	
}

大概的思路就是先找到要删除的节点，随后判断这个节点有几个非空子节点，0和1个空节点是一样的处理方法，二两个非空节点就需要用右子树的最小值或者左子树的最大值来替换，随后删除替换了值的那个节点。

6、二叉树的遍历

由于在外部，我们拿不到根节点，那么我们要怎么遍历一遍呢？这里就需要用到我们的套层艺术了！

首先我们先在private中写一个中序遍历的接口：

void order(Node*root)
{
	if (root == nullptr)
	{
		return;
	}
	order(root->left);
	cout << root->_val << " ";
	order(root->right);
}

随后，我们在publci中写一个无参的_oeder函数来调用order就行了。

void _order()
{
	order(_root);
	cout<< endl;
}

我们写一个简单的用例测试一下

#include<iostream>
using namespace std;
#include"BSTree.h"

int main()
{
	
	BSTree<int>Tree;
	Tree.Insert(6);
	Tree.Insert(3);
	Tree.Insert(2);
	Tree.Insert(1);
	Tree.Insert(4);
	Tree.Insert(7);
	Tree.Insert(9);
	Tree.Insert(8);
	Tree.Insert(5);
	Tree.Insert(10);
	Tree._order();



	for (int i = 1; i <= 10; ++i)
	{
		Tree.Erase(i);
		Tree._order();

	}
	Tree._order();

	return 0;
}

输出结果没有问题：

7、二叉树的析构销毁

在上面的代码中，存在一个内存泄漏的问题，就是我们所有的节点都是自己new出来的，所以也需要我们自己手动去销毁，自动构建出来的析构函数自然就不行，所以必须要自己写析构函数。所以我们可以实现一个destroy函数，后序递归销毁二叉树，随后让析构函数调用destroy函数就行。

void Destroy(Node* root)
{
    if (root)
    {
        Destroy(root->left);
        Destroy(root->right);
        delete root;
    }
}


	~BSTree()
	{
		destroy(_root);
	}

8、由key模型向key-val模型的转化

接下来我们去实现一下两种模型之间的转化：

其实，二者并无太大区别，在插入销毁查找中判断仍然使用key值判断只不过是把以往的单独的T改成了T,K，把之前的_val改成_key。

只不过我们需要实现一个额外的构造函数，这个构造函数需要进行深拷贝来实现，也就是说我们要进行递归对这个二叉树进行深拷贝。

	BSTree(const BSTree<T,K>&t)
	{
		_root=Copy(t._root);
	}
	Node* Copy(Node* root)
	{
		if (root == nullptr)
		{
			return nullptr;
		}

		Node* newRoot = new Node(root->_key, root->_val);
		newRoot->_left = Copy(root->_left);
		newRoot->_right = Copy(root->_right);

		return newRoot;
	}

key模型整体的代码如下：

#pragma once

template<class T>
struct BSTNode
{
	BSTNode(const T&data=T())
		:_val(data)
		,left(nullptr)
		,right(nullptr)
	{}
	BSTNode<T>* right;
	BSTNode<T>* left;
	T _val;
};

template<class T>
class BSTree
{
	typedef BSTNode<T> Node;
public:
	BSTree()
		:_root(nullptr)
	{}

	~BSTree()
	{
		destroy(_root);
	}
	Node* Find(const T& data)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_val == data)
			{
				return cur;
			}
			else if (cur->_val > data)
			{
				cur = cur->left;
			}
			else
			{
				cur = cur->right;
			}
		}
		return nullptr;
	}

	bool Insert(const T& data)
	{
		if (_root == nullptr)//如果是一个空树，就创建一个结点随后返回真，并把_root指向新创建的结点
		{
			_root = new Node(data);
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;//记录cur的父节点
		while (cur)
		{
			parent = cur;
			if (cur->_val > data)
			{
				cur = cur->left;
			}
			else if (cur->_val < data)
			{
				cur = cur->right;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(data);
		if (cur->_val > parent->_val)
		{
			parent->right = cur;
		}
		else
		{
			parent->left = cur;
		}
		return true;
	}

	bool Erase(const T& data)
	{
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)//查找是否有这个节点
		{
			if (cur->_val > data)
			{
				parent = cur;
				cur = cur->left;
			}
			else if (cur->_val < data)
			{
				parent = cur;
				cur = cur->right;
			}
			else
			{
				break;
			}
		}

		if (cur == nullptr)//没有这个节点直接返回
		{
			return false;
		}

		if (cur->left == nullptr)//左为空或者右为空，或者都为空的情况下
		{
			if (cur == _root)
			{
				_root = _root->right;
			}
			else if (cur == parent->left)
			{
				parent->left = cur->right;
			}
			else  
			{
				parent->right = cur->right;
			}
			delete cur;
			cur = nullptr;
			return true;
		}

		if (cur->right == nullptr)
		{
			if (cur == _root)
			{
				_root = _root->left;
			}
			else if (cur == parent->left)
			{
				parent->left = cur->left;
			}
			else
			{
				parent->right = cur->left;
			}
			delete cur;
			cur = nullptr;
			return true;
		}

		Node* pparent = cur;//两个子节点都在的情况下，需要找到右子树的最小节点，将两个的值进行交换，再删除右子树的最小节点，此时又是一个0/1子树的选择情况
		Node* pcur = cur->right;
		while (pcur->left)
		{
			pparent = pcur;
			pcur = pcur->left;
		}
		cur->_val = pcur->_val;

		Node* p = pcur->right;
		if (pparent->left == pcur)
		{
			pparent->left = p;
		}
		else
		{
			pparent->right = p;
		}
		delete pcur;
		pcur = nullptr;
		return true;
		
	}

	void _order()
	{
		order(_root);
		cout<< endl;
	}
private:
	void order(Node*root)
	{
		if (root == nullptr)
		{
			return;
		}
		order(root->left);
		cout << root->_val << " ";
		order(root->right);
	}

	void Destroy(Node* root)
	{
		if (root)
		{
			Destroy(root->left);
			Destroy(root->right);
			delete root;
		}
	}

	Node* _root;
};

key-val的模型代码如下:


template<class T, class K>
struct BSTNode
{
	BSTNode(const T& key = T(), const K& val=K())
		:_key(key)
		,_val(val)
		, left(nullptr)
		, right(nullptr)
	{}
	BSTNode<T,K>* right;
	BSTNode<T,K>* left;
	T _key;
	K _val;
};

template<class T,class K>
class BSTree
{
	typedef BSTNode<T,K> Node;
public:
	BSTree() = default;
	BSTree(const BSTree<T,K>&t)
	{
		_root=Copy(t._root);
	}
	Node* Copy(Node* root)
	{
		if (root == nullptr)
		{
			return nullptr;
		}

		Node* newRoot = new Node(root->_key, root->_val);
		newRoot->_left = Copy(root->_left);
		newRoot->_right = Copy(root->_right);

		return newRoot;
	}

	~BSTree()
	{
		Destroy(_root);
	}
	Node* Find(const T& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key == key)
			{
				return cur;
			}
			else if (cur->_key > key)
			{
				cur = cur->left;
			}
			else
			{
				cur = cur->right;
			}
		}
		return nullptr;
	}

	bool Insert(const T& key,const K&val)
	{
		if (_root == nullptr)//如果是一个空树，就创建一个结点随后返回真，并把_root指向新创建的结点
		{
			_root = new Node(key, val);
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;//记录cur的父节点
		while (cur)
		{
			parent = cur;
			if (cur->_key > key)
			{
				cur = cur->left;
			}
			else if (cur->_key < key)
			{
				cur = cur->right;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(key,val);
		if (cur->_key > parent->_key)
		{
			parent->right = cur;
		}
		else
		{
			parent->left = cur;
		}
		return true;
	}

	bool Erase(const T& key)
	{
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)//查找是否有这个节点
		{
			if (cur->_key > key)
			{
				parent = cur;
				cur = cur->left;
			}
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->right;
			}
			else
			{
				break;
			}
		}

		if (cur == nullptr)//没有这个节点直接返回
		{
			return false;
		}

		if (cur->left == nullptr)//左为空或者右为空，或者都为空的情况下
		{
			if (cur == _root)
			{
				_root = _root->right;
			}
			else if (cur == parent->left)
			{
				parent->left = cur->right;
			}
			else
			{
				parent->right = cur->right;
			}
			delete cur;
			cur = nullptr;
			return true;
		}

		if (cur->right == nullptr)
		{
			if (cur == _root)
			{
				_root = _root->left;
			}
			else if (cur == parent->left)
			{
				parent->left = cur->left;
			}
			else
			{
				parent->right = cur->left;
			}
			delete cur;
			cur = nullptr;
			return true;
		}

		Node* pparent = cur;//两个子节点都在的情况下，需要找到右子树的最小节点，将两个的值进行交换，再删除右子树的最小节点，此时又是一个0/1子树的选择情况
		Node* pcur = cur->right;
		while (pcur->left)
		{
			pparent = pcur;
			pcur = pcur->left;
		}
		cur->_key = pcur->_key;

		Node* p = pcur->right;
		if (pparent->left == pcur)
		{
			pparent->left = p;
		}
		else
		{
			pparent->right = p;
		}
		delete pcur;
		pcur = nullptr;
		return true;

	}

	void _order()
	{
		order(_root);
		cout << endl;
	}
private:
	void order(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		order(root->left);
		cout << root->_key << " " << root->_val << " ";
		order(root->right);
	}

	void Destroy(Node* root)
	{
		if (root)
		{
			Destroy(root->left);
			Destroy(root->right);
			delete root;
		}
	}

	Node* _root;
};

c测试用例如下：

#include<iostream>
using namespace std;
#include"BSTree.h"


void TestBSTree()
{
	// 统计水果出现的次数
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
   "苹果", "香蕉", "苹果", "香蕉" };
	BSTree<string, int> countTree;
	for (const auto& str : arr)
	{
		// 先查找水果在不在搜索树中
		// 1、不在，说明水果第一次出现，则插入<水果, 1>
		// 2、在，则查找到的节点中水果对应的次数++
		//BSTreeNode<string, int>* ret = countTree.Find(str);
		auto ret = countTree.Find(str);
		if (ret == NULL)
		{
			countTree.Insert(str, 1);
		}
		else
		{
			ret->_val++;
		}
	}
	countTree._order();
}

int main()
{
	
	BSTree<int,string>Tree;
	Tree.Insert(6, "six");
	Tree.Insert(3,"three");
	Tree.Insert(2,"two");
	Tree.Insert(1,"one");
	Tree.Insert(4,"four");
	Tree.Insert(7,"seven");
	Tree.Insert(9,"nine");
	Tree.Insert(8,"eight");
	Tree.Insert(5,"five");
	Tree.Insert(10,"ten");
	Tree._order();



	for (int i = 1; i <= 10; ++i)
	{
		Tree.Erase(i);
		Tree._order();

	}
	Tree._order();

	cout << endl;

	TestBSTree(); 

	return 0;
}

三.、小结

二叉搜索树是一种重要的数据结构，具有良好的查找、插入和删除性能。但它也存在潜在的不平衡问题，因此在实际应用中，常常需要通过自平衡的二叉搜索树（如AVL树、红黑树）来保证性能。

希望本文对基础的二叉搜索树的探索能对您产生帮助！

标签：Node,进阶,cur,nullptr,之二,right,二叉树,root,left
From： https://blog.csdn.net/htw250056/article/details/141281293