【C++】模拟实现二叉搜索(排序)树

修修修也

发布于 2024-09-24 17:22:42

740

发布于 2024-09-24 17:22:42

文章被收录于专栏：修也的进阶日记

一.了解项目功能

在本次项目中我们的目标是实现一个二叉搜索树(Binary Search Tree)类模板,还不了解二叉搜索树概念的朋友可以先移步[【数据结构】什么是二叉搜索(排序)树?] 其结构图示如下:

二叉搜索树结点(BSTreeNode)需要包含三个要素:键值_key,左指针域_left,右指针域_right.结点(BSTreeNode)逻辑结构图示如下:

二叉搜索树需要实现的功能有:

构造函数
中序遍历InOrder()函数
查找函数Find()--循环版 + FindR()--递归版
插入函数Insert()--循环版 + InsertR()--递归版
删除函数Erase()--循环版 + EraseR()--递归版
析构函数
拷贝构造函数
赋值运算符重载operator=函数

二.逐步实现项目功能模块及其逻辑详解

通过第二部分对项目功能的介绍，我们已经对的功能有了大致的了解，虽然看似需要实现的功能很多，貌似一时间不知该如何下手，但我们可以分步分模块来分析这个项目的流程，最后再将各部分进行整合，所以大家不用担心，跟着我一步一步分析吧！

！！！注意，该部分的代码只是为了详细介绍某一部分的项目实现逻辑，故可能会删减一些与该部分不相关的代码以便大家理解，需要查看或拷贝完整详细代码的朋友可以移步本文第四部分。

📌实现BSTreeNode类模板

🎏构造BSTreeNode类成员变量

我们在一开始需求分析时就已经明确了BSTreeNode类的成员变量组成包含三个要素:键值_key,左指针域_left,右指针域_right.结点(BSTreeNode),其逻辑结构图示如下:

这里还有一个小的点需要提一下,我们在这里实现的BSTreeNode类,后续是要给BSTree类使用的,考虑到后续我们在二叉搜索树的操作函数中会有直接操作结点成员变量的情况,如:

root = root->_right; //相当于在BSTreeNode外部直接通过类指针访问了类成员变量_right

基于class的封装特性,class的成员变量一般都是默认为私有的,如果我们要允许其他类直接访问class的成员变量和函数,就要将其都设置为public,或者通过友元/内部类来解决成员访问问题.

既然如此,我们不妨直接使用struct定义结点成员变量和函数,因为struct定义的类的成员变量和函数默认就是公有的,完全可以满足我们的需求.

综上所属,该部分代码如下:

template<class K>
struct BSTreeNode
{
	BSTreeNode<K>* _left;
	BSTreeNode<K>* _right;
	K _key;
};

🎏实现BSTreeNode类构造函数

BSTreeNode的构造函数我们实现两个即可,一个是有参构造,一个是无参构造,而无参构造又可以通过给缺省值的方式和有参构造合二为一,所以我们用初始化列表来实现一下BSTreeNode的构造函数:

//缺省值的作用是在无参调用时直接去调用模板实例化的类的无参构造函数
//这里一定不能将缺省值给0/nullptr!因为你不知道模板实例化的类具体到底是内置类型还是自定义类型(如Date)
//所以要显示调用K类型它自己的无参构造函数
BSTreeNode(const K& key = K())
	:_left(nullptr)
	,_right(nullptr)
	,_key(key)
{}

📌实现BSTree类模板

🎏构造BSTree类成员变量

BSTree类成员变量比较简单,就是一个根节点的指针,为了简化模板中出现的BSTreeNode<K>类型的名字,我们将其简化命名为:Node

该部分实现代码如下:

template<class K>
class BSTree
{
	typedef BSTreeNode<K> Node;  //简化命名
public:
    //成员函数

private:
    //成员变量or成员函数子函数
    Node* _root;
};

🎏实现BSTree类构造函数

BSTree类的构造函数非常简单,因为只有一个成员变量根节点指针_root,所以我们用初始化列表将该指针初始话为nullptr即可,代码如下:

BSTree()
	:_root(nullptr)
{}

🎏实现BSTree类InOrder()函数

BSTree类的中序遍历逻辑和二叉树的中序遍历逻辑一模一样,即

先递归访问左子树
再访问根节点
最后递归访问右子树

但在面向对象设计中,我们设计类内的递归函数会遇到一个问题,就是类对象调用其成员函数的递归传参问题: 我们知道C语言完成中序遍历函数时一个参数是恰好可以满足首次调用和递归调用时传参的形式的:

但是在面向对象语言中,这个参数是不好处理的,因为首次调用时不需要传参,类对象调用成员函数会默认传this指针,所以不需要传参数,但后续递归调用又需要传参数,这就导致这个函数参数有也不对,没有也不对:

所以好的解决方式是将递归主体封装成子函数,代替成员函数进行递归操作,这种方式我们在后续完成递归成员函数时会一直用到,大家一定要习惯。

综上所述,该部分实现代码如下:

//中序遍历函数
void InOrder()
{
	_InOrder(_root);  //代替成员函数完成递归
    cout<<endl;       //方便后续观察测试用例
}

//中序遍历子递归函数
void _InOrder(Node* root)
{
	if (root == nullptr)
	{
		return;
    }

	_InOrder(root->_left);       //递归访问左子树
	cout << root->_key << " ";   //访问根节点
	_InOrder(root->_right);      //递归访问右子树
}

🎏实现BSTree类Find()函数

BSTree类的查找函数实现思路如下:

从根节点开始比较查找, 如果查找值比根结点值大,则往右子树继续查找; 如果查找值比根结点值小,则往左子树继续查找;
最多查找高度次, 即查找到叶子节点, 如果还没找到, 则该值不存在于此树中。

思路图示如下:

🕹️循环版Find()函数

循环版Find()函数主要就是借助cur指针变量在二叉搜索树中一直查找,直到找到key值或者找到nullptr值为止,前者代表找到了,后者表示没有找到.

综上,实现代码如下:

//循环版Find
bool 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 true;
		}
	}
	return false;
}

🕹️递归版FindR()函数

递归版FindR()函数思路主要是根据key值递归去根的左或右子树继续查找,如果找到nullptr值,代表没有找到,就递归回false,如果找到了key值,就递归回true.

综上,实现代码如下:

//递归FindR成员函数
bool FindR(const K& key)
{
	return _FindR(_root, key);
}

//FindR()函数子递归
bool _FindR(Node* root, const K& key)
{
	if (root == nullptr)
	{
		return false;
	}

	if (root->_key < key)
	{
		_FindR(root->_right, key);   //根小于key,递归查找右子树
	}
	else if (root->_key > key)
	{
		_FindR(root->_left, key);    //根大于key,递归查找左子树
	}
	else
	{
		return true;          //根等于key,表示找到了
	}
}

🎏实现BSTree类Insert()函数

BSTree类的插入函数实现思路如下:

树为空,则直接新增节点,赋值给根节点指针
树不为空,则按二叉搜索树性质查找插入位置, 在查找到为空的位置插入新增值, 如果查找到该值已存在, 则返回查找失败(二叉搜索树不允许插入重复值)

思路图示如下:

🕹️循环版Insert()函数

循环版Insert()函数思路就是创建cur找插入位置,然后parent记录cur的父亲结点,方便找到后的插入工作,逻辑不是很难,细节要注意,实现代码及注释如下:

bool Insert(const K& key)
{ 
    //根节点为空直接令_root等于新插结点
	if (_root == nullptr)
	{
		_root = new Node(key);
		return true;
	}
    
    //开始在子树里面找插入位置cur,同时创建parent记录cur的父节点
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_key < key)    //查找位置key值比新插key值小,向右继续找插入位置
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_key > key)   //查找位置key值比新插key值大,向左继续找插入位置
		{
			parent = cur;
			cur = cur->_left;
		}
		else            //查找位置key值和新插key值相等,表明新插key值已经存在于树中了
		{
			return false;    //就不用再插入,直接返回插入失败
		}
	}
    
    //运行到此表示找到插入位置了,下面创建新结点,然后将其链接父节点即可
	cur = new Node(key);

	if (parent->_key < key)    //判断新结点和父节点的大小,大于就链接父节点的右指针
	{
		parent->_right = cur;
	}
	else         //小于就链接父节点的左指针
	{
		parent->_left = cur;
	}
	return true;
}

🕹️递归版InsertR()函数

递归InsertR()函数的逻辑是,如果新插key值大于根节点key值,就递归右子树继续插入,如果新插key值小于根节点key值,就递归左子树继续插入,如果相等就返回插入失败.

逻辑很简单,代码如下:

bool InsertR(const K& key)
{
	return _InsertR(_root, key);
}

bool _InsertR(Node*& root,const K& key)
{
	if (root == nullptr)    //找到nullptr表示找到插入位置了,直接插入即可
	{
		root = new Node(key);//因为子递归的参数是引用,所以可以直接将找到的空位置改为新结点
		return true;
	}

	if (root->_key < key)        //找到的位置key值比新插key值小,往右继续找位置
	{
		_InsertR(root->_right, key);
	}
	else if (root->_key > key)    //找到的位置key值比新插key值大,往左继续找位置
	{
		_InsertR(root->_left, key);
	}
	else        //找到的位置key值和新插入key值相等,返回插入失败
	{
		return false;
	}
}

🎏实现BSTree类Erase()函数

BSTree类的删除函数实现思路如下: 查找元素是否在二叉搜索中,如果不存在,则返回,如果存在,则待删除结点可能存在以下四种情况:

待删除结点无孩子结点
待删除结点只有左孩子结点(不管右孩子)
待删除结点只有右孩子结点(不管左孩子)
待删除结点左,右孩子结点都有

在实际删除操作中,可以将1和2 / 3合并起来,因为我们的逻辑是哪边有孩子就管理,没有孩子就可以不管,因此无孩子结点既可以和不管右孩子结点情况合并又可以和不管左孩子情况合并,合并后实际的删除情况及过程如下三种:

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

🕹️循环版Erase()函数

循环版Erase()函数实现如下,具体细节见代码注释:

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 (cur == _root)     //是根节点就没有父节点,直接让右孩子做根节点
				{
					_root = cur->_right;
				}
				else
				{
					if (parent->_right == cur)   //是父的右孩子就托孤到父亲的右指针
					{
						parent->_right = cur->_right;
					}
					else        //是父的左孩子就托孤到父亲的左指针
					{
						parent->_left = cur->_right;
					}
				}
			}
			else if (cur->_right == nullptr)    //右空托左孤
			{
				if (cur == _root)    //是根节点就没有父节点,直接让左孩子做根节点
				{
					_root = cur->_left;
				}
				else
				{
					if (parent->_right == cur)    //是父的右孩子就托孤到父亲的右指针
					{
						parent->_right = cur->_left;
					}
					else         //是父的左孩子就托孤到父亲的左指针
					{
						parent->_left = cur->_left;
					}
				}
			}
			else        //左右都不为空
			{
				//找左树的最右值
				Node* parent = cur;  //这里不能写=nullptr,防止删的节点的leftMax就是自己的左子树的情况,这样就不会进下面的while循环,parent没有被赋值,就会导致在9行后的if判断里出现对空指针解引用
				Node* leftMax = cur->_left;
				while (leftMax->_right)
				{
					parent = leftMax;
					leftMax = leftMax->_right;
				}

				swap(cur->_key, leftMax->_key);

				if (parent->_left == leftMax)
				{
					parent->_left = leftMax->_left;
				}
				else
				{
					parent->_right = leftMax->_left;
				}

				cur = leftMax;
			}
            
            //走到这里表示待删结点的孩子已经处理好了,可以直接释放了
			delete cur;
			return true;
		}
	}
	return false;
}

🕹️递归版EraseR()函数

递归版EraseR()函数实现如下,具体细节见代码注释:

bool EraseR(const K& key)
{
	return _EraseR(_root, key);
}

bool _EraseR(Node*& root, const K& key)
{
	if (root == nullptr)    //递归到空值表示待删元素不存在,返回删除失败
	{
		return false;
	}

	if (root->_key < key)    //小了,向右继续递归删
	{
		_EraseR(root->_right, key);
	}
	else if (root->_key > key)    //大了,向左继续递归删
	{
		_EraseR(root->_left, key);
	}
	else        //找到了,开始按三种情况删
	{
		Node*  del = root; //因为我们后面会更改root,防止delete时找不到待删元素,先记录下
		
		if (root->_left == nullptr)    //左空托右孤
		{
			root = root->_right;    //因为是引用,所以可以直接将自己改为右孩子
		}
		else if (root->_right == nullptr)    //右空托左孤
		{
			root = root->_left;    //因为是引用,所以可以直接将自己改为左孩子
		}
		else        //都有找接班
		{
			//找替代结点(左子树的最右值)
			Node* leftMax = root->_left;
			while (leftMax->_right)
			{
				leftMax = leftMax->_right;
			}
            
            //交换自己和接班的位置
			swap(root->_key, leftMax->_key);

            //然后复用递归删除自己就行,但是注意,因为自己和左子树的最右值,
            //即比自己小一点点的值交换了位置,那么再找自己删自己的时候就不能
            //从根节点开始找,因为对新根来说自己比它大一点那应该在右子树去找,
            //但实际自己被换到了左子树,所以应该一开始就在根结点的左子树找自己
			return _EraseR(root->_left, key);
		}
        
        //走到此代表待删结点的孩子已经处理好了,可以释放空间了
		delete del;
		return true;
	}
}

🎏实现BSTree类析构函数

由于析构函数是按后序遍历递归删除整颗树的,所以我们给析构函数也创建一个子函数, 按先左,再右,再根的顺序递归删除二叉树即可,实现代码及注释如下:

//析构函数
~BSTree()
{
	Destroy(_root);
}

//析构函数子递归
void Destroy(Node*& root)
{
	if (root == nullptr)
		return;

	Destroy(root->_left);    //先递归删左子树
	Destroy(root->_right);    //再递归删右子树

	delete root;        //最后删掉根节点
	root == nullptr;    //用引用传参还可以直接在这里将root置为nullptr
}

🎏实现BSTree类拷贝构造函数

由于拷贝构造函数是按先序遍历递归拷贝整颗树的,所以我们给拷贝构造函数也创建一个子函数, 按先根,再左,再右的顺序递归拷贝整颗二叉树即可,实现代码及注释如下:

//拷贝构造
BSTree(const BSTree<K>& t)
{
	_root = Copy(t._root);
}

//拷贝构造子函数
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);    //后递归链接右子树

	return copynode;        //注意最后要将当前结点返回给上一层链接
}

🎏实现BSTree类赋值运算符重载operator=函数

赋值运算符重载函数我们照例像之前实现STL容器那样偷个懒,直接借用形参是实参的一份临时拷贝这一特点,将this指针和待赋值的参数的形参做交换,这样就可以无痛完成赋值运算了,实现代码如下:

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

三.项目完整代码

我们将程序运行的代码分别在两个工程文件中编辑,完整代码如下:

📌test.cpp文件

该部分文件主要包含部分二叉搜索树功能测试代码,大家可以酌情参考。

#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(4);
	t.InOrder();

	t.Erase(6);
	t.InOrder();

	t.Erase(7);
	t.InOrder();

	t.Erase(8);
	t.InOrder();

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

//测试递归插入删除函数
void testBSTree2()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	BSTree<int> t;

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

	t.EraseR(4);
	t.InOrder();

	t.EraseR(6);
	t.InOrder();

	t.EraseR(7);
	t.InOrder();

	t.EraseR(8);
	t.InOrder();

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

void testBSTree3()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	BSTree<int> t;

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

	//测试拷贝构造
	BSTree<int> t1(t);
	t1.InOrder();
}

void testBSTree4()
{
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	BSTree<int> t;

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

	//测试赋值运算符重载
	BSTree<int> t1 = t;
	t1.InOrder();
}
int main()
{
	testBSTree1();
	return 0;
}

📌BinarySearchTree.h文件

#pragma once

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

	//缺省值的作用是在无参调用时直接去调用模板实例化的类的无参构造函数
	//这里一定不能将缺省值给0/nullptr!因为你不知道模板实例化的类具体到底是内置类型还是自定义类型(如Date)
	//所以要显示调用T类型它自己的无参构造函数
	BSTreeNode(const K& key = K())
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}
};

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

	//拷贝构造
	BSTree(const BSTree<K>& t)
	{
		_root = Copy(t._root);
	}

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

	~BSTree()
	{
		Destroy(_root);
	}

	bool Insert(const K& key)
	{ 
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}

		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
			{
				return false;
			}
		}
		cur = new Node(key);

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

	//循环版Find
	bool 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 true;
			}
		}
		return false;
	}


	//删除,四个场景
	//1.叶子  2. 一个孩子     托孤
	//3. 两个孩子      替换法:左子树的最大(右)结点,或者右子树的最小(左)节点
	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 (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_right == cur)
						{
							parent->_right = cur->_right;
						}
						else
						{
							parent->_left = cur->_right;
						}
					}
				}
				else if (cur->_right == nullptr)//右空托左孤
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_right == cur)
						{
							parent->_right = cur->_left;
						}
						else
						{
							parent->_left = cur->_left;
						}
					}
				}
				else//左右都不为空
				{
					//找左树的最右值
					Node* parent = cur;//写nullptr必崩
					Node* leftMax = cur->_left;
					while (leftMax->_right)
					{
						parent = leftMax;
						leftMax = leftMax->_right;
					}

					swap(cur->_key, leftMax->_key);

					if (parent->_left == leftMax)
					{
						parent->_left = leftMax->_left;
					}
					else
					{
						parent->_right = leftMax->_left;
					}

					cur = leftMax;
				}
				delete cur;
				return true;
			}
		}
		return false;
	}


	void InOrder()
	{
		_InOrder(_root);
	}

	bool FindR(const K& key)
	{
		return _FindR(_root, key);
	}

	bool InsertR(const K& key)
	{
		return _InsertR(_root, key);
	}

	bool EraseR(const K& key)
	{
		return _EraseR(_root, key);
	}

private:
	//将部分递归子函数放在这里,对外更好的封装这个类模板

	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);
		return copynode;
	}

	//析构函数子递归
	void Destroy(Node*& root)
	{
		if (root == nullptr)
			return;
		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
		root == nullptr;
	}

	bool _EraseR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			return false;
		}

		if (root->_key < key)
		{
			_EraseR(root->_right, key);
		}
		else if (root->_key > key)
		{
			_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* leftMax = root->_left;
				while (leftMax->_right)
				{
					leftMax = leftMax->_right;
				}

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

				return _EraseR(root->_left, key);
			}

			delete del;
			return true;
		}
	}

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

	//递归Find子递归
	bool _FindR(Node* root, const K& key)
	{
		if (root == nullptr)
		{
			return false;
		}

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

	//中序遍历子递归
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			//cout << "NULL" << endl;
			return;
		}

		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}

	Node* _root;
};