【数据结构】二叉搜索树的删除，插入，查找

数据结构 前端之家
前端之家收集整理的这篇文章主要介绍了【数据结构】二叉搜索树的删除，插入，查找，前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。
  1. <span style="font-family: Arial,Helvetica,sans-serif; background-color: rgb(255,255,255);">二叉搜索树的意思就是在这个二叉树中每一个左孩子的值都比他的父节点小，每一个右孩子的值都比父节点的大，中序遍历后会出现一个有序的数组</span>

插入

插入节点每一次都是插在叶子节点

实现起来比较简单

实现了递归与非递归

  1. bool _InsertR(Node* root,const K& key)
  2. 		{
  3. 			//初始化插入结点
  4. 			Node* node=new Node(key);
  5. 			node->_key=key;
  6. 			node->_left=node->_right=node->_parent=NULL;
  7. 			//空树时，直接作为根结点
  8. 			if((root)==NULL)
  9. 			{
  10. 				root=node;
  11. 				return true;
  12. 			}
  13. 			//插入到当前结点（*root）的左孩子
  14. 			if((root)->_left == NULL && (root)->_key > key){
  15. 				node->_parent=root;
  16. 				root->_left=node;
  17. 				return true;
  18. 			}
  19. 			//插入到当前结点（*root）的右孩子
  20. 			if((root)->_right == NULL && (root)->_key < key){
  21. 				node->_parent=root;
  22. 				(root)->_right=node;
  23. 				return true;
  24. 			}
  25. 			if(root->_key > key)
  26. 				_InsertR(root->_left,key);
  27. 			else if(root->_key < key)
  28. 				_InsertR(root->_right,key);
  29. 			else
  30. 				return true;
  1. ｝
  2. bool _Insert2(Node*& root,const K& key)
  3. 		{
  4. 			if(root==NULL)
  5. 			{
  6. 				root=new Node(key);
  7. 				return true;
  8. 			}
  9. 			if(root->_key<key)
  10. 				return _Insert2(root->_right,key);
  11. 			else if(root->_key>key)
  12. 				return _Insert2(root->_left,key);
  13. 			else
  14. 				return false;
  15. 		}
查找 
  1. 	bool FindR(const K& key)
  2. 	{
  3. 		if(_root==NULL)
  4. 			return false;
  5. 		Node* cur=_root;
  6. 		while(cur)
  7. 		{
  8. 			if(cur->_key<key)
  9. 				cur=cur->_right;
  10. 			else if(cur->_key>key)
  11. 				cur=cur->_left;
  12. 			else
  13. 				return true;
  14. 		}
  15. 	}

删除节点比较难，分四种情况

1.被删节点无左孩子

2.被删节点无右孩子

3.被删节点无左孩子也无右孩子

4.被删节点既有右孩子又有左孩子

递归实现

  1. bool _Remove(Node*& root,const K& key)
  2. 		{
  3. 			if (root==NULL)
  4. 			{
  5. 				return false;
  6. 			}
  7. 			if(root->_key<key)
  8. 			{
  9. 			return	_Remove(root->_right,key);
  10. 			}
  11. 			else if(root->_key>key)
  12. 			{
  13. 				return _Remove(root->_left,key);
  14. 			}
  15. 			else
  16. 			{
  17. 				Node* del=root;
  18. 				if(root->_left==NULL)
  19. 				{
  20. 					root=root->_right;
  21. 				}
  22. 				else if(root->_right==NULL)
  23. 				{
  24. 					root=root->_left;
  25. 				}
  26. 				delete del;
  27. 			}
  28. 		return true;
  29. 		}
非递归实现 
  1. bool Remove(const K& key)//非递归
  2. 	{
  3. 		if(_root==NULL)
  4. 			return false;
  5. 		Node* pre=NULL;
  6. 		Node* cur=_root;
  7. 		Node* del=cur;
  8. 		while (cur&&cur->_key!=key)
  9. 		{
  10. 			if(cur->_key>key)
  11. 			{
  12.  
  13. 				pre=cur;
  14. 				cur=cur->_left;
  15. 			}
  16. 			else if (cur->_key<key)
  17. 			{
  18. 				pre=cur;
  19. 				cur=cur->_right;
  20. 			}
  21. 		}
  22. 		if(cur->_left==NULL)
  23. 		{
  24. 			if(cur==_root)
  25. 				_root=cur->_right;
  26. 			else if(cur==pre->_left)
  27. 			{
  28. 				pre->_left=cur->_right;
  29. 			}
  30. 			else
  31. 			{
  32. 				pre->_right=cur->_right;
  33. 			}
  34. 			del=cur;
  35. 		}
  36. 		else if (cur->_right==NULL)
  37. 		{
  38. 			if(cur==_root)
  39. 			{
  40.        _root=cur->_left;
  41. 			}
  42. 			else if (pre->_left==cur)
  43. 			{
  44. 				pre->_left==cur->_left;
  45. 			}
  46. 			else
  47. 			{
  48. 				pre->_right=cur->_left;
  49. 			}
  50. 			del=cur;
  51. 		}
  52. 		else
  53. 		{
  54. 			Node* minRight=cur->_right;//右孩子最左节点
  55. 			pre=cur;
  56. 			while (minRight->_left)
  57. 			{
  58. 				pre=minRight;
  59. 				minRight=minRight->_left;
  60. 			}
  61. 			del=minRight;
  62. 			cur->_key=minRight->_key;//交换节点值
  63. 			if(pre->_left==minRight)
  64. 			{
  65. 				pre->_left=minRight->_right;
  66. 			}
  67. 			else
  68. 			{
  69. 				pre->_right=minRight->_right;
  70. 			}
  71. 		}
  72. 		delete del;
  73. 		return true;
  74. 		
  75. 	}

源代码 
  1. #include<iostream>
  2. using namespace std;
  3. template<class K>
  4. struct SearchBinaryTreeNode
  5. {
  6. 	SearchBinaryTreeNode<K>* _left;
  7. 	SearchBinaryTreeNode<K>* _right;
  8. 	SearchBinaryTreeNode<K>* _parent;
  9. 	K _key;
  10. 	SearchBinaryTreeNode(const K& key)
  11. 		:_key(key),_left(NULL),_right(NULL),_parent(NULL)
  12. 	{}
  13. };
  14. template<class K>
  15. class SearchBinaryTree
  16. {
  17. 	typedef SearchBinaryTreeNode<K> Node;
  18. public:
  19. 	SearchBinaryTree()
  20. 		:_root(NULL)
  21. 	{}
  22. 	SearchBinaryTree(const SearchBinaryTree<K>& t)
  23. 	{
  24. 		_root=t->_root;
  25. 	}
  26. 	~SearchBinaryTree()
  27. 	{
  28. 		delete _root;
  29. 	}
  30. 	bool InsertR(const K& key) // 插入节点
  31. 	{
  32. 		if (!_root) // 空树
  33. 		{
  34. 			_root = new Node(key);
  35. 			_root->_key = key;
  36. 		}
  37. 		else
  38. 		{
  39. 			_InsertR(_root,key);
  40. 		}
  41. 		return true;
  42. 	}
  43. 	bool Insert2(const K& key)//递归
  44. 	{
  45. 		_Insert2(_root,key);
  46. 		return true;
  47. 	}
  48. 	bool Remove2(const K& key)//递归
  49. 	{
  50. 		_Remove(_root,key);
  51. 		return true;
  52. 	}
  53. 	bool Remove(const K& key)//非递归
  54. 	{
  55. 		if(_root==NULL)
  56. 			return false;
  57. 		Node* pre=NULL;
  58. 		Node* cur=_root;
  59. 		Node* del=cur;
  60. 		while (cur&&cur->_key!=key)
  61. 		{
  62. 			if(cur->_key>key)
  63. 			{
  64.  
  65. 				pre=cur;
  66. 				cur=cur->_left;
  67. 			}
  68. 			else if (cur->_key<key)
  69. 			{
  70. 				pre=cur;
  71. 				cur=cur->_right;
  72. 			}
  73. 		}
  74. 		if(cur->_left==NULL)
  75. 		{
  76. 			if(cur==_root)
  77. 				_root=cur->_right;
  78. 			else if(cur==pre->_left)
  79. 			{
  80. 				pre->_left=cur->_right;
  81. 			}
  82. 			else
  83. 			{
  84. 				pre->_right=cur->_right;
  85. 			}
  86. 			del=cur;
  87. 		}
  88. 		else if (cur->_right==NULL)
  89. 		{
  90. 			if(cur==_root)
  91. 			{
  92.        _root=cur->_left;
  93. 			}
  94. 			else if (pre->_left==cur)
  95. 			{
  96. 				pre->_left==cur->_left;
  97. 			}
  98. 			else
  99. 			{
  100. 				pre->_right=cur->_left;
  101. 			}
  102. 			del=cur;
  103. 		}
  104. 		else
  105. 		{
  106. 			Node* minRight=cur->_right;//右孩子最左节点
  107. 			pre=cur;
  108. 			while (minRight->_left)
  109. 			{
  110. 				pre=minRight;
  111. 				minRight=minRight->_left;
  112. 			}
  113. 			del=minRight;
  114. 			cur->_key=minRight->_key;//交换节点值
  115. 			if(pre->_left==minRight)
  116. 			{
  117. 				pre->_left=minRight->_right;
  118. 			}
  119. 			else
  120. 			{
  121. 				pre->_right=minRight->_right;
  122. 			}
  123. 		}
  124. 		delete del;
  125. 		return true;
  126. 		
  127. 	}
  128. 	bool FindR(const K& key)
  129. 	{
  130. 		if(_root==NULL)
  131. 			return false;
  132. 		Node* cur=_root;
  133. 		while(cur)
  134. 		{
  135. 			if(cur->_key<key)
  136. 				cur=cur->_right;
  137. 			else if(cur->_key>key)
  138. 				cur=cur->_left;
  139. 			else
  140. 				return true;
  141. 		}
  142. 	}
  143.  
  144. 	void  InOrder()//中序遍历
  145. 	{
  146. 		_InOrder(_root);
  147. 		cout<<endl;
  148. 	}
  149. 	protected:
  150. 		bool _InsertR(Node* root,key);
  151. 			else
  152. 				return true;
  153. 		}
  154. 		bool _Insert2(Node*& root,key);
  155. 			else
  156. 				return false;
  157. 		}
  158. 		void _InOrder(Node* root)
  159. 		{
  160. 			Node* cur=root;
  161. 			if(cur==NULL)
  162. 				return;
  163. 			_InOrder(cur->_left);
  164. 			cout<<cur->_key<<" ";
  165. 			_InOrder(cur->_right);
  166. 		}
  167. 		bool _Remove(Node*& root,key);
  168. 			}
  169. 			else
  170. 			{
  171. 				Node* del=root;
  172. 				if(root->_left==NULL)
  173. 				{
  174. 					root=root->_right;
  175. 				}
  176. 				else if(root->_right==NULL)
  177. 				{
  178. 					root=root->_left;
  179. 				}
  180. 				delete del;
  181. 			}
  182. 		return true;
  183. 		}
  184.  
  185. private:
  186. 	Node* _root;
  187. };
  188. void test()
  189. {
  190. SearchBinaryTree<int> BSTree;//15,6,18,3,7,17,20,2,4,13,9
  191. BSTree.InsertR(15);
  192. BSTree.InsertR(6);
  193. BSTree.InsertR(18);
  194. BSTree.InsertR(3);
  195. BSTree.InsertR(7);
  196. BSTree.InsertR(17);
  197. BSTree.InsertR(20);
  198. BSTree.InsertR(2);
  199. BSTree.InsertR(4);
  200. BSTree.InsertR(13);
  201. BSTree.InsertR(9);
  202. BSTree.Insert2(10);
  203. BSTree.InOrder();
  204. BSTree.Remove2(13);
  205. BSTree.InOrder();
  206. BSTree.Remove(6);
  207. BSTree.InOrder();
  208. cout<<BSTree.FindR(2)<<endl;
  209. cout<<BSTree.FindR(20)<<endl;
  210. BSTree.InOrder();
  211. }

猜你在找的数据结构相关文章

【数据结构】键树
键树的基本概念 键树又称数字查找树（Digital Search Tree）。 它是一棵度大于等于2的树，...
【数据结构】绪论
[TOC] 基本概念 数据： 数据 是对客观事物的符号表示，在计算机科学中指所有能输入到计算机...
【数据结构】证明法
[TOC] 反证法 基本概念： 一般地，假设原命题不成立（即 在原命题的条件下，结论不成立），...
数据结构与算法系列之目录
最近抽空整理了&quot;数据结构和算法&quot;的相关文章。在整理过程中，对于每种数...
【数据结构】数组
[TOC] 矩阵在计算机图形学、工程计算中占有举足轻重的地位。在数据结构中考虑的是如何用最...
[操作系统]操作系统中断机制
1.当中断发生时，cpu立即进入核心态 2.当中断发生后，当前进程进入暂停状态，操作系统内核...
[日常] 浏览器前进后退与数据结构的思想
一张图保存一下 红点是当前地址 白色箭头是新打开页面 黑色箭头是后退页面 栈的思想 , 后退...
[算法] 开放寻址法解决哈希冲突方式
开放寻址法：又称开放定址法，当哈希冲突发生时，从发生冲突的那个单元起，按照一定的次序...
二叉树的基本概念介绍与代码实现（多图+代码）
@ 树的基本概念 图1 树的结点 结点：使用树结构存储的每一个数据元素都被称为“结点”。例...
史上最全单链表的增删改查反转等操作汇总以及5种排序算法(C语言)
1.准备工作 首先包含头文件，定义链表结构体，产生随即链表的范围，定义全局头尾节点。 #i...
LinuxWindowsCentOSUbuntuNginxWebServiceScalaMemcacheApacheRedisDockerBashAzureTomcatLNMPShell数据结构服务器运维网络安全
xebugnodemondocker-copydcoselasticsearcwindows-contdocker-windodocker-awsamazon-cloudenvoyproxyhashicorp-vaswisscomdevkafka-pythonzscalerphoton-osdocker-swarmkamongoogle-cloudconcoursewso2-ampersistent-vapi-managerprocess-manamanjarojenkins-workhypriotremoteapikeystonejsbitcoindbitcoin-test