二叉查找树算法_二叉判定树和二叉排序树

文章目录

二叉搜索树（二叉排序树、二叉查找树）

二叉搜索树（二叉排序树、二叉查找树）

二叉搜索树基本概念

二叉搜索树又称二叉排序树、二叉查找树，它或者是一棵空树，或者是具有以下性质的二叉树:

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

下图就是一棵二叉搜索树：

下图不是一棵二叉搜索树：

二叉搜索树基本操作

二叉树的结构定义

为了使我们的二叉搜索树能够存储不同类型的数据，我们这里使用模板。

首先需要一个基本的结构体类型去存储数据。

（ps：在这里要声明一点，在C++中，struct实际上是一个类，该类与C++其他的类不同的是，其成员变量和成员方法默认都是公有的。由于struct在C++中也是类，所以 struct的类也会有构造函数。）

首先定义一个结构体BSTreeNode,该结构体用来存储数据。并且该结构体还包含了左指针与右指针。该结构体可以理解为二叉搜索树中的每一个基本节点。

再定义一个BSTree的类，该类是二叉搜索树类，里面包含了二叉搜索树根节点(root)的指针，以及相关的插入、查找、删除等基本实现函数。

template <class T>
struct BSTreeNode
{ 
   
	BSTreeNode(const T& _key) :left(nullptr), right(nullptr), key(_key)
	{ 
   }
public:
	BSTreeNode<T>* left;
	BSTreeNode<T>* right;
	T key;
};

template<class T>
class BSTree
{ 
   
public:
	typedef BSTreeNode<T> Node;
	Node* root = nullptr;
}

为了方便后续代码的编写，这里我们将 BSTreeNode 直接重新定义为Node,这样在之后我们就可以用Node来代表BSTreeNode，大大减少了工作量。

那么二叉搜索树的基本框架就定义完成了。接下来我们看二叉搜索树的基本函数是如何编写的。

二叉搜索树的插入

插入的具体过程如下：

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

首先判断树是否为空，如果树为空，那么直接插入节点

bool _InsertB(Node*& root, const T& key)
{ 
   
	if (!root)
	{ 
   
		root = new Node(key);
		return true;
	}
}

树不为空，我们按二叉搜索树性质查找插入位置，插入新节点

这里我们演示插入节点：15

先与根节点比较

再与值为14的节点比较

再与值为16的节点比较

最后 ptr 指针指向空，此时该ptr指针的位置就是待插入节点的位置。

那么流程我们分析完了代码该如何编写呢？

代码的编写可以分为两种，一是通过循环，二是通过递归，我们这里两种都会进行展示。

循环查找插入
既然通过循环，那么我们肯定要知道当前 ptr 指针的双亲结点，否则只有一个指向空的指针无法进行插入。所以我们需要一个指针 parent ，去记录 ptr 指针的上一个位置，即 ptr 的双亲结点指针。当 ptr 指针指向空的时候，说明已经找到了当前待插入节点的正确位置，那么此时使用parent指针就可以将待插入节点进行插入。

具体代码如下：

bool _Insert(const T& key)
{ 
   
	if (!root)
		root = new Node(key);
	else
	{ 
   
		Node* ptr = root, * parent = nullptr;
		while (ptr)
		{ 
   
			parent = ptr;
			if (ptr->key > key)
				ptr = ptr->left;
			else if (ptr->key < key)
				ptr = ptr->right;
			else
				return false;
		}
		ptr = new Node(key);
		if (parent->key > key)
			parent->left = ptr;
		else
			parent->right = ptr;
	}
	return true;
}

当 ptr 指针为空的时候就会退出 while 循环。此时创建一个值为 key 的新节点，用 ptr指向新创建的节点。
在这里插入的时候会发现有一个问题，你如何知道当前新创建的节点是插入在 parent (原ptr的双亲结点)节点的左侧还是右侧？显然这是不清楚的，那么我们需要去比较parent（双亲结点）的值与待插入结点的值的大小。如果待插入节点的值大于parent（双亲节点）的值，那么就应该插入parent的右侧，否则就插入在parent的左侧。

当前 ptr 指向了待插入的新节点。parent指向了待插入区域的双亲节点，但 parent 并不知道 ptr 应该放在他的左侧还是右侧，此时需要比较 parent 与 ptr 的值的大小才能正确插入。
即上述代码中的：

if (parent->key > key)
		parent->left = ptr;
else
		parent->right = ptr;

最后插入成功，返回true。

递归查找插入
思路与循环一样，但是代码用递归实现

代码如下：

bool _InsertB(Node*& root, const T& key)
{ 
   
	if (!root)
	{ 
   
		root = new Node(key);
		return true;
	}
	if (key < root->key)
		return _InsertR(root->left, key);
	else if (key > root->key)
		return _InsertR(root->right, key);
	return false;
}

同循环查找插入一样。当递归下去root指针为空指针的时候，则说明已经找到了待插入的位置，那么此时创建新的节点并赋值，再返回true，代表插入成功。
值得注意的是，这里的函数形参在传递指针时使用了引用。即Node*& root，使用引用的好处是：当前函数的参数 root 即为上一层节点的左孩子指针或右孩子指针。也就是说修改 root 的值。实际上就是修改了上一层节点的左指针或者右指针。
（PS：这里看不懂的可以去先查阅一下引用的定义，这里简单说明：引用即为另一个变量的别名。也就是说，root即为上一层双亲结点的左孩子或右孩子的指针，就拿 _InsertR(root->left, key)举例说明，当前传递下去的是root节点的左孩子指针，那么在递归到下一层时root->left即为下一层递归的root,那么此时去修改root也就能直接修改上一层的左孩子指针）

这样做的好处是我们不必记录当前待插入区域的双亲结点的指针。直接修改root，将root指向新创建的节点，就能成功插入。相比循环查找插入简化很多步骤。

此时就有人问，既然引用这么好，为什么在上一个循环查找插入时不采用引用的方式？这里是因为引用在定义时就需要。给出所引用的对象。也就是说:

int a=0;
int &b=a;

引用在创建时就需要给出所引用的对象，这里创建了b引用了a，那么后续b永远只能是a的别名，无法改变。
此时就有人问下面这段代码不就使b引用了b吗？输出的结果为20。

int c=20;
b=c;
cout<<b<<endl;

这其实是错误的，引用在定义时就已经确定了是对a的引用，即绑定了a。这段代码看似将b又引用了c。打印b的值后为20。看似将b又引用了c。实际上这只是赋值，将b的值赋成了20，又因为b是a的别名，b就是a，a也是b，那么将b赋值为20，同时就修改了a，此时a的值也为二十。这也说明了b并没有重新引用c。

二叉搜索树的查找

从根开始比较查找，比根节点大则往右子树查找，比根节点小则往左子树查找。
最多查找高度次，走到到空，还没找到，这个值不存在。

先看流程图：

演示查找整数4的过程

同插入操作一样，也是从根节点开始，依次查找。

如果当前节点的值小于目标值，那么就走当前节点的右子树。如果当前节点的值大于目标值。只那么就走当前节点的左子树。

同样查找也分为循环查找和递归查找，这里不再详细说明，给出两个查找的代码：

循环查找

bool _find(const T& key)
{ 
   
	Node* cur = root;
	while (cur)
	{ 
   
		if (cur->key > key)
			cur = cur->left;
		else if (cur->key < key)
			cur = cur->right;
		else
			return true;
	}
	return false;
}

递归查找

bool _findR(Node* root, const T& key)
{ 
   
	if (!root)
		return false;
	if (root->key > key)
		return _findR(root->left, key);
	else if (root->key < key)
		return _findR(root->right, key);
	return true;
}

遍历操作

二叉搜索树的遍历大多用中序遍历，因为中序遍历所得到的值都是升序的。
代码如下：

void _inorder(Node* ptr)
{ 
   
	if (!ptr)
		return;
	_inorder(ptr->left);
	cout << ptr->key << " ";
	_inorder(ptr->right);
}

删除操作

二叉搜索树的删除操作也是二叉搜索树中最重要最精髓的部分。

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情
况：

要删除的结点无孩子结点
要删除的结点只有左孩子结点
要删除的结点只有右孩子结点
要删除的结点有左、右孩子结点

看起来有待删除节点有4中情况，实际情况a可以与情况1或者2合并起来，因此真正的删除过程如下：

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

被删除结点为叶子结点

直接从二叉排序中删除即可，不会影响到其他结点。例如删去0：

被删除结点仅有一个孩子

仅有一个左孩子
以值为5的节点为例：它没有右孩子，只有左孩子。（先把10指向5的左指针移动，去指向3，然后再删除5）
仅有一个右孩子
以值为16的节点为例：它没有左孩子，只有右孩子。（先把14指向16的右指针移动，去指向17，然后再删除16）

被删除结点左右孩子都在

我们假设删除根节点10，流程图如下：

这里我们删除的是根节点10。我们寻找10结点的左子树中的最大值。

先遍历10节点左子树的第一个节点，随后去寻找左子树中最右侧的节点，依次往下遍历，如果往下遍历的过程中存在右节点，那么就继续递归直到遍历到的节点没有右孩子为止，那么此时得到的这个节点，就是10节点左子树中的最大值。此时我们交换10和8再删除10。就成功完成了删除当左右孩子都存在时的的节点的情况。

当然，我们也可以采用寻找10节点右子树中的最小值交换，一样可以成功删除当左右孩子都存在时的情况的节点。

当然这里存在特殊情况，如图：

此时要删除8节点。8节点有左右孩子。寻找左子树中最大值时，8节点的左孩子就是左子树的最大值。那么此时的处理方法可以是：

交换5和8的值，然后递归执行删除5节点。此时的情况就转化为：删除5节点。并且该节点没有右孩子。
如果不采用递归的方式，那么我们此时可以做判断。判断寻找8节点的左子树最大值的指针，是否等于八节点的左孩子指针，如果两者相等，那么就说明8节点左子树中的最大值，就是8节点的左孩子。那么此时对这种情况进行特殊处理即可。处理方法就是交换后删除5节点，而此时就如同删除没有右孩子的节点情况相同。

代码如下：
ps：代码中删除当左右孩子都存在时，采用的方法是寻找右子树中的最小值。

非递归

bool _erease(const T& key)
{ 
   
	if (!root)
		return false;
	Node* cur = root, * parent = nullptr;
	while (cur)
	{ 
   
		parent = cur;
		if (cur->key > key)
			cur = cur->left;
		else if (cur->key < key)
			cur = cur->right;
		else
		{ 
   
			Node* tmp = cur;
			if (!cur->left)  //没有左子树
			{ 
   
				if (cur == root)
				{ 
   
					root = cur->right;
				}
				else
				{ 
   
					if (parent->left == cur)
						parent->left = cur->right;
					else
						parent->right = cur->right;
				}
			}
			else if (!cur->right)  //没有右子树
			{ 
   
				if (cur == root)
				{ 
   
					root = cur->left;
				}
				else
				{ 
   
					if (parent->left == cur)
						parent->left = cur->left;
					else
						parent->right = cur->left;
				}
			}
			else   //左右孩子都在
			{ 
   
				//左右孩子都在的情况需要替换，可以用当前需要被删除的节点的左子树上的最大值(左子树的右下角)，或者右子树的最小值(右子树的左下角)，
				//这里统一用右子树的坐下角

				Node* ret = cur->right, * ret_parent = cur;
				while (ret->left)
				{ 
   
					ret_parent = ret;
					ret = ret->left;
				}
				swap(cur->key, ret->key);
				tmp = ret;
				if (ret == ret_parent->right)    //如果满足这个条件，那么说明待删除节点cur的右孩子没有左孩子，那么直接等于cur右孩子的右孩子即可
					ret_parent->left = ret->left;
				else
					ret_parent->right = ret->right;
			}
			delete tmp;
			return true;
		}
	}
	return false;
}

递归实现

bool _ereaseR(Node*& root, const T& key)
{ 
   
	if (root->key > key)
		return _ereaseR(root->left, key);
	else if (root->key < key)
		return _ereaseR(root->right, key);
	else
	{ 
   
		Node* tmp = root;
		if (!root->left)
		{ 
   
			root = root->right;
		}
		else if (!root->right)
		{ 
   
			root = root->left;
		}
		else
		{ 
   
			Node* ret = root->right, * ret_parent = root;
			while (ret->left)
			{ 
   
				ret_parent = ret;
				ret = ret->left;
			}
			swap(ret->key, root->key);
			tmp = ret;
			if (ret == root->right)
				return _ereaseR(root->right, key);   
	     //不能用引用传递ret，因为传递ret，相当于是ret的别名，并不会修改双亲节点的孩子
			else
				return _ereaseR(ret_parent->left, key);
		}
		delete tmp;
		return true;
	}
}

代码总览

#include<iostream>
#include<vector>
using namespace std;

template <class T>
struct BSTreeNode
{ 
   
	BSTreeNode(const T& _key) :left(nullptr), right(nullptr), key(_key)
	{ 
   }
public:
	BSTreeNode<T>* left;
	BSTreeNode<T>* right;
	T key;
};


template<class T>
class BSTree
{ 
   
public:
	typedef BSTreeNode<T> Node;
	Node* root = nullptr;

	bool _InsertB(Node*& root, const T& key)
	{ 
   
		if (!root)
		{ 
   
			root = new Node(key);
			return true;
		}
		if (key < root->key)
			return _InsertR(root->left, key);
		else if (key > root->key)
			return _InsertR(root->right, key);
		return false;
	}



	bool _Insert(const T& key)
	{ 
   
		if (!root)
			root = new Node(key);
		else
		{ 
   
			Node* cur = root, * parent = nullptr;
			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);
			if (parent->key > key)
				parent->left = cur;
			else
				parent->right = cur;
		}
		return true;
	}

	bool _findR(Node* root, const T& key)
	{ 
   
		if (!root)
			return false;
		if (root->key > key)
			return _findR(root->left, key);
		else if (root->key < key)
			return _findR(root->right, key);
		return true;
	}


	bool _find(const T& key)
	{ 
   
		Node* cur = root;
		while (cur)
		{ 
   
			if (cur->key > key)
				cur = cur->left;
			else if (cur->key < key)
				cur = cur->right;
			else
				return true;
		}
		return false;
	}

	void _inorder(Node* ptr)
	{ 
   
		if (!ptr)
			return;
		_inorder(ptr->left);
		cout << ptr->key << " ";
		_inorder(ptr->right);
	}


	bool _ereaseR(Node*& root, const T& key)
	{ 
   
		if (root->key > key)
			return _ereaseR(root->left, key);
		else if (root->key < key)
			return _ereaseR(root->right, key);
		else
		{ 
   
			Node* tmp = root;
			if (!root->left)
			{ 
   
				root = root->right;
			}
			else if (!root->right)
			{ 
   
				root = root->left;
			}
			else
			{ 
   
				Node* ret = root->right, * ret_parent = root;
				while (ret->left)
				{ 
   
					ret_parent = ret;
					ret = ret->left;
				}
				swap(ret->key, root->key);
				tmp = ret;
				if (ret == root->right)
					return _ereaseR(root->right, key);   //不能用引用传递ret，因为传递ret，相当于是ret的别名，并不会修改双亲节点的孩子
				else
					return _ereaseR(ret_parent->left, key);
			}
			delete tmp;
			return true;
		}

	bool _erease(const T& key)
	{ 
   
		if (!root)
			return false;
		Node* cur = root, * parent = nullptr;
		while (cur)
		{ 
   
			parent = cur;
			if (cur->key > key)
				cur = cur->left;
			else if (cur->key < key)
				cur = cur->right;
			else
			{ 
   
				Node* tmp = cur;
				if (!cur->left)  //没有左子树
				{ 
   
					if (cur == root)
					{ 
   
						root = cur->right;
					}
					else
					{ 
   
						if (parent->left == cur)
							parent->left = cur->right;
						else
							parent->right = cur->right;
					}
				}
				else if (!cur->right)  //没有右子树
				{ 
   
					if (cur == root)
					{ 
   
						root = cur->left;
					}
					else
					{ 
   
						if (parent->left == cur)
							parent->left = cur->left;
						else
							parent->right = cur->left;
					}
				}
				else   //左右孩子都在
				{ 
   
					//左右孩子都在的情况需要替换，可以用当前需要被删除的节点的左子树上的最大值(左子树的右下角)，或者右子树的最小值(右子树的左下角)，
					//这里统一用右子树的坐下角

					Node* ret = cur->right, * ret_parent = cur;
					while (ret->left)
					{ 
   
						ret_parent = ret;
						ret = ret->left;
					}
					swap(cur->key, ret->key);
					tmp = ret;
					if (ret == ret_parent->right)    //如果满足这个条件，那么说明待删除节点cur的右孩子没有左孩子，那么直接等于cur右孩子的右孩子即可
						ret_parent->left = ret->left;
					else
						ret_parent->right = ret->right;
				}
				delete tmp;
				return true;
			}
		}
		return false;
	}

public:

	void Insert(const T& key)
	{ 
   
		_Insert(key);
	}

	void Find(const T& key)
	{ 
   
		_find(key);
	}

	void Erease(const T& key)
	{ 
   
		_ereaseR(root, key);
	}

	void Inorder()
	{ 
   
		_inorder(root);
	}

};


int main()
{ 
   
	BSTree<int> Tree;
	vector<int> ret{ 
    12,1,3,2,8,7,0,6,-1,13 };
	for (auto& e : ret)
	{ 
   
		Tree.Insert(e);
	}

	Tree.Inorder();
	cout << endl;
	for (auto it = ret.begin(); it != ret.end(); it++)
	{ 
   
		cout << *it << endl;
		Tree.Erease(*it);
	}
}

今天的文章二叉查找树算法_二叉判定树和二叉排序树分享到此就结束了，感谢您的阅读。

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/82249.html