二叉树进阶(搜索二叉树)

这篇具有很好参考价值的文章主要介绍了二叉树进阶(搜索二叉树)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

引言 

1.二叉搜索树的模拟实现

1.1  链式二叉树的定义

1.2 二叉搜索树的模拟实现 

1.2.1 二叉搜索树的结点类

1.2.2 二叉搜索树类的构造与中序遍历实现

1.2.3 增

1.非递归实现

2.非递归实现

1.2.4 查

1.非递归实现

2.递归实现 

1.2.5 删

1.非递归实现

(1)情况分析

(2)解决方案 

(3)领养代码实现 

(4)替代法代码实现 

2.递归实现

1.2.6  整体代码展示

2.二叉搜索树的应用

2.1 key模型

2.2 key-value(kv)模型

3.二叉搜索树的相关oj题

1. 二叉树创建字符串

2. 二叉树的分层遍历1

3. 二叉树的分层遍历2

4. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先

5. 二叉树搜索树转换成排序双向链表

6. 根据一棵树的前序遍历与中序遍历构造二叉树

7. 根据一棵树的中序遍历与后序遍历构造二叉树


引言 

在之前文章中,我们用C语言实现了链式二叉树,在该节,我们将会通过C++的方式,对二叉树进

一步研究,尝试手动模拟实现二叉搜索树,为接下来学习map,set打下相应的基础

1.二叉搜索树的模拟实现

1.1  链式二叉树的定义

在链式二叉树的一节中,我们曾经提到过

由于二叉树的形状是不确定的,甚至可以全部倾向一边,构成我们熟悉的单链表.

因此,从某种意义上来说,二叉树的增删查改并没有意义,除非有着特殊结构的限定

二叉树进阶(搜索二叉树),C++,算法

所以,这节主要研究的就是二叉树中一种特殊的结构——搜索二叉树(如图所示)

搜索二叉树的特点:

1. 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;

2. 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;

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

1.2 二叉搜索树的模拟实现 

1.2.1 二叉搜索树的结点类

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

	BSTreeNode(const K& key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}
};

构造函数,直接将结点左右指针都赋为空,同时_key置为用户给的key值 

1.2.2 二叉搜索树类的构造与中序遍历实现

二叉搜索树类的成员就一个——根

二叉树进阶(搜索二叉树),C++,算法

为了接下来代码书写简便,和前面模拟实现一样,对二叉搜索树类型重命名

typedef BSTreeNode<K> Node;

二叉搜索树其实还有一个非常有趣的特征,中序遍历二叉搜索树,得到的会是一个有序的序列

因此,我们可以通过在类里面实现中序遍历,来迅速简单验证我们构造的二叉搜索树是否成功

调用中序遍历Inorder,需要我们传根,但是根是我们类里面的私有成员

在类外部,是无法直接访问的,除非我们在类里面加一个Getroot的成员函数

不过这样就会显得代码有些冗余,所以我们会换一种做法,通常是将中序遍历进行嵌套实现

这样用户调用的时候,不需要传根,同时在类里面,我们也可以直接访问根这个私有成员

//中序遍历
  	void Inorder()
	{
		_Inorder(_root);
		cout << endl;
	}

    void _Inorder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_Inorder(root->_left);
		cout << root->_key << " ";
		_Inorder(root->_right);
	}

 PS:

这里不能采用给缺省值来解决问题

void _Inorder(Node* root = _root) ❌

1.缺省值必须是全局变量或者常量,而这里的_root显然不是

2.函数成员变量的访问,需要this指针,它是一个临时形参,只能在函数内部访问,现在连函数内部都还没进去,怎么可以通过this指针来访问函数成员呢?

1.2.3 增

1.非递归实现

我们第一个实现的是插入函数,这样我们就可以先构造出我们的二叉搜索树,并简单用中序遍历,

验证实现是否成功,这样再进行后续的模拟实现

二叉搜索树的插入(增)

a. 树为空,则直接新增节点,赋值给root指针

b. 树不空,按二叉搜索树性质查找插入位置,插入新节点

树为空,这没有什么好解释的,new一个结点,对应结点指针指向_root即可

但假如树不为空,就必须满足二叉搜索树的性质,先找到结点的正确位置,再进行插入

找到结点位置没有什么好解释的,就按照新节点的val值和现在当前节点的val作比较,如果比它

大,则向右移动插入,否则,就向左移动插入

同时为了方便插入,我们还需要随时记录插入结点的父节点位置指针

比如下面这张图,要插入16,我们移动cur的同时,还需要记录它的parent,这样当cur为空,即找

到对应的正确位置,就及时将parent指向它

二叉树进阶(搜索二叉树),C++,算法

PS:cur可能是parent的左孩子也可能是右孩子,所以在调整指向的时候,还需要进一步判断

	bool insert(const K& key)
	{
		//如果是第一个元素,直接就将它作为二叉树的根
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}
		//如果不是就考虑插入元素
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			//如果当前结点的值小于Key,往右移动
			if (cur->_key < key)
			{   
				parent = cur;
				cur = cur-> _right;
			}
			//如果当前结点的值大于Key,往左移动
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			//出现相同元素,直接报错
			else
			{
				return false;
			}
		}
		//找到对应正确位置,new一个节点,并且将parent指向它
		cur = new Node(key);
		if (parent->_key < key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		return true;
	}
2.非递归实现

前面我们已经讲过,如果要在类外部访问私有成员变量_root,那就需要增添Getroot成员函数

所以一般在类内部实现递归函数,我们都用嵌套实现

这里有一个技巧非常绝妙,我们注意到_InsertR函数参数中,root用的是引用传参

所以找到正确的位置,传给root,直接就是parent->left或者parent->right的别名

充分利用了函数栈帧和引用相关知识,设计得很有意思

//二叉树插入(递归版本)
	bool InsertR(const K& key)
	{
		return _InsertR(_root, key);
	}
bool _InsertR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}

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

1.2.4 查

 二叉搜索树的查找

a. 从根开始比较,查找,比根大则往右边走查找,比根小则往左边走查找

b. 最多查找高度次,走到到空,还没找到,这个值不存在。

总体思路和插入非常类似,相比而言,会比插入还要简单,相当于插入的节选代码,稍作修改,两

者甚至可以实现赋用

1.非递归实现
//二叉树查找
	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;
	}
2.递归实现 
//二叉树查找(递归版本)
	bool FindR(const K& key)
	{
		return _FindR(_root, key);
	}
bool _FindR(Node* root, const K& key)
	{
		if (root == nullptr)
			return false;
		if (root->_key == key)
			return true;

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

1.2.5 删

1.非递归实现
(1)情况分析

删除可以说是二叉搜索树模拟实现的核心,而且难度也最高

我们需要一步步进行分析

首先对于被删除的节点,我们需要考虑它的child,节点被删除,那child指向肯定就要作出调整

二叉树进阶(搜索二叉树),C++,算法

比如说删除16,那就可以直接删除即可

但是删除15,或者说删除18,就会是另外不同的情况,不可能删除15,然后把17和16两个结点都

弄丢的,所以我们需要先把不同的情况列出来,然后根据每种情况,提出不同的解决方案

总共有四种情况

列写思路也很简单,这个节点有没有孩子,无孩子,就像图中的16;有孩子的话有几个孩子?有一

个孩子,和有两个孩子是不同的情况

无孩子

a. 要删除的结点无孩子结点

有孩子(有几个孩子?)

b. 要删除的结点只有左孩子结点

c. 要删除的结点只有右孩子结点

d. 要删除的结点有左、右孩子结点 

但事实上,我们可以把a情况,放到b情况或者c情况中,用统一方法解决,所以总共可以算三种情

二叉树进阶(搜索二叉树),C++,算法

(2)解决方案 

对于第一种情况,直接删除即可,没有孩子需要处理,比如说16这个节点

对于第二,第三种情况,我们采取托孤的方式,让爷爷来带孙子,毕竟父亲被删除了,那爷爷自然

就可以空出一只手,我们让被删结点的爸爸,也就是爷爷,来照顾孙子,就可以解决只有左孩子和

右孩子的情况

比如15这个节点,我们把它删除,那它的父节点18自然会空出一只手,来领养17这个儿子

PS:

第一种情况,可以归到第二,三种情况处理,删除16,实际上就是让17领养孙子,孙子为空指针,没有差别,可以直接让17领养空结点

对于第三种情况,我们采取替代的方法,寻找被删除节点左树的最大节点或者右树的最小节点

为什么要用左树的最大节点或者右树的最小节点来替代呢?

1.因为我们要保证替代后,它仍然是一棵搜索二叉树

    左树的最大节点,或者右树的最小节点,都可以满足替代后,根大于左子树的所有结点,同时小于右子树的所有结点

2.替代后,删除原结点,可以转换为我们熟悉的前两种情况

比如说删除12,我们用它的左子树的最大结点来替代(其实就是把12这个值改成9)

然后把原来9这个结点直接释放,就实现了删除12结点的操作

9由于是从左子树里面挑出来的,所以比12右子树所有结点都要小

但又是左子树里面最大的,所以完全可以实现替代12之后,保持是一棵搜索二叉树

(类似我们也可以选择15——右树的最小结点来替代)

二叉树进阶(搜索二叉树),C++,算法

(3)领养代码实现 

现在讨论完不同情况后,我们就可以开始着手实现代码,在这期间,同样有很多需要注意的细节

首先,我们还是要找到这个要删除的结点,同样的,我们也要记录它的父亲

我们把第一种情况也放在第二种一同解决

但这里还需要注意两个点

第一,假如被删结点,没有父节点呢?也就是没有爷爷,此时就无法实现托孤了,对空指针解引用,会造成程序的崩溃

二叉树进阶(搜索二叉树),C++,算法  

第二,被删结点的父节点不是随便领养的,还需要判断被删结点原来是父节点的右孩子还是左孩子,只有空出来的手才可以领养孩子

//如果该结点没有右孩子
if (cur->_right == nullptr)
{   
	//判断cur是不是根,如果是根,则没有parent
	if (cur == _root)
	{
		_root = cur->_left;
	}
	else
	{
		//并且该结点是父节点的右孩子,则让parent的右指针领养它的左孩子
		if (parent->_right == cur)
		{
			parent->_right = cur->_left;
		}
		else
		{
			parent->_left = cur->_left;
		}
	}
	delete cur;
}

//如果该结点没有左孩子
else if (cur->_left == nullptr)
{
	//并且该结点是父节点的右孩子,则让parent的右指针领养它的右孩子
	//父亲有可能为空,因为根没有parent
	if (cur == _root)
	{
		_root = cur->_right;
	}
	else
	{
		if (parent->_right == cur)
		{
			parent->_right = cur->_right;
		}
		else
		{
			parent->_left = cur->_right;
		}
	}
	delete cur;
}
(4)替代法代码实现 

接下来,我们需要处理最复杂的第三种情况,也就是用替代法,来删除有两个孩子的结点

这里采用右树最小节点的方式来替代,把右树最小节点,记为minRight

它的父节点指针,记作pminRight

只要左子树不为空,我们就一直往左移动,毕竟一棵搜索二叉树的最小节点,一定在最左边

找到后,将它的值和被删结点互换即可

但是还是有两点需要注意

第一,右树的最小节点一定没有左孩子,否则就不是最小节点

这不意味着右树最小节点一定没有右孩子,所以删除的时候,同样需要考虑领养问题

二叉树进阶(搜索二叉树),C++,算法

比如说删除12,则15就是右子树的最小节点,删除15后,还需要考虑18和17的领养问题

第二,pminRight不能初始值赋为空,假如没有进循环找minRight,则pminRight就始终为空,则后面领养的时候,空指针解引用,会导致程序崩溃

二叉树进阶(搜索二叉树),C++,算法

//该结点有两个孩子,找左子树的最大值,或者右子树的最小值
else
{   
	//pMinRight不能赋为空,否则没有进循环,空指针解引用报错
	Node* pMinRight = cur;
	Node* MinRight = cur->_right;
	//只要左子树不为空,就一直往左移动,找右树最小节点
	while (MinRight->_left)
	{  
		pMinRight = MinRight;
		MinRight = MinRight->_left;
	}
	
	//直接赋值
	cur->_key = MinRight->_key;
	//删除相应结点,需要考虑领养问题
	//右子树的最小节点,一定没有左孩子,但无法确定是否有右孩子
	if (pMinRight->_right == MinRight)
	{
		pMinRight->_right = MinRight->_right;
	}
	else
	{
		pMinRight->_left = MinRight->_right;
	}
	delete MinRight;
}

 将上述全部代码结合起来,就是整个删除的非递归代码

//二叉树删除
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->_right == nullptr)
			{   
				//判断cur是不是根,如果是根,则没有parent
				if (cur == _root)
				{
					_root = cur->_left;
				}
				else
				{
					//并且该结点是父节点的右孩子,则让parent的右指针领养它的左孩子
					if (parent->_right == cur)
					{
						parent->_right = cur->_left;
					}
					else
					{
						parent->_left = cur->_left;
					}
				}
				delete cur;
			}
			//如果该结点没有左孩子
			else if (cur->_left == nullptr)
			{
				//并且该结点是父节点的右孩子,则让parent的右指针领养它的右孩子
				//父亲有可能为空,因为根没有parent
				if (cur == _root)
				{
					_root = cur->_right;
				}
				else
				{
					if (parent->_right == cur)
					{
						parent->_right = cur->_right;
					}
					else
					{
						parent->_left = cur->_right;
					}
				}
				delete cur;
			}
			//该结点有两个孩子,找左子树的最大值,或者右子树的最小值
			else
			{   
				//pMinRight不能赋为空,否则没有进循环,空指针解引用报错
				Node* pMinRight = cur;
				Node* MinRight = cur->_right;
				//只要左子树不为空,就一直往左移动
				while (MinRight->_left)
				{  
					pMinRight = MinRight;
					MinRight = MinRight->_left;
				}
				
				//直接赋值
				cur->_key = MinRight->_key;
				//删除相应结点,需要考虑领养问题
				//右子树的最小节点,一定没有左孩子,但无法确定是否有右孩子
				if (pMinRight->_right == MinRight)
				{
					pMinRight->_right = MinRight->_right;
				}
				else
				{
					pMinRight->_left = MinRight->_right;
				}
				delete MinRight;
			}
			return true;
		}
	}
	return false;
}
2.递归实现

递归的总体思路,和非递归其实是一致的,没有什么区别

下面代码采取的是找出左树最大节点的方式,来实现替代法

不过递归如果要用引用传值来实现,也不是一件简单的事情

在替代法实现删除的时候,假如只有一个孩子,用引用传值来实现递归,和上面其实是一样的

但是如果是替代法,引用传值起到的作用其实不大

还有很关键的一点,由于是层层函数栈帧递归,我们要采用swap,而不是直接赋值

//二叉树删除(递归版本)
bool EraseR(const K& key)
{
	return _EraseR(_root, key);
}

bool _EraseR(Node*& root, const K& key)
{   
    //假如递归到空节点,说明删除节点不存在,此时return false
	if (root == nullptr)
		return false;
    //递归删除节点
	if (root->_key < key)
	{
		return _EraseR(root->_right, key);
	}
	else if (root->_key > key)
	{
		return _EraseR(root->_left, key);
	}
	else
	{
		//找到相应的结点,并保存下来
		Node* del = root;
		//如果只有左孩子
		if (root->_right == nullptr)
		{
			root = root->_left;
		}
		//如果只有右孩子
		else if (root->_left == nullptr)
		{
			root = root->_right;
		}
		//如果有左右孩子
		else
		{
			Node* maxleft = root->_left;
			while (maxleft->_right)
			{
				maxleft = maxleft->_right;
			}

			//交换两个结点的值
			swap(root->_key, maxleft->_key);
			//再递归删除子结点
			return _EraseR(root->_left, key);
		}
		delete del;

		return true;
	}
}

1.2.6  整体代码展示

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

	BSTreeNode(const K& key)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
	{}
};
template <class K>
class BSTree
{
	typedef BSTreeNode<K> Node;
public:
	BSTree() = default;  // 强制生成默认构造
	//拷贝构造
	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)
		{
			//如果当前结点的值小于Key,往右移动
			if (cur->_key < key)
			{   
				parent = cur;
				cur = cur-> _right;
			}
			//如果当前结点的值大于Key,往左移动
			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;
	}
    //二叉树查找
	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;
	}
	//二叉树删除
	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->_right == nullptr)
				{   
					//判断cur是不是根,如果是根,则没有parent
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						//并且该结点是父节点的右孩子,则让parent的右指针领养它的左孩子
						if (parent->_right == cur)
						{
							parent->_right = cur->_left;
						}
						else
						{
							parent->_left = cur->_left;
						}
					}
					delete cur;
				}
				//如果该结点没有左孩子
				else if (cur->_left == nullptr)
				{
					//并且该结点是父节点的右孩子,则让parent的右指针领养它的右孩子
					//父亲有可能为空,因为根没有parent
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_right == cur)
						{
							parent->_right = cur->_right;
						}
						else
						{
							parent->_left = cur->_right;
						}
					}
					delete cur;
				}
				//该结点有两个孩子,找左子树的最大值,或者右子树的最小值
				else
				{   
					//pMinRight不能赋为空,否则没有进循环,空指针解引用报错
					Node* pMinRight = cur;
					Node* MinRight = cur->_right;
					//只要左子树不为空,就一直往左移动
					while (MinRight->_left)
					{  
						pMinRight = MinRight;
						MinRight = MinRight->_left;
					}
					
					//直接赋值
					cur->_key = MinRight->_key;
					//删除相应结点,需要考虑领养问题
					//右子树的最小节点,一定没有左孩子,但无法确定是否有右孩子
					if (pMinRight->_right == MinRight)
					{
						pMinRight->_right = MinRight->_right;
					}
					else
					{
						pMinRight->_left = MinRight->_right;
					}
					delete MinRight;
				}
				return true;
			}
		}
		return false;
	}
	//二叉树查找(递归版本)
	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);
	}
	//中序遍历
	void Inorder()
	{
		_Inorder(_root);
		cout << endl;
	}
protected:
	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;
	    
		Node* newRoot = new Node(root->_key);
		newRoot->_left = Copy(root->_left);
		newRoot->_right = Copy(root->_right);
		return newRoot;
	}
	void Destroy(Node*& root)
	{
		if (root == nullptr)
			return;
		Destroy(root->_left);
		Destroy(root->_right);
		delete root;

		root = nullptr;
	}
	bool _FindR(Node* root, const K& key)
	{
		if (root == nullptr)
			return false;
		if (root->_key == key)
			return true;

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

	bool _InsertR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
			return true;
		}

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

		bool _EraseR(Node*& root, const K& key)
		{
			if (root == nullptr)
				return false;
			if (root->_key < key)
			{
				return _EraseR(root->_right, key);
			}
			else if (root->_key > key)
			{
				return _EraseR(root->_left, key);
			}
			else
			{
				//找到相应的结点,并保存下来
				Node* del = root;
				//如果只有左孩子
				if (root->_right == nullptr)
				{
					root = root->_left;
				}
				//如果只有右孩子
				else if (root->_left == nullptr)
				{
					root = root->_right;
				}
				//如果有左右孩子
				else
				{
					Node* maxleft = root->_left;
					while (maxleft->_right)
					{
						maxleft = maxleft->_right;
					}
		
					//交换两个结点的值
					swap(root->_key, maxleft->_key);
					//再递归删除子结点
					return _EraseR(root->_left, key);
				}
				delete del;
		
				return true;
			}
		}

	void _Inorder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_Inorder(root->_left);
		cout << root->_key << " ";
		_Inorder(root->_right);
	}
private:
	Node* _root = nullptr;
};

2.二叉搜索树的应用

2.1 key模型

K模型即只有key作为关键码,结构中只需要存储Key即可,关键码即为需要搜索到的值

K模型在生活中其实很常见,比如门禁系统,车库系统识别车牌,检查一篇文章中单词拼写是否正

确都可能采用K模型

拿检查一篇文章中单词拼写是否正确这个例子来说,我们将词库中所有单词插入到一棵二叉搜索树

中,然后将文章中每一个单词,和这颗二叉搜索树进行比对,由于二叉搜索树的特性,能够可以迅

速确定该单词是否在这棵树里面,如果没有找到,就意味着单词拼写错误

2.2 key-value(kv)模型

每一个关键码key,都有与之对应的值Value,即键值对。该种方式在现实生活中非常常见

常见的应用,比如说中英文互译字典,或者通过电话号码+验证码来查询考试成绩

都是键-值互换的典型应用

想要实现key_value的二叉搜索树也不是难事,只要在节点中多加入一个参数value即可

其它都不需要改变,建树,找树的整个过程,依旧只和key相关

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


		BSTreeNode(const K& key, const V& value)
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
			, _value(value)
		{}
	};

	template<class K, class V>
	class BSTree
	{
		typedef BSTreeNode<K, V> Node;
	public:

		bool Insert(const K& key, const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key, value);
				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, value);
			// 链接
			if (parent->_key < key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}

			return true;
		}

		Node* 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 cur;
				}
			}

			return nullptr;
		}

		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
				{
					// 删除
					// 1、左为空
					if (cur->_left == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}

						delete cur;

					} // 2、右为空
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}

						delete cur;
					}
					else
					{
						// 找右树最小节点替代,也可以是左树最大节点替代
						Node* pminRight = cur;
						Node* minRight = cur->_right;
						while (minRight->_left)
						{
							pminRight = minRight;
							minRight = minRight->_left;
						}

						cur->_key = minRight->_key;

						if (pminRight->_left == minRight)
						{
							pminRight->_left = minRight->_right;
						}
						else
						{
							pminRight->_right = minRight->_right;
						}

						delete minRight;
					}

					return true;
				}
			}

			return false;
		}


		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}

	protected:
		void _InOrder(Node* root)
		{
			if (root == nullptr)
				return;

			_InOrder(root->_left);
			cout << root->_key << ":" << root->_value << endl;
			_InOrder(root->_right);
		}
	private:
		Node* _root = nullptr;
	};
}
void TestBSTree5()
{
	string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果",\
   "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉", "梨"};

	key_value::BSTree<string, int> countTree;
	for (auto str : arr)
	{
		//key_value::BSTreeNode<string, int>* ret = countTree.Find(str);
		auto ret = countTree.Find(str);
		if (ret == nullptr)
		{
			countTree.Insert(str, 1);
		}
		else
		{
			ret->_value++;
		}
	}

	countTree.InOrder();
}

3.二叉搜索树的相关oj题

1. 二叉树创建字符串

606. 根据二叉树创建字符串 - 力扣(LeetCode)

二叉树进阶(搜索二叉树),C++,算法

空括号有可能省略,也有可能不省略,需要根据图片分类讨论

总共有三种情况

1.左子树为空,右子树不为空,该括号不能省略

2.左子树,右子树都为空,该括号省略

3.左子树为空,右子树不为空,该括号省略

class Solution {
public:
    string tree2str(TreeNode* root) {
         if (root == nullptr)
           return "";
         
         //左子树为空,右子树不为空,该括号不能省略
         //左子树,右子树都为空,该括号省略
         //左子树为空,右子树不为空,该括号省略
         string str = to_string(root->val);
         //左子树不为空,或者左子树为空,右子树不为空,加括号
         if (root->left || root->right)
         {
             str+="(";
             str+=tree2str(root->left);
             str+=")";
         }
         //如果右子树不为空
         if(root->right)
         {
             str+="(";
             str+=tree2str(root->right);
             str+=")";
         }
         return str;
    }
};

2. 二叉树的分层遍历1

102. 二叉树的层序遍历 - 力扣(LeetCode)

二叉树进阶(搜索二叉树),C++,算法

由于C++有vector这个容器,因此二维数组实现起来非常方便

只需要创建vector<vector<int>> 类型的对象即可

同时创建一个levelSize的变量,也就是一层中有多少个节点

每次循环,除了将该层节点存入一个vector中,还将下一层的非空节点,存入栈中

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        //定义一个levelsize来确定现在出的是第几行,保证一行一行出
        queue<TreeNode*> q1;
        vector<vector<int>> vv;
        int Levelsize = 0;
        if (root)
        {
            q1.push(root);
            Levelsize = 1;
        }

        while (!q1.empty())
        {
            vector<int> v;
            while (Levelsize--)
            {
                //栈顶元素出队列
                TreeNode* front = q1.front();
                q1.pop();
                v.push_back(front->val);
                //如果该节点的左子树不为空,则把相应节点入队列
                if (front->left)
                {
                    q1.push(front->left);
                }
                //如果该节点的右子树不为空,则把相应节点入队列
                if (front->right)
                {
                    q1.push(front->right);
                }
            }
            //把对应的v压入vv中
            vv.push_back(v);
            Levelsize = q1.size();
        }
        return vv;
    }
};

3. 二叉树的分层遍历2

107. 二叉树的层序遍历 II - 力扣(LeetCode)

二叉树进阶(搜索二叉树),C++,算法

先实现层序遍历,再reverse一下即可

4. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先

236. 二叉树的最近公共祖先 - 力扣(LeetCode)

二叉树进阶(搜索二叉树),C++,算法

本道题有两种思路来解决

第一种,两个节点假如分别在左子树和右子树,则它们的根节点必定是公共节点

我们先实现一个判断节点是否在一棵树里面的函数InTree

然后直接递归即可,如果两个节点都在右子树,则公共祖先不可能在左子树;同理,假如两个节点

都在左子树,则公共祖先不可能在右子树;途中假如其中一个节点是根节点,则它就是两者的公共

祖先

class Solution {
    bool InTree(TreeNode* root, TreeNode* x)
    {
       if (root == nullptr)
         return false;
       if (root == x)
         return true;
       return InTree(root->left,x) || InTree(root->right,x);
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
       //方法一,两个节点假如分别在左子树和右子树,则它们的根节点必定是公共节点
       if (root == nullptr)
         return nullptr;
       //假如其中一个节点是根节点,则它就是两者的公共祖先
       if (root == p || root == q)
         return root;
       //p在左子树或者在右子树
       bool pInleft = InTree(root->left,p);
       bool pInright = !pInleft;

       //q在左子树或者在右子树
       bool qInleft = InTree(root->left,q);
       bool qInright = !qInleft;
       
       //如果两者都在左子树,则公共节点一定在左子树
       if (pInleft && qInleft)
          return lowestCommonAncestor(root->left,p,q);
       //如果两者都在右子树,则公共节点一定在右子树
       else if(pInright && qInright)
          return lowestCommonAncestor(root->right,p,q);
       else 
          return root;
    }
};

第一种思路虽然可以解决问题,但是时间效率上却不高

第二种思路在时间效率上就会高于第一种思路,但是实现起来却不太容易

总体思路为求出两个节点的路径,然后求两个路径的交点,该交点即为公共节点

如何求出从根节点到目标节点的路径呢?

我们采取先序遍历的方式,不管三七二十一都先把节点压入栈中,假如在某一个节点,在它的左子

树中,我们没有找到目标节点,在右子树中,也还是没找到目标节点,那该节点一定不在路径当

中,就可以把该节点直接pop掉

class Solution {
public:
    bool GetPath(TreeNode* root, stack<TreeNode*>& Path,TreeNode* x)
    {
        //只要节点不为空,就入栈
        if (root == nullptr)
            return false;
        Path.push(root);
        //假如遇到了目标节点,则剩下的就不需要再递归
        if (root == x)
          return true;
        //先序遍历
        if (GetPath(root->left,Path,x))
          return true;
        if (GetPath(root->right,Path,x))
          return true;
        //假如左子树,右子树都不存在该节点,则该节点必定不是该路径上的一点,需要pop掉
        Path.pop();
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //法二:求出两个节点的路径,然后求两个路径的交点,该交点即为公共节点
        stack<TreeNode*> pPath;
        stack<TreeNode*> qPath;
        GetPath(root,pPath,p);
        GetPath(root,qPath,q);
        //假如两者长度不一致,则先调整为一致长度
        while (pPath.size() != qPath.size())
        {
            if (pPath.size() > qPath.size())
                pPath.pop();
            else
                qPath.pop();
        }
        //现在两者同样长度,则同时出栈,直到遇到公共祖先节点
        while (pPath.top() != qPath.top())
        {
            pPath.pop();
            qPath.pop();
        }
        return pPath.top();
    }
};

5. 二叉树搜索树转换成排序双向链表

二叉搜索树与双向链表_牛客题霸_牛客网 (nowcoder.com)

二叉树进阶(搜索二叉树),C++,算法

二叉树进阶(搜索二叉树),C++,算法

这道题的难度在于它只允许直接在原树上操作,需要充分理解递归,建立函数栈帧的过程,才能

对这道题的破解有一定思路

class Solution {
public:
    void _Convert(TreeNode* cur,TreeNode*& prev)
	{
        if(cur == nullptr)
		  return;
		_Convert(cur->left,prev);
		//核心代码
		cur->left = prev;
		//只有前驱节点指针不为空,才指向cur
		if(prev){
			prev->right = cur;
		}
		prev = cur;
		_Convert(cur->right,prev);
	}
    TreeNode* Convert(TreeNode* pRootOfTree) {
        //观察双向链表,可知要采取中序遍历的方式
		//为了调节节点的指向,我们定义一个前驱指针和后驱指针
		TreeNode* prev = nullptr;
		_Convert(pRootOfTree,prev);

		//已知根节点,找双向循环链表的头节点
		TreeNode* head = pRootOfTree;
		while (head && head->left)
		{
			head = head->left;
		}
		return head;
    }
};

6. 根据一棵树的前序遍历与中序遍历构造二叉树

105. 从前序与中序遍历序列构造二叉树 - 力扣(LeetCode) 

二叉树进阶(搜索二叉树),C++,算法

利用类似快排的思想,先从前序遍历中确定根节点,再从中序遍历中找它的左子树和右子树

自下而上把它们链接起来

PS:中序遍历是左,根,右的结构,我们遍历先序遍历,是采用cur引用从前往后遍历,因此链接

的时候,也是先是左孩子链接,然后是右孩子链接 

class Solution {
public:
   TreeNode* _buildTree(vector<int>& preorder, \
       vector<int>& inorder,int& cur,int begini,int endi)
   {    
        if (begini > endi)
          return nullptr;
        TreeNode* root = new TreeNode(preorder[cur]);
        //分割出左右区间,从中序遍历序列中,找出前序遍历的根节点
        int rooti = begini;
        while (rooti <= endi)
        {
            if(preorder[cur] == inorder[rooti])
              break;
            else
              rooti++;
        }

        cur++;
        //[begini  rooti-1] rooti [rooti+1  endi]
        root->left = _buildTree(preorder,inorder,cur,begini,rooti - 1);
        root->right = _buildTree(preorder,inorder,cur,rooti+1,endi);
        return root;
   }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
       //类似快排的思想,划分子区间,再递归建树
       int cur = 0;
       return _buildTree(preorder,inorder,cur,0,inorder.size()-1);
    }
};

7. 根据一棵树的中序遍历与后序遍历构造二叉树

106. 从中序与后序遍历序列构造二叉树 - 力扣(LeetCode) 

二叉树进阶(搜索二叉树),C++,算法思路和上题一样,不过区别就在于后序遍历是左,右,根的结构,因此需要从后往前遍历,而且链

接的时候,要先右子树链接,再链接左子树文章来源地址https://www.toymoban.com/news/detail-556367.html

class Solution {
   TreeNode* _buildTree(vector<int>& inorder,\
      vector<int>& postorder,int& cur,int begini,int endi)
    {
         //如何区间长度小于1,则返回空指针
         if (begini > endi)
           return nullptr;
         //根据后序遍历序列,建节点
         TreeNode* root = new TreeNode(postorder[cur]);
         //从中序遍历序列中找到和根节点的值相同的节点
         //注意不是从头(下标0)开始找,而是从当前的区间的开始begini开始找
         int rooti = begini;
         while (rooti <= endi)
         {
             if (inorder[rooti] == postorder[cur])
               break;
             rooti++;
         }
         //更新根节点
         cur--;
         //找到后,就可以根据中序序列,将区间划分为三个部分
         //[begini,rooti - 1]rooti[rooti+1,endi]
         //要从右子树开始建树
         //因为后序遍历是左子树,右子树,根的结构,cur--得到的是右子树的根
         root->right = _buildTree(inorder, postorder,cur,rooti+1,endi);
         root->left = _buildTree(inorder, postorder,cur,begini,rooti - 1);

         return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0 || postorder.size() == 0)  return nullptr;
        //后序遍历,从后往前才是根
        int cur = postorder.size() - 1;
        return _buildTree(inorder,postorder,cur,0,inorder.size() - 1);
    }
};

到了这里,关于二叉树进阶(搜索二叉树)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包