fork(20) download
copy 
  1. #include <iostream>
  2. #include <cstdlib>
  3.  
  4. struct Tree {
  5. 	int   val;
  6. 	Tree* left;
  7. 	Tree* right;
  8. };
  9.  
  10. Tree* InsertNode(Tree* node, int val);
  11. void  PrintNode(std::ostream& _out, const Tree* node);
  12. void  ClearNode(Tree* node);
  13.  
  14.  
  15. //удаление
  16. Tree* DeleteNode(Tree* node, int val){
  17. 	if(node == NULL)
  18. 		return node;
  19.  
  20. 	if(val == node->val){
  21.  
  22. 		Tree* tmp;
  23. 		if(node->right == NULL)
  24. 			tmp = node->left;
  25. 		else {
  26.  
  27. 			Tree* ptr = node->right;
  28. 			if(ptr->left == NULL){
  29. 				ptr->left = node->left;
  30. 				tmp = ptr;
  31. 			} else {
  32.  
  33. 				Tree* pmin = ptr->left;
  34. 				while(pmin->left != NULL){
  35. 					ptr  = pmin;
  36. 					pmin = ptr->left;
  37. 				}
  38. 				ptr->left   = pmin->right;
  39. 				pmin->left  = node->left;
  40. 				pmin->right = node->right;
  41. 				tmp = pmin;
  42. 			}
  43. 		}
  44.  
  45. 		delete node;
  46. 		return tmp;
  47. 	} else if(val < node->val)
  48. 		node->left  = DeleteNode(node->left, val);
  49. 	else
  50. 		node->right = DeleteNode(node->right, val);
  51. 	return node;
  52. }
  53.  
  54.  
  55. int main(void){
  56. 	Tree* tree = NULL;
  57. 	for(int i = 0; i < 20; ++i)
  58. 		tree = InsertNode(tree, std::rand() % 10);
  59.  
  60. 	PrintNode(std::cout, tree);
  61. 	std::cout << std::endl;
  62.  
  63. 	tree = DeleteNode(tree, 5);
  64. 	tree = DeleteNode(tree, 2);
  65. 	tree = DeleteNode(tree, 9);
  66.  
  67. 	PrintNode(std::cout, tree);
  68. 	ClearNode(tree);
  69. 	return 0;
  70. }
  71.  
  72.  
  73. //вставка
  74. Tree* InsertNode(Tree* node, int val){
  75. 	if(node == NULL){
  76. 		node = new (std::nothrow) Tree();
  77. 		if(node != NULL){
  78. 			node->val  = val;
  79. 			node->left = node->right = NULL;
  80. 		}
  81. 		return node;
  82. 	}
  83.  
  84. 	if(val < node->val)
  85. 		node->left  = InsertNode(node->left, val);
  86. 	else
  87. 		node->right = InsertNode(node->right, val);
  88. 	return node;
  89. }
  90.  
  91. //печать
  92. void PrintNode(std::ostream& _out, const Tree* node){
  93. 	if(node != NULL){
  94. 		if(node->left != NULL)
  95. 			PrintNode(_out, node->left);
  96.  
  97. 		_out << node->val << ' ';
  98.  
  99. 		if(node->right != NULL)
  100. 			PrintNode(_out, node->right);
  101. 	}
  102. }
  103.  
  104. //удаление всего
  105. void ClearNode(Tree* node){
  106. 	if(node != NULL){
  107. 		if(node->left != NULL)
  108. 			ClearNode(node->left);
  109. 		if(node->right != NULL)
  110. 			ClearNode(node->right);
  111. 		delete node;
  112. 	}
  113. }
Success #stdin #stdout 0s 3228KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0 1 2 2 2 3 3 3 5 5 6 6 6 6 6 7 7 9 9 
0 0 1 2 2 3 3 3 5 6 6 6 6 6 7 7 9
https://ideone.com/lre6CJ
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!