C++ 二叉查找树各种功能的实现（插入、前中后递归非递归遍历、合并（复制）删除、节点个数与树深度、清空树）

1、简要概念

根节点：没有父节点只有子节点。
叶结点：没有子节点。
二叉树：节点可以包含两个子节点（也可能是空）的树，每一个节点区分为左节点和右节点。
完全二叉树：所有的终端节点都有两个子节点，所有叶结点位于同一层次。
二叉查找树（有序二叉树）：对于树中的每个节点n，其左子树中的所有值小于节点n中的值，其右子树中的所有值大于节点n中的值。

2、二叉查找树各种功能实现

#include<iostream>
//#include "BST.h"
#include<stack>
using namespace std;

template<class T>
class BSTNode
{
public:
	BSTNode(T tem = 0, BSTNode* left_tem = NULL, BSTNode* right_tem = NULL) :el(tem), left(left_tem), right(right_tem) {}
	~BSTNode(){
		el = 0;
		left = NULL;
		right = NULL;
	}
	T el;
	BSTNode* left;
	BSTNode* right;
};

template<class T>
class BST
{
public:
	//NULL指的是指针的地址，并不是说root_tem的构造函数，此构造函数的目的是让root的地址为空
	BST(BSTNode<T>* root_tem = NULL) :root(root_tem) {}
	~BST() { destory(false); }
	void creat(int num);
	void insert(BSTNode<T>*&);
	void insert(T& el);
	void delete_node_copy(const T &, bool is);
	void delete_node_copy(BSTNode<T>*& node);
	void delete_node_merge(const T&, bool is);
	void delete_node_merge(BSTNode<T>*&);
	void preorder() { preorder(root); }
	void inorder() { inorder(root); }
	void postorder() { postorder(root); }
	void preorder_nonrec() { preorder_nonrec(root); }
	void inorder_nonrec() { inorder_nonrec(root); }
	void postorder_nonrec() { postorder_nonrec(root); }
	void destory(bool is);
	int nodenum();
	int treedepth();

protected:
	int treedepth(BSTNode<T>*);
	void preorder(BSTNode<T>*);
	int nodenum(BSTNode<T>*);
	void inorder(BSTNode<T>*);
	void postorder(BSTNode<T>*);
	void preorder_nonrec(BSTNode<T>* node);
	void inorder_nonrec(BSTNode<T>* node);
	void postorder_nonrec(BSTNode<T>* node);
	void destory(BSTNode<T>*&);
private:
	BSTNode<T> * root;
};

template<class T>
void BST<T>::creat(int num)
{
	T el;
	if (num <= 0) {
		cout << "输入有误" << endl;
		return;
	}
	for (int i = 0;i < num;++i) {
		cout << "选择你需要插入的数值" << endl;
		cin >> el;
		insert(el);
	}
	return;
}

template<class T>
void BST<T>::insert(BSTNode<T> *& node)
{	
	//使用引用，防止函数内部则会重新生成一个临时指针，内容与传入参数的指针一致。
	BSTNode<T> * tem = root, *prev = NULL;
	while (tem != 0) {
		prev = tem;
		if (node->el < tem->el)
			tem = tem->left;
		else
			tem = tem->right;
	}
	if (root == NULL)
		root = node;
	else if (node->el < prev->el)
		prev->left = node;
	else
		prev->right = node;
	return;
}

template<class T>
void BST<T>::insert(T& el)
{
	BSTNode<T> * tem = root, *prev = NULL;
	//找到el所处的合适位置
	while (tem != NULL) {
		prev = tem;
		if (el < tem->el)
			tem = tem->left;
		else
			tem = tem->right;
	}
	//第一次insert，此时root为NULL
	//注意执行了第一个if之后就不再执行else if里面的内容了
	//后面的则是为了添加子节点
	if (root == NULL)
		root = new BSTNode<T>(el);
	else if (el < prev->el)
		prev->left=new BSTNode<T>(el);
	else
		prev->right=new BSTNode<T>(el);
	return;
}

//const T &el引用，只是为了不生成中间临时变量
//bool is只是为了显示与否，防止已经删除了el，
//再去进行检测的话，要是出现“不存在节点”就尴尬了
template<class T>
void BST<T>::delete_node_copy(const T &el, bool is)
{	

	BSTNode<T>* tmp = root, *prev = NULL;
	if (root == NULL) {
		cout << "二叉查找树为空" << endl;
		return;
	}
	while (tmp != NULL) {
		if (el == tmp->el)
			break;
		if (el < tmp->el) {
			prev = tmp;
			tmp = tmp->left;
		}
		else {
			prev = tmp;
			tmp = tmp->right;
		}
	}
	if (tmp == NULL) {
		if (is)
			cout << "二叉查找树中不含此节点" << endl;
		return;
	}
	else if (tmp == root)
		delete_node_copy(root);
	else if (el < prev->el)
		//注意这里要用prev->left，而不仅仅是tmp，因为仅用tmp会导致
		//prev->left成为野指针
		delete_node_copy(prev->left);
	else
		delete_node_copy(prev->right);
	//采用递归再一次查找是否存在el的值，false为不打印“二叉查找树中不含此节点”
	delete_node_copy(el, false);
}

template<class T>
void BST<T>::delete_node_copy(BSTNode<T>*& node)
//输入参数要使用引用，不然待删除的指针会成为野指针
//上面那句话是错的，不会产生野指针，使用引用第一个原因是
//为了不生成中间临时变量，提高效率
//第二个原因是为了改变node可以同时改变prev->left or prev->right
{
	BSTNode<T>* tmp = node, *prev = NULL;
	if (node == NULL) {
		cout << "输入的是空节点" << endl;
		return;
	}
	//待删除的节点没有左子节点，那么直接将右子节点作为其本身
	//或者没有左右子节点，那么将NULL左右node本身
	if (node->left == NULL)
		node = node->right;
	else if (node->right == NULL)
		node = node->left;
	//倘若节点左右子节点都存在
	else {
		prev = tmp;
		//取到待删除节点的左子节点，
		tmp = tmp->left;
		//找到左子节点下的最右节点
		//也就是比待删除节点小，但是在待删除节点的左边是最大值
		while (tmp->right != NULL) {
			prev = tmp;
			tmp = tmp->right;
		}
		//将此最大值的值赋值给待删除节点的值，这样变不会违反二叉查找树的规则
		node->el = tmp->el;
		//考虑node的左子节点没有右子节点
		if (prev == node)
			prev->left = tmp->left;
		//倘若node的左子节点有右子节点，
		else
			//tmp的左子节点永远比prev大，因为tmp是prev的右子节点
			//不用考虑tmp->right，因为已经是最右！
			prev->right = tmp->left;
	}
	//就算没有析构函数，delete tmp也会同时回收el,left,right
	delete tmp;
}

template<class T>
void BST<T>::delete_node_merge(const T & el, bool is)
//const表示在本函数中不能给el赋值，并不代表外界传入的实参一定是const类型
//注意事项同delete_node_copy
{
	BSTNode<T>* tmp = root, *prev = NULL;

	if (root == NULL) {
		cout << "二叉查找树为空" << endl;
		return;
	}
	while (tmp != NULL) {
		if (el == tmp->el)
			break;
		if (el < tmp->el) {
			prev = tmp;
			tmp = tmp->left;
		}
		else {
			prev = tmp;
			tmp = tmp->right;
		}
	}
	if (tmp == NULL) {
		if (is)
			cout << "二叉查找树中不含此节点" << endl;
		return;
	}
	else if (tmp == root)
		delete_node_merge(root);
	else if (el < prev->el)
		delete_node_merge(prev->left);
	else
		delete_node_merge(prev->right);
	delete_node_merge(el, false);
}

template<class T>
void BST<T>::delete_node_merge(BSTNode<T>*& node)
//注意事项同delete_node_copy
{
	BSTNode<T>* tmp = node;
	if (node == NULL) {
		cout << "输入空节点" << endl;
		return;
	}
	if (node->left == NULL)
		node = node->right;
	else if (node->right == NULL)
		node = node->left;
	else {
		//找到待删除节点的左子节点的最右子节点，
		//也就是小于待删除节点的值中的最大节点
		tmp = tmp->left;
		while (tmp->right != NULL)
			tmp = tmp->right;
		//将待删除节点的右子节点（大）放置在最右子节点（小）的右边，
		tmp->right = node->right;
		tmp = node;
		node = node->left;
	}
	//不能直接delete node，因为此时node已经被赋予新值
	delete tmp;
}

template<class T>
void BST<T>::destory(bool is)
{
	if (is && root == NULL) {
		cout << "二叉查找树为空" << endl;
		return;
	}
	destory(root);
	return;
}
//仅可以采用后序遍历删除节点
template<class T>
void BST<T>::destory(BSTNode<T>* &node)
{
	if (node != NULL) {
		destory(node->left);
		destory(node->right);
		delete node;
		node = NULL;
	}
	return;
}

template<class T>
int BST<T>::nodenum()
{
	if (root == NULL) {
		cout << "二叉查找树为空,节点数为0" << endl;
		return 0;
	}
	else {
		int i = nodenum(root);
		cout << "此二叉查找树共有" << i << "个节点" << endl;
		return i;
	}
}

template<class T>
int BST<T>::nodenum(BSTNode<T>* node)
{
	if (node != NULL) {
		//left代表节点node左子树的节点个数
		int left = nodenum(node->left);
		//right代表节点node右子树的节点个数
		int right = nodenum(node->right);
		//将左右节点个数相加再加一，得到包括自身的节点个数（一代表的意义）
		return left + right + 1;
	}
	return 0;
}

template<class T>
int BST<T>::treedepth()
{
	if (root == NULL) {
		cout << "二叉查找树为空,深度为0" << endl;
		return 0;
	}
	else {
		int i = treedepth(root);
		cout << "此二叉查找树的深度为" << i << endl;
		return i;
	}
}

template<class T>
int BST<T>::treedepth(BSTNode<T>* node)
{
	if (node != NULL) {
		//left代表节点node左子树的深度
		int left = treedepth(node->left);
		//right代表节点node右子树的深度
		int right = treedepth(node->right);
		//取左右子数深度的较大值再加一，得到包括自身的节点深度
		return (left > right) ? left + 1 : right + 1;
	}
	return 0;
}

template<class T>
void BST<T>::preorder(BSTNode<T>* node)
{
	if (node == root && node == NULL)
		cout << "空" << endl;
	if (node != NULL) {
		cout << node->el << "  ";
		preorder(node->left);
		preorder(node->right);
	}
	return;
}

template<class T>
void BST<T>::inorder(BSTNode<T>* node)
{
	if (node == root && node == NULL)
		cout << "空" << endl;
	if (node != NULL) {
		inorder(node->left);
		cout << node->el << "  ";
		inorder(node->right);
	}
	return;
}

template<class T>
void BST<T>::postorder(BSTNode<T>* node)
{
	if (node == root && node == NULL)
		cout << "空" << endl;
	if (node != NULL) {
		postorder(node->left);
		postorder(node->right);
		cout << node->el << "  ";
	}
	return;
}
//注意pop只是弹出stack的起始值，并非返回一个值。
//而top则是返回stack的起始值，不弹出。
template<class T>
void BST<T>::preorder_nonrec(BSTNode<T>* node)
{
	stack<BSTNode<T>*> travstack;
	BSTNode<T>* tem = node;
	if (tem == NULL) {
		cout << "空" << endl;
		return;
	}
	travstack.push(tem);
	while (!travstack.empty()) {
		//先弹出并打印tem
		tem = travstack.top();
		travstack.pop();
		cout << tem->el << "  ";
		//由于栈是先进后出，因此先将右子节点压栈
		if (tem->right != NULL)
			travstack.push(tem->right);
		//将左子节点压栈
		if (tem->left != NULL)
			travstack.push(tem->left);
	}
	return;
}

template<class T>
void BST<T>::inorder_nonrec(BSTNode<T>* node)
{
	stack<BSTNode<T>*> travstack;
	BSTNode<T>* tem = node;
	if (tem == NULL) {
		cout << "空" << endl;
		return;
	}
	while (tem != NULL) {
		//first
		//压栈顺序：右子节点->本节点，为了以及子树节点的右子节点
		//节点往左移
		while (tem != NULL) {
			if (tem->right != NULL)
				travstack.push(tem->right);
			travstack.push(tem);
			tem = tem->left;
		}
		//second
		//把栈中节点拿出来并且打印
		tem = travstack.top();
		travstack.pop();
		//当子树的根节点存在右节点，则不打印，符合中序遍历
		while (!travstack.empty() && tem->right == NULL) {
			cout << tem->el << "  ";
			tem = travstack.top();
			travstack.pop();
		}
		//third
		//打印子树的根节点
		cout << tem->el << "  ";
		//fourth
		//将第一步中的子树根节点的右子节点弹出
		//如果空了，则说明已经全部打印完，退出循环
		if (!travstack.empty()) {
			tem = travstack.top();
			travstack.pop();
		}
		else
			tem = NULL;
	}
	return;
}

template<class T>
void BST<T>::postorder_nonrec(BSTNode<T>* node)
{
	stack<BSTNode<T>*> travstack;
	BSTNode<T>* tem = node;
	BSTNode<T>* tem2 = node;
	if (tem == NULL) {
		cout << "空" << endl;
		return;
	}
	while (tem != NULL) {
		//first
		//找到最左子节点
		for (;tem->left != NULL;tem = tem->left)
			travstack.push(tem);
		//second
		//倘若没有右子节点，则打印
		//第二个条件见下图黄色线部分，应用于子树最终所有右子节点的打印
		//这也是为什么后序遍历比中序前序需要加多一个变量的原因
		while (tem->right == NULL || tem->right == tem2) {
			cout << tem->el << "  ";
			tem2 = tem;
			if (travstack.empty())
				return;
			else {
				tem = travstack.top();
				travstack.pop();
			}
		}
		//重新将子树根节点压栈，此时其一定会有右子节点
		travstack.push(tem);
		//third
		//去右边
		tem = tem->right;
	}
	return;
}

int main()
{
	BST<int> l;
	int n;
	int i;
	cout << "1.创建二叉查找树   2.前序遍历   3.中序遍历   4.后序遍历  \n";
	cout << "5.输入创建节点的数值   6.合并删除_删除的节点   7.复制删除_删除的节点\n";
	cout << "8.清空二叉查找树   9.二叉查找树的节点个数   10.二叉查找树的深度   \n";

	do {
		cout << "请输入要执行的操作: " << endl;
		cin >> i;
		switch (i)
		{
		case 1:
			l.destory(false);
			cout << "输入创建二叉查找树中节点的个数" << endl;
			cin >> n;
			l.creat(n);
			break;
		case 2:
			cout << "前序遍历为：  ";
			l.preorder();
			cout << endl;
			break;
		case 3:
			cout << "中序遍历为：  ";
			l.inorder();
			cout << endl;
			break;
		case 4:
			cout << "后序遍历为：  ";
			l.postorder();
			cout << endl;
			break;
		case 5:
			cout << "输入创建节点的数值" << endl;
			cin >> n;
			l.insert(n);
			cout << endl; 
			break;
		case 6:
			cout << "合并删除_删除的节点数值为  " << endl;
			cin >> n;
			l.delete_node_merge(n, true);
			cout << endl;
			break;
		case 7:
			cout << "复制删除_删除的节点数值为  " << endl;
			cin >> n;
			l.delete_node_copy(n, true);
			cout << endl;
			break;
		case 8:
			l.destory(true);
			cout << endl;
			break;
		case 9:
			l.nodenum();
			break;
		case 10:
			l.treedepth();
			break;
		case 11:
			cout << "前序遍历（非递归）为：  ";
			l.preorder_nonrec();
			cout << endl;
			break;
		case 12:
			cout << "中序遍历（非递归）为：  ";
			l.inorder_nonrec();
			cout << endl;
			break;
		case 13:
			cout << "后序遍历（非递归）为：  ";
			l.postorder_nonrec();
			cout << endl;
			break;
		}
	} while (i != 0);
	system("pause");
	return 0;
}

3、个别功能详细说明

插入（输入参数为类节点实例）

template<class T>
void BST<T>::insert(BSTNode<T> *& node)
之所以使用引用是不会产生类的复制构造函数，提高效率吗？

肯定不是的，为什么？因为传入参数是指针（4字节），而并非一个类的实例，因此并不会调用类的复制构造函数，但倘若不是用引用，函数内部则会重新生成一个临时指针，内容与传入参数的指针一致。

在这里引用和不引用好像在效率与运行中没什么太大区别，但在复制删除中，引用与非引用则有很大区别。

复制删除（delete_node_copy(const T &el, bool is)）

	if (tmp == NULL) {
		if (is)
			cout << "二叉查找树中不含此节点" << endl;
		return;
	}
	else if (tmp == root)
		delete_node_copy(root);
	else if (el < prev->el)
		//注意这里要用prev->left，而不仅仅是tmp，因为仅用tmp会导致
		//prev->left成为野指针
		delete_node_copy(prev->left);
	else
		delete_node_copy(prev->right);
为什么要这么麻烦用delete_node_copy(prev->left);和delete_node_copy(prev->right);delete_node_copy(root);而不直接用

delete_node_copy(tmp);呢，tmp不是在上面的步骤中已经是待删除的节点了吗？

因为我们知道，在（delete_node_copy(BSTNode<T>*& node)）中，将会对node赋值，即以下代码：
	if (node->left == NULL)
		node = node->right;
	else if (node->right == NULL)
		node = node->left;
	else {
        ......
倘若使用tmp作为传入参数，我们就要首先知道tmp在上一个函数中只是作为一个临时变量，标志着待删除的节点，当我们下一个函数运行对node赋值时，由于使用的引用，因此修改的直接是tmp，没错你是修改了tmp，但是对于整棵树来讲是一点变化没有，因为节点与节点的联系就只有父节点的左右指针联系着子节点，但你现在只是修改了一个临时变量tmp 所指向的地址值，而没有去修改prev->left的值，因此是无用功的。

复制删除的步骤：检查待删除节点是否不存在左子节点或右子节点（因为这两种情况好处理）->若存在，则找到树中比待删除节点的值小的节点中的最大值（即待删除节点的左子节点的最右子节点）->将最右子节点的值与待删除节点交换（不违反树的性质，待删除节点左边仍然是比其小，右边仍然是比其大）->判断待删除节点的左子节点是否存在右子节点->相应的左右指针变换->删除最右子节点

使用delete_node_copy(BSTNode<T>* node)（注意没有引用符号&）会产生类的复制构造函数吗？并不会！！！只会产生一个临时指针，内容等同于传入参数，因为你的传入参数类型是*，指针因此不会，会产生类的构造函数的传入参数是delete_node_copy(BSTNode<T> node)。

合并删除（注意事项同复制删除）
清空二叉树

为什么在destory(BSTNode<T>* &node)的末尾要添加delete node;node = NULL;而在delete_node_copy(BSTNode<T>*& node)和delete_node_merge(BSTNode<T>*& node)的末尾只是delete tmp;

首先我们要知道destory(BSTNode<T>* &node)使用的是引用，而传入参数是destory(root);当我们在delete root时，只不过是把root上的内容释放了，但&root中仍然存在root的地址，指针依旧可用，但指针指向地址的内容却已经被释放，这就是我们所属片的野指针，这样会造成指针的内容不可访问而出错，因此我们需要添加root=NULL，初始化指针。

而在delete_node_copy(BSTNode<T>*& node)和delete_node_merge(BSTNode<T>*& node)中，我们delete的是tmp，一个在本函数才生成的临时变量，因此它会随着函数的结束而编译器自动将其销毁，生命周期仅为一个函数，因此不需要我们手动销毁。

root的生命周期与类相关，而在我们这个函数中，此类的生命周期就是main函数的周期，因此其不会像tmp一样自动销毁，当我们一个main函数是不会停止，需要一直运行时，那么这些野指针永远不会被销毁，存在极大的安全隐患。

清空二叉树只可以用后序遍历，不可用前序中序遍历，因为当你把root给删除了，自然也就不可以在删除剩下的未删除的节点了。

前序遍历非递归

步骤：判断root是否非空->将root压栈->判断栈中是否非空->从栈中取元素->visit(node)->将右子树压栈->将左子树压栈->跳至第三步

前序遍历是先打印左边，因此左边要比右边先压栈；当左子树都visit后，则栈中只剩下右子树的起始节点，因此又开始打印右子树的节点。

中序遍历非递归

先将节点的右子节点以及自身按顺序压栈->而后将节点左移->直至到达最左子节点

将栈中节点拿出打印，若节点含有右子节点则停止

将子树根节点打印

将栈中的元素弹出，此时弹出的元素是之前先将右子节点保存的元素，这样就可以跳转到其他子树

后续非递归

将节点左移，边移边压栈，此时tem已到最左子节点，但tem没有到栈里去

若没有右子节点，则打印tem，且从栈中弹出，依次检查

若有右子节点，则重新压栈，因为后序中子树根节点是最后遍历的

节点右移。

注意黄色线部分就是判断（tem->right == tem2）的意义所在，此时后序由于是从后往前，因此需要多加一个判断，不仅仅是right==NULL。

原文链接：https://blog.csdn.net/qq_41620518/article/details/88774342

你可能也喜欢