admin管理员组

文章数量:1794759

【C++的剃刀】我不允许你还不会二叉搜索树BST

二叉搜索树概念

二叉搜索树又称二叉排序树，它有可能是一棵空树，有可能是具有以下性质的二叉树：

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

二叉搜索树操作

当一颗二叉搜索树具有以下结点时，其形态是这样的：

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

​

二叉搜索树的查找

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

代码语言：javascript代码运行次数：0运行复制
/*查找元素key*/
bool find(Node* root, int key)
{
	while (root != NULL)
	{
		if (key == root->data)
			return true;
		else if (key < root->data)
			root = root->left;
		else
			root = root->right;
	}
	return false;
}

二叉搜索树的插入

插入的具体过程如下： a. 树为空，则直接新增节点，赋值给root指针 b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

代码语言：javascript代码运行次数：0运行复制
void insert(int key)
{
	//定义一个临时指针 用于移动
	Node* temp = root;//方便移动 以及 跳出循环
	Node* prev = NULL;//定位到待插入位置的前一个结点
	while (temp != NULL)
	{
		prev = temp;
		if (key < temp->data)
		{
			temp = temp->left;
		}
		else if(key > temp->data)
		{
			temp = temp->right;
		}
		else
		{
			return;
		}
	}
 
	if (key < prev->data)
	{
		prev->left = (Node*)malloc(sizeof(Node));
		prev->left->data = key;
		prev->left->left = NULL;
		prev->left->right = NULL;
	}
	else
	{
		prev->right = (Node*)malloc(sizeof(Node));
		prev->right->data = key;
		prev->right->left = NULL;
		prev->right->right = NULL;
	}
}

二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况： a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点

代码语言：javascript代码运行次数：0运行复制
int delete_node(Node* node, int key)
{
	if (node == NULL)
	{
		return -1;
	}
	else
	{
		if (node->data == key)
		{
			//当我执行删除操作 需要先定位到删除结点的前一个结点（父节点）
			Node* tempNode = prev_node(root, node, key);
			Node* temp = NULL;
			
			//如果右子树为空，只需要重新连接结点（包含叶子结点），直接删除
			if (node->right == NULL)
			{
				temp = node;
				node = node->left;
				/*判断待删除结点是前一个结点的左边还是右边*/
				if (tempNode->left->data == temp->data)
				{
					Node* free_node = temp;
					tempNode->left = node;
					free(free_node);
					free_node = NULL;
				}
				else
				{
					Node* free_node = temp;
					tempNode->right = node;
					free(free_node);
					free_node = NULL;
				}
			}
			else if (node->left == NULL)
			{
				temp = node;
				node = node->right;
				if (tempNode->left->data == temp->data)
				{
					Node* free_node = temp;
					tempNode->left = node;
					free(free_node);
					free_node = NULL;
				}
				else
				{
					Node* free_node = temp;/
					tempNode->right = node;
					free(free_node);
					free_node = NULL;
				}
			}
			else//左右子树都不为空
			{
				temp = node;
				/*往左子树 找最大值*/
				Node* left_max = node;//找最大值的临时指针
				left_max = left_max->left;//先到左孩子结点
				while (left_max->right != NULL) 
				{
					temp = left_max;
					left_max = left_max->right;
				}
				node->data = left_max->data;
				if (temp != node)
				{
					temp->right = left_max->left;
					free(left_max);
					left_max = NULL;
				}
				else
				{
					temp->left = left_max->left;
					free(left_max);
					left_max = NULL;
				}
			}
			
		}
		else if(key < node->data)
		{
			delete_node(node->left, key);
		}
		else if (key > node->data)
		{
			delete_node(node->right, key);
		}
	}
}

二叉搜索树的应用

1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到 的值。 比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

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

2. KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方 式在现实生活中非常常见：

比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英 文单词与其对应的中文<word, chinese>就构成一种键值对。 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出 现次数就是<word, count>就构成一种键值对。

代码语言：javascript代码运行次数：0运行复制
#pragma once

// 改造二叉搜索树为KV结构
template<class K, class V>
struct BSTNode
{
	BSTNode(const K& key = K(), const V& value = V())
		: _pLeft(nullptr), _pRight(nullptr), _key(key), _Value(value)
	{}
	BSTNode<T>* _pLeft;
	BSTNode<T>* _pRight;
	K _key;
	V _value
};
template<class K, class V>
class BSTree
{
	typedef BSTNode<K, V> Node;
	typedef Node* PNode;
public:
	BSTree() : _pRoot(nullptr) {}
	PNode Find(const K& key);
	bool Insert(const K& key, const V& value)
		bool Erase(const K& key)
private:
	PNode _pRoot;
};
void TestBSTree3()
{
	// 输入单词，查找单词对应的中文翻译
	BSTree<string, string> dict;
	dict.Insert("string", "字符串");
	dict.Insert("tree", "树");
	dict.Insert("left", "左边、剩余");
	dict.Insert("right", "右边");
	dict.Insert("sort", "排序");
	// 插入词库中所有单词
	string str;
	while (cin >> str)
	{
		BSTreeNode<string, string>* ret = dict.Find(str);
		if (ret == nullptr)
		{
			cout << "单词拼写错误，词库中没有这个单词:" << str << endl;
		}
		else
		{
			cout << str << "中文翻译:" << ret->_value << endl;
		}
	}
}
void TestBSTree4()
{
	// 统计水果出现的次数
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
   "苹果", "香蕉", "苹果", "香蕉" };
	BSTree<string, int> countTree;
	for (const auto& str : arr)
	{
		// 先查找水果在不在搜索树中
		// 1、不在，说明水果第一次出现，则插入<水果, 1>
		// 2、在，则查找到的节点中水果对应的次数++
		//BSTreeNode<string, int>* ret = countTree.Find(str);
		auto ret = countTree.Find(str);
		if (ret == NULL)
		{
			countTree.Insert(str, 1);
		}
		else
		{
			ret->_value++;
		}
	}
	countTree.InOrder();
}

二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二 叉搜索树的深度的函数，即结点越深，则比较次数越多。 但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

最优情况下，二叉搜索树为完全二叉树 ( 或者接近完全二叉树 )，其平均比较次数为：

最差情况下，二叉搜索树退化为单支树 ( 或者类似单支 ) ，其平均比较次数为：

学习编程就得循环渐进，扎实基础，勿在浮沙筑高台

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-07-25，如有侵权请联系 cloudcommunity@tencent 删除二叉树key苹果搜索c++

本文标签： C的剃刀我不允许你还不会二叉搜索树BST

版权声明：本文标题：【C++的剃刀】我不允许你还不会二叉搜索树BST 内容由林淑君副主任自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.xiehuijuan.com/baike/1754782455a1706362.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。