• 二叉搜索树的实现

    目录

    1.二叉搜索树概念

    2.二叉树插入的实现 

    3. 二叉搜索树的查找

    4.二叉树的删除

     5.二叉搜索树的应用

    5.1 K模型

    5.2 KV模型

    1.二叉搜索树概念

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

    2.二叉树插入的实现 

    如何插入？

    1. 如果树为空，直接插入。
    2. 如果树不为空，则将要插入的值与二叉树中各结点的值比较，最后再插入

    例如：

     代码实现：

    先创建一个结构体存储每个结点的信息：

    1. template<class K>
    2. struct BSTreeNode
    3. {
    4. 	BSTreeNode* _left;
    5. 	BSTreeNode* _right;
    6. 	K _key;
    7.  
    8. 	BSTreeNode(const K& key)
    9. 		:_left(nullptr)
    10. 		, _right(nullptr)
    11. 		, _key(key)
    12. 	{}
    13. };
    1. template<class K>
    2. class BSTree
    3. {
    4.  typedef BSTreeNode Node;
    5. public:
    6.      bool _InsertR(const K& key)
    7.    {
    8. 	  return _InsertR(_root, key);
    9.    }
    10.  
    11. private：
    12.   	bool _InsertR(Node*& root, const K& key)
    13. 	{
    14. 		if (root == nullptr)
    15. 		{
    16. 			root = new Node(key);
    17. 			return true;
    18. 		}
    19. 		if (key > root->_key)
    20. 		{
    21. 			return _InsertR(root->_right, key);
    22. 		}
    23. 		else if (key < root->_key)
    24. 		{
    25. 			return _InsertR(root->_left, key);
    26. 		}
    27. 		else//不允许存在相同的值
    28. 			return false;
    29. 	}
    30. }
    root是父亲结点的左右指针的引用，修改root也就是修改父亲结点的左右指针，

    3. 二叉搜索树的查找 

    1.  
    2.   bool _FindR(Node* root, const K& key)
    3. 	{
    4. 		
    5. 		if (root == nullptr)
    6. 			return false;
    7.  
    8. 		if (root->_key < key)
    9. 		{
    10. 			return _FindR(root->_right, key);
    11. 		}
    12. 		else if (root->_key > key)
    13. 		{
    14. 			return _FindR(root->_left, key);
    15. 		}
    16. 		else
    17. 		{
    18. 			return true;
    19. 		}
    20. 	}

    4.二叉树的删除

    二叉树的删除可分为两种情况。

    1. 1.要删除的结点只有一个孩子或无孩子。
    2. 2.要删除的结点有两个孩子。

    例如：

    1.  第一种情况：
    2.     1.删除4；
    3.     2.删除10；
    4.   第二种情况：
    5.     1.删除3；在它的右子树中寻找中序下的第一个结点(关键码最小，也就是最左结点)，用它的值填补到被删除 
    6.              节点中，再来处理该结点的删除问题--替换法删除
    1.    bool _EraseR(Node*& root, const K& key)//root是父亲结点左右指针的引用
    2. 	{
    3. 		if (root == nullptr)
    4. 			return false;
    5.  
    6. 		if (root->_key < key)
    7. 		{
    8. 			return _EraseR(root->_right, key);
    9. 		}
    10. 		else if (root->_key > key)
    11. 		{
    12. 			return _EraseR(root->_left, key);
    13. 		}
    14.        ​
    15.        else//先找到要删除的结点
    16. 		{
    17. 			Node* del = root;
    18. 			if (root->_left == nullptr)
    19. 			{
    20. 				root = root->_right;
    21. 			}
    22. 			else if (root->_right == nullptr)
    23. 			{
    24. 				root = root->_left;
    25. 			}
    26. 			else
    27. 			{
    28. 				Node* minRight = root->_right;//找到被删删除结点的右孩子,minRight
    29. 				while (minRight->_left)//以minRight为根，找到最左的孩子。
    30. 				{
    31. 					minRight = minRight->_left;
    32. 				}
    33.  
    34. 				swap(root->_key, minRight->_key);//将被删出的结点与最左孩子值替换。
    35. 				return _EraseR(root->_right, key);//此时被删除的结点在之前最左孩子的位置，它 
    36.                                                      无左孩子，转换成了第一种情况对其删除。
    37. 			}
    38. 			delete del;
    39. 			return true;
    40. 		}
    41. 		
    42. 	}

     画图分析：

     完整代码：

    1. template<class K>
    2. struct BSTreeNode
    3. {
    4. 	BSTreeNode* _left;
    5. 	BSTreeNode* _right;
    6. 	K _key;
    7.  
    8. 	BSTreeNode(const K& key)
    9. 		:_left(nullptr)
    10. 		, _right(nullptr)
    11. 		, _key(key)
    12. 	{}
    13. };
    14.  
    15. template<class K>
    16. class BSTree
    17. {
    18. 	typedef BSTreeNode Node;
    19.  
    20. private:
    21. 	void DestoryTree(Node* root)
    22. 	{
    23. 		if (root == nullptr)
    24. 			return;
    25.  
    26. 		DestoryTree(root->_left);
    27. 		DestoryTree(root->_right);
    28. 		delete root;
    29. 	}
    30.  
    31. 	Node* CopyTree(Node* root)
    32. 	{
    33. 		if (root == nullptr)
    34. 			return nullptr;
    35.  
    36. 		Node* copyNode = new Node(root->_key);
    37. 		copyNode->_left = CopyTree(root->_left);
    38. 		copyNode->_right = CopyTree(root->_right);
    39.  
    40. 		return copyNode;
    41. 	}
    42. public:
    43. 	// 强制编译器自己生成构造，C++11支持
    44. 	BSTree() = default;
    45. 	BSTree(const BSTree& t)//写了拷贝构造，不会默认生成构造函数
    46. 	{
    47. 		_root = CopyTree(t._root);
    48. 	}
    49.  
    50. 	BSTree& operator=(BSTree t)
    51. 	{
    52. 		swap(_root, t._root);
    53. 		return *this;
    54. 	}
    55.  
    56. 	~BSTree()
    57. 	{
    58. 		DestoryTree(_root);
    59. 		_root = nullptr;
    60. 	}
    61. 	
    62.  
    63.     bool _FindR(const K& key)
    64.   {
    65.  	 return _FindR(_root, key);
    66.   }
    67.   bool _InsertR(const K& key)
    68.   {
    69. 	 return _InsertR(_root, key);
    70.   }
    71.   bool _EraseR(const K& key)
    72.   {
    73.  	 return _EraseR(_root, key);
    74.   }
    75.  
    76.   void InOrder()
    77.   {
    78.      _InOrder(_root);
    79.   }
    80.  
    81. private:
    82. 	bool _EraseR(Node*& root, const K& key)
    83. 	{
    84. 		if (root == nullptr)
    85. 			return false;
    86.  
    87. 		if (root->_key < key)
    88. 		{
    89. 			return _EraseR(root->_right, key);
    90. 		}
    91. 		else if (root->_key > key)
    92. 		{
    93. 			return _EraseR(root->_left, key);
    94. 		}
    95. 		else
    96. 		{
    97. 			Node* del = root;
    98. 			if (root->_left == nullptr)
    99. 			{
    100. 				root = root->_right;
    101. 			}
    102. 			else if (root->_right == nullptr)
    103. 			{
    104. 				root = root->_left;
    105. 			}
    106. 			else
    107. 			{
    108. 				Node* minRight = root->_right;
    109. 				while (minRight->_left)
    110. 				{
    111. 					minRight = minRight->_left;
    112. 				}
    113.  
    114. 				swap(root->_key, minRight->_key);
    115. 				return _EraseR(root->_right, key);
    116. 			}
    117.  
    118. 			delete del;
    119. 			return true;
    120. 		}
    121.  
    122. 		
    123. 	}
    124. 	bool _InsertR(Node*& root, const K& key)
    125. 	{
    126. 		if (root == nullptr)
    127. 		{
    128. 			root = new Node(key);
    129. 			return true;
    130. 		}
    131. 		if (key > root->_key)
    132. 		{
    133. 			return _InsertR(root->_right, key);
    134. 		}
    135. 		else if (key < root->_key)
    136. 		{
    137. 			return _InsertR(root->_left, key);
    138. 		}
    139. 		else
    140. 			return false;
    141. 		
    142. 	}
    143. 	bool _FindR(Node* root, const K& key)
    144. 	{
    145. 		
    146. 		if (root == nullptr)
    147. 			return false;
    148.  
    149. 		if (root->_key < key)
    150. 		{
    151. 			return _FindR(root->_right, key);
    152. 		}
    153. 		else if (root->_key > key)
    154. 		{
    155. 			return _FindR(root->_left, key);
    156. 		}
    157. 		else
    158. 		{
    159. 			return true;
    160. 		}
    161. 	}
    162. 	void _InOrder(Node* root)
    163. 	{
    164. 		if (root == nullptr)
    165. 			return;
    166.  
    167. 		_InOrder(root->_left);
    168. 		cout << root->_key << " ";
    169. 		_InOrder(root->_right);
    170. 	}
    171. private:
    172. 	Node* _root = nullptr;
    173. };

     5.二叉搜索树的应用

    5.1 K模型

    K 模型即只有 key 作为关键码，结构中只需要存储 Key 即可，关键码即为需要搜索到 值 。
    比如： 给一个单词 word ，判断该单词是否拼写正确 ，具体方式如下：
    以词库中所有单词集合中的每个单词作为 key ，构建一棵二叉搜索树
    在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误

    5.2 KV模型

    每一个关键码 key ，都有与之对应的值 Value ，即 的键值对 。
    比如：
    英汉词典就是英文与中文的对应关系 ，通过英文可以快速找到与其对应的中文，英
    文单词与其对应的中文 就构成一种键值对；
    或者统计单词等的次数，若存在，则把value的值+1；
    对上面代码进行改进，来运用KV模型。
    下面展示需要更改的部分 
    1. template<class K, class V>
    2. struct BSTreeNode
    3. {
    4. 	BSTreeNode* _left;
    5. 	BSTreeNode* _right;
    6.  
    7. 	const K _key;
    8. 	V _value;
    9.  
    10. 	BSTreeNode(const K& key, const V& value)
    11. 		:_left(nullptr)
    12. 		, _right(nullptr)
    13. 		, _key(key)
    14. 		, _value(value)
    15. 	{}
    16. };
    1. template<class K, class V>
    2. class BSTree
    3. {
    4. 	typedef BSTreeNode Node;
    5. public:
    6.  
    7. 	void InOrder()
    8. 	{
    9. 		_InOrder(_root);
    10. 		cout << endl;
    11. 	}
    12.  
    13. 	Node* FindR(const K& key)//返回结点的指针，可对结点内容进行修改
    14. 	{
    15. 		return _FindR(_root, key);
    16. 	}
    17.  
    18. 	bool InsertR(const K& key, const V& value)
    19. 	{
    20. 		return _InsertR(_root, key, value);
    21. 	}
    22.  
    23.  
    24. private:
    25.  
    26.  
    27. 	bool _InsertR(Node*& root, const K& key, const V& value)
    28. 	{
    29. 		if (root == nullptr)
    30. 		{
    31. 			root = new Node(key, value);
    32. 			return true;
    33. 		}
    34.  
    35. 		if (root->_key < key)
    36. 			return _InsertR(root->_right, key, value);
    37. 		else if (root->_key > key)
    38. 			return _InsertR(root->_left, key, value);
    39. 		else
    40. 			return false;
    41. 	}
    42.  
    43. 	Node* _FindR(Node* root, const K& key)
    44. 	{
    45. 		if (root == nullptr)
    46. 			return nullptr;
    47.  
    48. 		if (root->_key < key)
    49. 		{
    50. 			return _FindR(root->_right, key);
    51. 		}
    52. 		else if (root->_key > key)
    53. 		{
    54. 			return _FindR(root->_left, key);
    55. 		}
    56. 		else
    57. 		{
    58. 			return root;
    59. 		}
    60. 	}
    61. 	void _InOrder(Node* root)
    62. 	{
    63. 		if (root == nullptr)
    64. 			return;
    65.  
    66. 		_InOrder(root->_left);
    67. 		cout << root->_key << ":" << root->_value << endl;
    68. 		_InOrder(root->_right);
    69. 	}
    70. private:
    71. 	Node* _root = nullptr;
    72. };

    例如：

    1. void test2()
    2. {
    3. 	string arr[] = { "香蕉","苹果","梨","桃子","梨","香蕉","黄瓜" };
    4. 		BSTree<string, int> p;
    5. 	for (auto ch : arr)
    6. 	{
    7. 		auto ret = p.FindR(ch);
    8. 		if (ret==nullptr)
    9. 		{
    10. 			p.InsertR(ch, 1);
    11. 		}
    12. 		else
    13. 		{
    14. 			ret->_value++;
    15. 		}
    16. 	}
    17. 	p.InOrder();
    18. }
    19. int main()
    20. {
    21. 	test2();
    22. 	return 0;
    23. }

    结果：

    1. 黄瓜:1
    2. 梨:2
    3. 苹果:1
    4. 桃子:1
    5. 香蕉:2

  • 相关阅读:
    学习java第一百一十三天
    实验五 模块、包和库
    从最初的月薪 23K 涨到了年薪65W，真像做梦一样……
    Javaer 面试必背系列！超高频八股之三色标记法
    PTA C 1050 螺旋矩阵（思路与优化）
    卧兔观察：决心有了，就让拼多多飞一会儿吧
    人工智能轨道交通行业周刊-第15期（2022.9.19-9.25）
    golang的切片使用总结一
    【python】py文件全自动打包成spec文件
    安卓APP（1）——安卓工程构建和第一APP运行
  • 原文地址：https://blog.csdn.net/m0_64397669/article/details/126081453