fork(3) download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <malloc.h>
  4.  
  5. typedef struct tree {
  6. 	struct tree* left;
  7. 	struct tree* right;
  8. 	int    val;
  9. } bstree;
  10.  
  11. int  bstree_add(bstree** tr, int val);
  12. void bstree_remove(bstree** tr, int val);
  13. void bstree_print(FILE* hout, const bstree* tr);
  14. void bstree_clear(bstree* tr);
  15.  
  16.  
  17.  
  18. int main(void){
  19. 	int     i;
  20. 	bstree* tr = NULL;
  21.  
  22. 	for(i = 0; i < 30; ++i)
  23. 		bstree_add(&tr, rand() % 10);
  24.  
  25. 	//вывести 
  26. 	bstree_print(stdout, tr);
  27.  
  28. 	//удалить
  29. 	bstree_remove(&tr, 1);
  30. 	bstree_remove(&tr, 4);
  31. 	bstree_remove(&tr, 9);
  32. 	bstree_remove(&tr, 6);
  33.  
  34. 	putchar('\n');
  35. 	bstree_print(stdout, tr);
  36.  
  37. 	bstree_clear(tr);
  38. 	return 0;
  39. }
  40.  
  41.  
  42.  
  43. //добавление элемента в bst-дерево
  44. int bstree_add(bstree** tr, int val){
  45. 	bstree* ptr = *tr;
  46.  
  47. 	while(ptr != NULL){
  48. 		if(val == ptr->val)
  49. 			return 0;
  50. 		else if(val < ptr->val){
  51. 			tr  = &ptr->left;
  52. 			ptr = ptr->left;
  53. 		} else {
  54. 			tr  = &ptr->right;
  55. 			ptr = ptr->right;
  56. 		}
  57. 	}
  58.  
  59. 	ptr = (bstree*)malloc(sizeof(bstree));
  60. 	if(ptr == NULL)
  61. 		return 0;
  62.  
  63. 	ptr->left = ptr->right = NULL;
  64. 	ptr->val  = val;
  65. 	*tr = ptr;
  66. 	return 1;
  67. }
  68.  
  69.  
  70. //удаление элемента из дерева
  71. void bstree_remove(bstree** tr, int val){
  72. 	bstree*  ptr1, *iter, *ptr2;
  73.  
  74. 	for(iter = *tr; iter != NULL;){
  75. 		if(val == iter->val)
  76. 			break;
  77. 		else if(val < iter->val) {
  78. 			tr   = &iter->left;
  79. 			iter = iter->left;
  80. 		} else {
  81. 			tr   = &iter->right;
  82. 			iter = iter->right;
  83. 		}
  84. 	}
  85.  
  86. 	if(iter == NULL)
  87. 		return;
  88.  
  89. 	if(iter->right == NULL)
  90. 		*tr = iter->left; 
  91. 	else {
  92. 		ptr2 = iter->right;
  93. 		if(ptr2->left == NULL) { 
  94. 			ptr2->left = iter->left;  
  95. 			*tr = ptr2;
  96. 		} else {
  97. 			ptr1 = ptr2->left; 
  98. 			while(ptr1->left != NULL){
  99. 				ptr2 = ptr1;
  100. 				ptr1 = ptr2->left;
  101. 			}
  102. 			ptr2->left  = ptr1->right;
  103. 			ptr1->left  = iter->left;
  104. 			ptr1->right = iter->right;
  105. 			*tr = ptr1;
  106. 		}
  107. 	}
  108. 	free(iter);
  109. }
  110.  
  111.  
  112. //проход по-возрастанию
  113. void bstree_print(FILE* hout, const bstree* tr){
  114. 	if(tr != NULL){
  115. 		bstree_print(hout, tr->left);
  116. 		fprintf(hout, "%d ", tr->val);
  117. 		bstree_print(hout, tr->right);
  118. 	}
  119. }
  120.  
  121.  
  122. //удаление всего дерева
  123. void bstree_clear(bstree* tr){
  124. 	if(tr != NULL){
  125. 		bstree_clear(tr->left);
  126. 		bstree_clear(tr->right);
  127. 		free(tr);
  128. 	}
  129. }
  130.  
Success #stdin #stdout 0s 2140KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 1 2 3 5 6 7 8 9 
0 2 3 5 7 8
https://ideone.com/ZTmJS0
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!