【数据结构】二叉搜索树 - 优化遍历搜索 _ [进阶篇_复习专用]

怼烎@ 2024-04-01 09:44 150阅读 0赞

> **目录**
> 
> 1.二叉搜索树
> 
> 1.1二叉搜索树概念
> 
> 1.2二叉搜索树模板
> 
> 1.2.1二叉树的结点
> 
> 1.2.2二叉树类模板
> 
> 1.3二叉搜索树操作的实现
> 
> 1.3.1二叉搜索树的插入
> 
> 1.3.2中序遍历 
> 
> 1.3.3 二叉搜索树的查找
> 
> 1.3.4二叉搜索树的删除
> 
> 1.4二叉搜索树操作的递归实现 
> 
> 1.4.1递归实现插入操作
> 
> 1.4.2递归实现查找 
> 
> 1.4.3递归实现删除操作 
> 
> 2.二叉搜索树应用分析
> 
> 2.1 K模型
> 
> 2.2 KV模型
> 
> 3.二叉搜索树性能分析
> 
> 3.1最优情况
> 
> 3.2最差情况

## 1.二叉搜索树 ##

### 1.1二叉搜索树概念 ###

> 二叉搜索树：它或者是一棵空树，或者是具有下列性质的二叉树。
> 
>  *  若它的左子树不空，则左子树上所有结点的值均小于它根结点的值；
>  *  若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
> 
> 二叉搜索树也称**二叉查找数**(可以用于查找)或者**二叉排序树**(中序遍历出的结果是有序的)**。**
> 
> 二叉树的中序遍历: 首先遍历左子树，然后访问根结点，最后遍历右子树。

![45e1869cf6c047b480226a2196e80698.png][]

### 1.2二叉搜索树模板 ###

#### 1.2.1二叉树的结点 ####

template <class K>
    struct BTNode
    {
    	BTNode* left;//指向左子结点
    	BTNode* right;//指向右子结点
    	K _key;
    };

> 为什么使用struct，而不使用class？
> 
> class定义的类中的成员默认是私有的，在类外是不能访问的；
> 
> struct定义的类中的成员默认是共有的，在类外可以访问；访问权限问题。

#### 1.2.2二叉树类模板 ####

template <class K>
    class BSTree
    {
    	typedef BSNode<K> Node;//对类模板结点进行重命名
    public:
    	//放对外调用接口-对二叉树进行操作
    private:
    	Node* _root = nullptr;//Node指针，缺省值为nullptr
    };

### 1.3二叉搜索树操作的实现 ###

![5f8ad917d87542c9bc776341791254e3.png][]

#### 1.3.1二叉搜索树的插入 ####

先来看一下二叉搜索树的声明：

bool Insert(const K& key);

现在来解释一下为什么插入返回的是一个布尔类型：二叉搜索树中的数据是不能重复的，相同的数据无法插入，返回false；

不相同的数据插入成功，返回true。

**画图看一下插入过程：**

![5139c8683fed49ecaaf5ab5c3c0095da.png][]

**二叉搜索树插入的具体实现：**

bool Insert(const K& key)
    {
    	if (_root == nullptr)//二叉搜索树为空
    	{
    		_root = new Node(key);
    		return true;
    	}
    	//不为空
    	Node* cur = _root;
    	Node* parent = nullptr;
    	while (cur)
    	{
    		if (key > cur->_key)
    		{
    			parent = cur;
    			cur = cur->right;
    		}
    		else if (key < cur->_key)
    		{
    			parent = cur;
    			cur = cur->left;
    		}
    		else//插入的值和结点的值相同
    			return false;
    	}
    	cur = new Node(key);
    	//找到插入的位置和插入位置的parent
    	if (key > parent->_key)
    		parent->right = cur;
    	if (key < parent->_key)
    		parent->left = cur;
    	return true;
    }

> **注意：在使用new来为Node对象开辟空间时，会调用Node的构造函数，所以在BTNode中要显示写出一个有参构造。**

BTNode(const K& key)
    	:left(nullptr)
    	, right(nullptr)
    	, _key(key)
    {}

#### 1.3.2中序遍历 ####

使用中序遍历(Inorder)访问二叉搜索树中的元素：

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

这样写会有一个问题：成员函数\_Inorder的参数root在类外如何去传？有两种解决方案。

1.  对外公开一个接口GetRoot()
2.  在类内完成调用

如何在类内完成调用？在定义一个公开的Inorder去调用\_Inorder。

public:
    	void Inorder()
    	{
    		_Inorder(_root);
    	}
    private:
    	void _Inorder(Node* root)
    	{
    		if (root == nullptr)
    			return;
    		_Inorder(root->left);
    		cout << root->_key << " ";
    		_Inorder(root->right);
    	}

结合插入和中序遍历的接口，下面进行一下测试：

void TestBSTree1()
    {
    	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13, 3, 1 };
    	BSTree<int> t;
    	for (auto& e : a)
    	{
    		t.Insert(e);
    	}
    	t.Inorder();
    }

在主函数中调用TestBSTree1()，看能不能得到我们想要的结果：

> ![977373f071c24bf6ac772081283d7e7c.png][]
> 
> 使用中序遍历打印出的结果是升序的，而且重复的数据也是无法插入的，直接反映了二叉搜索树的两个特征：**升序+去重。**

#### 1.3.3 二叉搜索树的查找 ####

查找和插入的遍历是相似的，不过当遍历的指针为空时，代表没有找到，找到的话会直接返回。

bool Find(const K& key)
    {
    	Node* cur = _root;
    	while (cur)
    	{
    		if (key > cur->_key)
    		{
    			cur = cur->right;
    		}
    		else if (key < cur->_key)
    		{
    			cur = cur->left;
    		}
    		else//找到了
    			return true;
    	}
    	return false;
    }

void TestBSTree1()
    {
    	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13, 3, 1 };
    	BSTree<int> t;
    	for (auto& e : a)
    	{
    		t.Insert(e);
    	}
    	t.Inorder();
    	cout << t.Find(10) << endl;
    	cout << t.Find(100) << endl;
    }

> ![a68f8a2370dc4ac788546955cba3bb69.png][]
> 
> 直接使用cout进行打印时：结果为true -> 1；结果为false -> 0。

#### 1.3.4二叉搜索树的删除 ####

二叉搜索树的删除有点复杂，需要考虑多种场景和解决办法。

二叉搜索树删除的返回值还是一个布尔类型：删除成功返回true，删除的值不存在返回false。

> 二叉树的删除首先需要确定这个值是否存在，如果存在再进行删除，如果不存在直接返回fasle。

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
    		{
    			//找到了，进行删除
    		}
    	}
    	return false;//没找到，返回false
    }

找到之后进行删除又可以分为三种情况：

**1.被删除结点有右结点，没有左结点**

![16f94e4fa6dd4a12bdadfafb29741a10.png][]

if (cur == _root)
    {
    	_root = cur->_right;
    }
    else
    {
    	//判断被删除结点是父结点的左还是右
    	if (cur == parent->_left)
    	{
    		parent->_left = cur->_right;
    	}
    	else
    	{
    		parent->_right = cur->_right;
    	}
    }
    
    delete cur;
    cur = nullptr;

**2.被删除结点有左结点，没有右结点(没有子结点的情况走1.2的其中一个)**

![8f1880698c1541b6ad0bb00edbc629a1.png][]

if (_root == cur)
    {
    	_root = cur->_left;
    }
    else
    {
    	if (cur == parent->_left)
    	{
    		parent->_left = cur->_left;
    	}
    	else
    	{
    		parent->_right = cur->_left;
    	}
    }
    
    delete cur;
    cur = nullptr;

**3.被删除结点既有左结点，又有右结点**

> **替换法：找到左子树的最大值或者右子树的最小值和删除的值进行交换，然后再把要删除值的结点删除。**

![876fd45d76b5426e9892f3451fb69463.png][]

需要注意的是：删除的的max或者min结点可能还有子结点，还要进一步进行判断。

Node* minParent = cur;
    Node* min = cur->_right;
    while (min->_left)
    {
    	minParent = min;
    	min = min->_left;
    }
    
    swap(cur->_key, min->_key);
    if (minParent->_left == min)
    minParent->_left = min->_right;
    else
    minParent->_right = min->_right;
    
    delete min;
    min = nullptr;
    return true;

**完整代码实现：**

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 (cur == parent->_left)
    						parent->_left = cur->_right;
    					else
    						parent->_right = cur->_right;
    				}
    
    				delete cur;
    				cur = nullptr;
    			}
    			else if (cur->_right == nullptr)
    			{
    				if (_root == cur)
    					_root = cur->_left;
    				else
    				{
    					if (cur == parent->_left)
    						parent->_left = cur->_left;
    					else
    						parent->_right = cur->_left;
    				}
    
    				delete cur;
    				cur = nullptr;
    			}
    			else
    			{
    				// 替换法删除 -- 
    				Node* minParent = cur;
    				Node* min = cur->_right;
    				while (min->_left)
    				{
    					minParent = min;
    					min = min->_left;
    				}
    
    				swap(cur->_key, min->_key);
    				if (minParent->_left == min)
    					minParent->_left = min->_right;
    				else
    					minParent->_right = min->_right;
    
    				delete min;
    				min = nullptr;
    				return true;
    			}
    		}
    		return true;
    	}
    	return false;
    }

测试一下是否正确：

void TestBSTree1()
    {
    	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13, 3, 1 };
    	BSTree<int> t;
    	for (auto& e : a)
    	{
    		t.Insert(e);
    	}
    	t.Inorder();
    
    	t.Erase(3);
    	t.Inorder();
    
    	t.Erase(8);
    	t.Inorder();
    
    	for (auto& e : a)
    	{
    		t.Erase(e);
    	}
    	t.Inorder();
    }

> ![fc23c814f68e4c3ea5e5e9434e39f51c.png][]
> 
> 通过运行结果可以看到：一个一个删除数据没有问题，而且全部删除也是没有问题的。

### 1.4二叉搜索树操作的递归实现 ###

递归的时候同样需要传入根节点，而且根节点并不能给缺省值，所以需要在类内实现一个公有的接口来调用类内的Node\* \_root。

#### 1.4.1递归实现插入操作 ####

public:
    	bool FindR(const K& key)
    	{
    		return _FindR(_root, key);
    	}
    private:
    	bool _InsertR(Node*& root, const K& key)
    	{
    		if (root == nullptr)
    		{
    			//插入
    			root = new Node(key);
    			return true;
    		}
    		if (key > root->_key)
    		{
    			return _InsertR(root->right, key);
    		}
    		else if (key < root->_key)
    		{
    			return _InsertR(root->left, key);
    		}
    		else
    			return false;
    	}

#### 1.4.2递归实现查找 ####

public:
    	bool FindR(const K& key)
    	{
    		return _FindR(_root, key);
    	}
    private:
    	bool _FindR(Node* root, const K& key)
    	{
    		if (root == nullptr)
    			return false;
    		if (key > root->_key)
    			return _FindR(root->right, key);
    		else if (key < root->_key)
    			return _FindR(root->left, key);
    		else
    			return true;
    	}

#### 1.4.3递归实现删除操作 ####

public:
    	bool EraseR(const K& key)
    	{
    		return _EraseR(_root, key);
    	}
    private:
    	bool _EraseR(Node*& root, const K& key)
    	{
    		if (root == nullptr)
    			return false;
    
    		if (key > root->_key)
    			return _EraseR(root->right, key);
    		else if (root->_key > key)
    			return _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* min = root->right;
    				while (min->left)
    				{
    					min = min->left;
    				}
    				swap(root->_key, min->_key);
    				return _EraseR(root->right, key);
    			}
    
    			delete del;
    			return true;
    		}
    	}

## 2.二叉搜索树应用分析 ##

### 2.1 K模型 ###

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

举个栗子：**给一个单词word，判断该单词是否拼写正确**，具体的操作方式如下：

1.  以词库中所有单词集合中的每个单词作为key，构建一颗二叉搜索树
2.  在二叉搜索树中检索该单词是否存在，存在就是拼写正确，不存在就是拼写错误

### 2.2 KV模型 ###

> KV模型：每一个关键码key，都有与之对应的值value，也就是<key, value>的键值对。

举栗：**英汉词典(英文和中文的对应关系)**

*  通过英文可以快速的找到对应的中文
 *  统计单词出现的次数，通过<word，count>键值对的对应关系来找到count

## 3.二叉搜索树性能分析 ##

**插入和删除操作都必须先查找，而查找在不同的情况下效率是不同的，最多查找高度次。(不同情况下高度不同)**

### 3.1最优情况 ###

**二叉搜索树为完全二叉树(或者接近完全二叉树)，次数为：longN。**

![85d924f9954a41f8876294ca0382353e.png][]

### 3.2最差情况 ###

**二叉搜索树为单支树，次数为：N。**

![1365cd8515d246fb83b3ba6c01c71db5.png][]

**二叉搜索树的内容到这里就完结了，最后在这里祝大家10 24程序节快乐，希望我们的程序写的越来越好，编程能力越来越强。**

[45e1869cf6c047b480226a2196e80698.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/bdc33faf6ef14ab1bcc9b41365a2d0da.png
[5f8ad917d87542c9bc776341791254e3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/189194e5f537408ab815519bf78ed1fa.png
[5139c8683fed49ecaaf5ab5c3c0095da.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/f53e042110d040758cd0ef49737cd77a.png
[977373f071c24bf6ac772081283d7e7c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/e2d0b25347aa49f481784a9396144cf2.png
[a68f8a2370dc4ac788546955cba3bb69.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/1b71d209ce0943699c09de740565a91c.png
[16f94e4fa6dd4a12bdadfafb29741a10.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/ed1af069bcd4438188fd7e4f4f09eba6.png
[8f1880698c1541b6ad0bb00edbc629a1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/d0496300398249b09a719eb6e3e710d0.png
[876fd45d76b5426e9892f3451fb69463.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/90b23dfffe0644158c6e19d6f8963a30.png
[fc23c814f68e4c3ea5e5e9434e39f51c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/61f8da80d454479f9d106e89810067aa.png
[85d924f9954a41f8876294ca0382353e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/e2f8c47684214fd691ba439f110fd44a.png
[1365cd8515d246fb83b3ba6c01c71db5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/7b7dc1627a6f40d188adafee7c2d4b35.png