• 数据结构 六 理解二叉搜索树的实现

    数据结构就是定义出某种结构：像数组结构、链表结构、树形结构等，实现数据结构就是我们主动去管理增删查改的实现函数

    二叉搜索树的概念

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

    非空左子树上所有节点的值都小于根节点的值，右子树上所有节点的值都大于根节点的值

    二叉搜索树的定义

    1. template<class K>//搜索二叉树
    2. struct BSTreeNode
    3. {
    4.   BSTreeNode* _left;//左孩子指针
    5.   BSTreeNode* _right;//右孩子指针
    6.   K _key;//节点数据值
    7.   //构造函数
    8.   BSTreeNode(const K& key):_left(nullptr),_right(nullptr),_key(key)
    9.   {}
    10. };

    先来了解一下文件BinnarySearchTree.h中的接口

    1. template<class K>
    2. class BSTree
    3. {
    4. 	typedef BSTreeNode Node;	//重命名上面的定义 
    5. public
    6.     //递归查找
    7. 	bool FindR(const K& key)
    8. 	{
    9. 		return _FindR(_root, key);
    10. 	}
    11. 	//递归插入
    12. 	bool InsertR(const K& key)
    13. 	{
    14. 		return _InsertR(_root, key);
    15. 	}
    16. 	//递归删除
    17. 	bool EraseR(const K& key)
    18. 	{
    19. 		return _EraseR(_root, key);
    20. 	}
    21. 	//中序遍历 类内调用拿root
    22. 	void InOrder()
    23. 	{
    24. 		_InOrder(_root);
    25. 		cout << endl;
    26. 	}
    27.  
    28.     //构造函数
    29.     BSTree() = default;
    30. 	//拷贝构造
    31. 	BSTree(const BSTree& t)；
    32. 	//赋值函数
    33. 	BSTree& operator=(BSTree t)；
    34. 	//析构函数
    35. 	~BSTree()；
    36. private:
    37. 	//类部子函数不继承的话通常私有
    38.     bool _EraseR(Node*& root,const K& key)；//递归删除
    39.     bool _InsertR(Node*& root,const K& key)；//递归插入
    40.     bool _FindR(Node* root,const K& key)；//递归查找
    41.     void _InOrder(Node* root)；//中序遍历函数
    42.     void DestroyTree(Node* root)//置空函数
    43. 	Node* CopyTree(Node* root)//树的拷贝
    44. private:
    45. 	Node* _root = nullptr;
    46. };

    下面我们来详细学习函数接口的具体实现

    递归插入函数的定义

    1. //递归插入函数
    2. bool _InsertR(Node*& root,const K& key)//递归插入
    3. {
    4.   if (root == nullptr)//为空就申请节点插入数据
    5.   {
    6.     root = new Node(key);//注意上面传指针引用 可以直接连接 
    7.     return true;
    8.   }
    9.   if (key > root->_key)//插入的值大于根 往右走
    10.   {
    11.     return _InsertR(root->_right, key);
    12.   }
    13.   else if (key < root->_key)//插入的值小于根 往右走
    14.   {
    15.     return _InsertR(root->_left, key);
    16.   }
    17.   else
    18.   {
    19.     return false;//相等说明数据已经有了
    20.   }
    21. }

    递归删除函数的定义

    1. bool _EraseR(Node*& root,const K& key)//递归删除
    2. {
    3.   //先找到要删除的节点
    4.   if (root == nullptr)//为空返回false
    5.   {
    6.     return false;
    7.   }
    8.   if (key > root->_key)//要删除的大于根
    9.   {
    10.     return  _EraseR(root->_right, key);//递归右树找
    11.   }
    12.   else if (key < root->_key)//要删除的小于根
    13.   {
    14.     return  _EraseR(root->_left, key);//递归左树找
    15.   }
    16.   
    17.   //走到这里说明已经找到要删除的数据
    18.   else
    19.   {
    20.     //1.删除一个孩子 左为空或右为空 托孤   
    21.   
    22.     Node* del = root;//先保存要删除的节点
    23. 	if (root->_left == nullptr)//左为空 让父亲指向右
    24. 	{
    25. 	  root = root->_right;//引用
    26. 	}
    27. 	else if (root->_right == nullptr)右为空 让父亲指向左
    28. 	{
    29. 	  root = root->_left;
    30. 	}
    31. 	
    32.     //2.删除2个孩子左右都不为空 替换法
    33.     else
    34. 	{
    35. 	  Node* minRight = root->_right;//
    36. 	  while (minRight->_left)
    37. 	  {
    38. 	    minRight = minRight->_left;
    39. 	  }
    40. 	  swap(root->_key, minRight->_key);//交换数据
    41. 	  //此时要删除的已经换下来 再去右树递归删除
    42. 	  return _EraseR(root->_right, key);//指定树	
    43. 	}
    44. 	delete del;
    45. 	return true;
    46.   }
    47. }

    中序遍历函数的定义

    1. //中序遍历
    2. void _InOrder(Node* root) 左子树 根 右子树
    3. {
    4.   if (root == nullptr)
    5. 	  return;
    6.   _InOrder(root->_left);//先走左边
    7.   cout << root->_key << " "; 打印数据
    8.   _InOrder(root->_right);//后走右边
    9. }

      我们先用以上接口实现图中二叉树的插入和删除测试案例TestBSTree

    1. //递归插入测试
    2. void TestBSTree1()
    3. {
    4.   //
    5.   BSTree<int> t;
    6.   int a[] = { 8,3,1,10,6,4,7,14,13, };
    7.   for (auto e : a)
    8.   {
    9.     t.InsertR(e);//依次插入 默认去重 
    10.   }
    11.   t.InOrder();//遍历打印 1 3 4 6 7 8 10 13 14
    12. }
    13.  
    14. //递归删除测试
    15. void TestBSTree2()
    16. {
    17.   //
    18.   BSTree<int> t;
    19.   int a[] = { 8,3,1,10,6,4,7,14,13, };
    20.   for (auto e : a)
    21.   {
    22.     t.InsertR(e);//依次插入 默认去重 
    23.   }
    24.   t.InOrder();//打印1 3 4 6 7 8 10 13 14
    25.  
    26.   t.EraseR(14);//删除14
    27.   t.InOrder();//打印1 3 4 6 7 8 10 13
    28. }
    29. int main()
    30. {
    31.   TestBSTree1();//递归插入
    32.   TestBSTree2();//递归删除
    33.   return 0;
    34. }

    递归查找函数的定义

    从根开始比较查找，比根大则往右边查找，比根小则往左边查找

    【数据结构】——搜索二叉树的插入，查找和删除（递归&非递归）
    zip 0星 超过10%的资源 275KB
    下载
    1. bool _FindR(Node* root,const K& key)//递归查找
    2. {
    3.  
    4.   if (root == nullptr)
    5.     return false;
    6.   if (key > root->_key)//
    7.   {
    8.     return _FindR(root->_right, key);
    9.   }
    10.   else if(key < root->_key)
    11.   {
    12.     return _FindR(root->_left, key);
    13.   }
    14.   else
    15.   {
    16.     return true;//相等就找到了
    17.   }
    18. }

    置空函数定义

    置空函数一般会放在我们进行插入或删除的函数最后，释放我们在堆上申请的空间，将其还给操作系统，另外也会相应的进行检查越界等问题

    1. void DestroyTree(Node* root)//置空函数
    2. {
    3.   if (root == nullptr)
    4. 	return;
    5.   DestroyTree(root->_left);
    6.   DestroyTree(root->_right);
    7.   delete root;
    8. }

    析构函数定义

    1. ~BSTree()//析构函数
    2. {
    3.   DestroyTree(_root);//调用置空函数
    4.   _root = nullptr;
    5. }

    赋值函数定义

    1. BSTree& operator=(BSTree t)//赋值函数
    2. {
    3.   swap(_root, t._root);
    4.   return *this;
    5. }

    树的拷贝函数定义

    1. Node* CopyTree(Node* root)//拷贝树
    2. {
    3.   if (root == nullptr)
    4. 	return nullptr;
    5.   Node* copynode = new Node(root->_key);
    6.   copynode->_left = CopyTree(root->_left);//递归创建左树
    7.   copynode->_right = CopyTree(root->_right);//递归创建右树
    8.   return copynode;
    9. }

    拷贝构造函数定义

    1. BSTree(const BSTree& t)//拷贝构造
    2. {
    3.   _root = CopyTree(t._root);//调用下方树的拷贝函数
    4.   cout << "调用拷贝构造" << endl;
    5. }

    我们再用上面这几个接口实现第3个测试案例TestBSTree3

    1. //赋值函数测试
    2. void TestBSTree3()
    3. {
    4.   //
    5.   BSTree<int> t;
    6.   int a[] = { 8,3,1,10,6,4,7,14,13, };
    7.   for (auto e : a)
    8.   {
    9.     t.InsertR(e);//依次插入 默认去重 
    10.   }
    11.   t.InOrder();//遍历打印 1 3 4 6 7 8 10 13 14
    12.   BSTree<int> t1;
    13.   t1 = t;//赋值函数 调用拷贝构造
    14.   t.InOrder();//遍历打印1 3 4 6 7 8 10 13 14
    15. }
    16.  
    17. int main()
    18. {
    19.   TestBSTree3();//赋值函数测试
    20.   return 0;
    21. }

    最后这里放一下整个二叉搜索树递归版本代码的实现，方便大家观察理解

    1. #pragma once
    2. template<class K>//搜索二叉树
    3. struct BSTreeNode
    4. {
    5.   BSTreeNode* _left;
    6.   BSTreeNode* _right;
    7.   K _key;
    8.   //构造函数
    9.   BSTreeNode(const K& key):_left(nullptr),_right(nullptr),_key(key)
    10.   {}
    11. };
    12.  
    13. template<class K>
    14. class BSTree
    15. {
    16.   typedef BSTreeNode Node;
    17.  
    18. public:
    19.  
    20. 	//默认构造
    21. 	BSTree() = default;
    22. 	//拷贝构造
    23. 	BSTree(const BSTree& t)
    24. 	{
    25. 		_root = CopyTree(t._root);
    26. 		cout << "调用拷贝构造" << endl;
    27. 	}
    28. 	//赋值函数
    29. 	BSTree& operator=(BSTree t)
    30. 	{
    31. 		swap(_root, t._root);
    32. 		return *this;
    33. 	}
    34. 	//析构函数
    35. 	~BSTree()
    36. 	{
    37. 		DestroyTree(_root);
    38. 		_root = nullptr;
    39. 	}
    40. 	//递归查找
    41. 	bool FindR(const K& key)
    42. 	{
    43. 		return _FindR(_root, key);
    44. 	}
    45. 	//递归插入
    46. 	bool InsertR(const K& key)
    47. 	{
    48. 		return _InsertR(_root, key);
    49. 	}
    50. 	//递归删除
    51. 	bool EraseR(const K& key)
    52. 	{
    53. 		return _EraseR(_root, key);
    54. 	}
    55. 	//中序遍历 类内调用拿root
    56. 	void InOrder()
    57. 	{
    58. 		_InOrder(_root);
    59. 		cout << endl;
    60. 	}
    61. private://类部子函数不继承的话通常私有
    62. 	//递归删除
    63. 	bool _EraseR(Node*& root,const K& key)
    64. 	{
    65. 		if (root == nullptr)
    66. 		{
    67. 			return false;
    68. 		}
    69. 		if (key > root->_key)//
    70. 		{
    71. 			return  _EraseR(root->_right, key);
    72. 		}
    73. 		else if (key < root->_key)
    74. 		{
    75. 			return  _EraseR(root->_left, key);
    76. 		}
    77. 		else
    78. 		{
    79. 			Node* del = root;//保存要删除的节点
    80. 			//相等说明可以删除了 三种情况
    81. 			if (root->_left == nullptr)
    82. 			{
    83. 				root = root->_right;//引用
    84. 			}
    85. 			else if (root->_right == nullptr)
    86. 			{
    87. 				root = root->_left;
    88. 			}
    89. 			else//左右都不为空 替换法
    90. 			{
    91. 				Node* minRight = root->_right;
    92. 				while (minRight->_left)
    93. 				{
    94. 					minRight = minRight->_left;
    95. 				}
    96. 				swap(root->_key, minRight->_key);//交换数据
    97. 				//此时要删除的已经换下来 再去右树递归删除
    98. 				return _EraseR(root->_right, key);//指定树
    99. 				
    100. 			}
    101. 			delete del;
    102. 			return true;
    103. 		}
    104. 	}
    105.  
    106. 	bool _InsertR(Node*& root,const K& key)//递归插入
    107. 	{
    108. 		if (root == nullptr)//为空就申请节点插入数据
    109. 		{
    110. 			root = new Node(key);//注意上面传指针引用 可以直接连接 
    111. 			return true;
    112. 		}
    113. 		if (key > root->_key)//插入的值大于根 往右走
    114. 		{
    115. 			return _InsertR(root->_right, key);
    116. 		}
    117. 		else if (key < root->_key)//插入的值小于根 往右走
    118. 		{
    119. 			return _InsertR(root->_left, key);
    120. 		}
    121. 		else
    122. 		{
    123. 			return false;//相等说明数据已经有了
    124. 		}
    125. 	}
    126.  
    127.  
    128. 	bool _FindR(Node* root,const K& key)//递归查找
    129. 	{
    130. 		//
    131. 		if (root == nullptr)
    132. 			return false;
    133. 		if (key > root->_key)//
    134. 		{
    135. 			return _FindR(root->_right, key);
    136. 		}
    137. 		else if(key < root->_key)
    138. 		{
    139. 			return _FindR(root->_left, key);
    140. 		}
    141. 		else
    142. 		{
    143. 			return true;//相等就找到了
    144. 		}
    145. 	}
    146. 	void _InOrder(Node* root)//中序遍历
    147. 	{
    148. 		if (root == nullptr)
    149. 			return;
    150.  
    151. 		_InOrder(root->_left);
    152. 		cout << root->_key << " ";
    153. 		_InOrder(root->_right);
    154. 	}
    155.  
    156. 	void DestroyTree(Node* root)//置空函数
    157. 	{
    158. 		if (root == nullptr)
    159. 			return;
    160. 		DestroyTree(root->_left);
    161. 		DestroyTree(root->_right);
    162. 		delete root;
    163. 	}
    164. 	Node* CopyTree(Node* root)//拷贝树
    165. 	{
    166. 		if (root == nullptr)
    167. 			return nullptr;
    168. 		Node* copynode = new Node(root->_key);
    169. 		copynode->_left = CopyTree(root->_left);//递归创建左树
    170. 		copynode->_right = CopyTree(root->_right);//递归创建右树
    171. 		return copynode;
    172. 	}
    173. private:
    174. 	Node* _root = nullptr;
    175. };
    176.  
    177.  
    178. //递归插入测试
    179. void TestBSTree1()
    180. {
    181. 	BSTree<int> t;
    182. 	int a[] = { 8,3,1,10,6,4,7,14,13, };
    183. 	for (auto e : a)
    184. 	{
    185. 		t.InsertR(e);//依次插入 默认去重 
    186. 	}
    187. 	t.InOrder();//遍历  
    188. }
    189.  
    190. //递归删除测试
    191. void TestBSTree2()
    192. {
    193. 	BSTree<int> t;
    194. 	int a[] = { 8,3,1,10,6,4,7,14,13, };
    195. 	for (auto e : a)
    196. 	{
    197. 		t.InsertR(e);//依次插入 默认去重 
    198. 	}
    199. 	t.InOrder();//打印 1 3 4 6 7 8 10 13 14
    200.  
    201. 	t.EraseR(8);//删除8
    202. 	t.EraseR(3);//删除3
    203. 	t.InOrder();//打印 1 4 6 7 10 13 14
    204. }
    205.  
    206. //赋值函数测试
    207. void TestBSTree3()
    208. {
    209. 	BSTree<int> t;
    210. 	int a[] = { 8,3,1,10,6,4,7,14,13, };
    211. 	for (auto e : a)
    212. 	{
    213. 		t.InsertR(e);//依次插入 默认去重 
    214. 	}
    215. 	t.InOrder();//遍历打印 1 3 4 6 7 8 10 13 14
    216. 	BSTree<int> t1;
    217. 	t1 = t;//赋值函数 调用拷贝构造
    218. 	t.InOrder();//遍历打印1 3 4 6 7 8 10 13 14
    219. }
    220.  
    221. int main()
    222. {
    223. 	TestBSTree1();//插入函数测试
    224. 	TestBSTree2();//删除函数测试
    225. 	TestBSTree3();//赋值函数测试
    226. 	return 0;
    227. }

    在Java和C++的学习当中，前期学习数据结构当中的顺序表、链表、二叉树等便于我们后面更好的学习容器，后面会继续分享红黑树和排序的实现

    希望这篇文章大家有所收获，我们下篇见

  • 相关阅读:
    机器学习知识总结 —— 15. 什么是支持向量机（对偶问题、核技巧）？
    Maximum And Queries (easy version)
    Java虚拟机（JVM）-- Dump内存快照
    代码分析之今日头条
    Windows10系统下安装GPU版Pytorch和MMDetection
    Docker 启动容器
    jQuery获取更改标签内容、操作标签属性：html()、text()、val()、attr()、prop()
    论文基本功——LaTeX：公式及其编号
    nginx常用命令
    Java特性之设计模式【备忘录模式】
  • 原文地址：https://blog.csdn.net/qq_72486849/article/details/126016282