fork(3) download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3.  
  4. struct node
  5. {
  6. 	node*left,
  7. 		*right;
  8. 	int key;
  9. 	char value[100];
  10. };
  11.  
  12. void insert(node** root, char* word)
  13. {
  14. 	node * new_node = new node();
  15. 	strcpy(new_node->value, word);
  16. 	new_node->key = 1;
  17. 	new_node->left = NULL;
  18. 	new_node->right = NULL;
  19. 	if ((*root) != NULL)
  20. 	{
  21. 		if (strcmp((*root)->value, new_node->value) > 0)
  22. 		{
  23. 			insert(&(*root)->left, word);
  24. 		}
  25. 		else if (strcmp((*root)->value, new_node->value) < 0)
  26. 		{
  27. 			insert(&(*root)->right, word);
  28. 		}
  29. 		else
  30. 			(*root)->key++;
  31. 	}
  32. 	else
  33. 	{
  34. 		(*root) = new_node;
  35. 	}
  36. }
  37.  
  38. void preorder(node* p) {
  39. 	if (p == NULL) return;
  40.  
  41. 	std::cout << p->value << std::endl;
  42. 	preorder(p->left);
  43. 	preorder(p->right);
  44. }
  45.  
  46.  
  47. node* findNode(node* p, char * word) {
  48. 	if (p == NULL || strcmp(p->value, word) == 0)
  49. 		return p;
  50. 	if (strcmp(p->value, word) > 0)
  51. 	return findNode(p->left, word);
  52. 	else 
  53. 		return findNode(p->right, word);
  54. }
  55.  
  56. node* findMinNode(node* p) {
  57. 	while (p->left != NULL) p = p->left;
  58. 	return p;
  59. }
  60.  
  61. node* DeleteNode(node *root, node * delnode)
  62. {
  63. 	if (root == NULL) return root;
  64.  
  65. 	else if (strcmp(root->value, delnode->value) > 0) root->left = DeleteNode(root->left, delnode);
  66.  
  67. 	else if (strcmp(root->value, delnode->value) < 0)  root->right = DeleteNode(root->right, delnode);
  68. 	else {
  69. 		// у  узла нет дочерних узлов
  70. 		// просто удаляем этот узел
  71. 		if (root->left == NULL && root->right == NULL)
  72. 		{
  73. 			delete root;
  74. 			root = NULL;
  75.  
  76. 		}
  77.  
  78. 		// если есть один дочерний 
  79. 		// меняем на него 
  80. 		else if (root->left == NULL) {
  81. 			node *temp = root;
  82. 			root = root->right;
  83. 			delete temp;
  84. 		}
  85. 		else if (root->right == NULL) {
  86. 			node *temp = root;
  87. 			root = root->left;
  88. 			delete temp;
  89. 		}
  90.  
  91. 		//если  удаляемый элемент имеет двух потомков
  92. 		//то нужно заменить его минимальным элементом из правого поддерева
  93. 		// и рекурсивно удалить минимальный элемент из правого поддерева
  94. 		else {
  95. 			node *temp = findMinNode(root->right);
  96. 			strcpy(root->value, temp->value);
  97. 			root->right = DeleteNode(root->right, temp);
  98. 		}
  99. 	}
  100. 	return root;
  101. }
  102. int main()
  103. {
  104. 	node* tree = NULL;
  105. 	char line[] = "Ivan Ivanov Odessa 34 0482222222";
  106. 	char word[] = "Odessa";
  107.  
  108. 	for (char *ptr = strtok(line, " ,!?"); ptr != NULL; ptr = strtok(NULL, " ,!?"))
  109. 	{
  110. 		insert(&tree, ptr);
  111. 	}
  112. 	// вывод дерева
  113. 	preorder(tree);
  114.  
  115. 	// ввод слова для удаления
  116. 	std::cout << "\nword for deleting: ";
  117. 	//std::cin.getline(word, 50);
  118.  
  119.  
  120. 	node* fnode = findNode(tree, word);
  121. 	if (fnode)
  122. 	{
  123. 		std::cout << fnode->value << std::endl;
  124. 		tree = DeleteNode(tree, fnode);
  125. 	}
  126. 	else
  127. 		std::cout << "\nWord not found.\n";
  128.  
  129. std::cout << "\n";
  130. 	// вывод дерева
  131. 	preorder(tree);
  132.  
  133.  
  134.  
  135. 	return 0;
  136. }
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Ivan
34
0482222222
Ivanov
Odessa

word for deleting: Odessa

Ivan
34
0482222222
Ivanov
https://ideone.com/s5dtCK
language:
C++14 (gcc 8.3)
created:
7 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!