Бинарное дерево поиска. Разработать функцию удаления - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Здравствуйте! Помогите пожалуйста!

Имеется

связной список

, который содержит

целые числа

. Нужно сформировать на основе списка

бинарное дерево поиска

, а также нужно разработать

функцию удаления

 из дерева всех узлов, содержащих отрицательные значения.

Очень нужна ваша помощь!!!

Забыл код:
Листинг программы 
  1. #include "stdafx.h"
  2. #include <iostream>
  3. using namespace std;
  4.  
  5. struct node
  6. {
  7.     int key;
  8.     node* lft;
  9.     node* rgt;
  10.     node(int key) : key(key), lft(0), rgt(0)
  11.     {
  12.     }
  13.     ~node()
  14.     {
  15.         delete lft;
  16.         delete rgt;
  17.     }
  18.     bool isleaf() const
  19.     {
  20.         return (lft == rgt) && (lft == NULL);
  21.     }
  22. };
  23.  
  24. node* destroy(node *n)
  25. {
  26.     //  дерево состоит из одной вершины
  27.     if (n->isleaf())
  28.     {
  29.         delete n;
  30.         return 0;
  31.     }
  32.     else
  33.         //  левое поддерево пусто
  34.         if (n->lft == 0)
  35.         {
  36.             //  сохраняем указатель на правое поддерево
  37.             node* r = n->rgt;
  38.             //  копируем состояние узла находящегося справа
  39.             *n = *r;
  40.             //  удаляем узел
  41.             r->lft = 0;
  42.             r->rgt = 0;
  43.             delete r;
  44.         }
  45.         else
  46.             //  левое поддерево не пусто
  47.         {
  48.             //  ищем узел являющийся самым правым в левом поддереве
  49.             //  самый правый узел
  50.             node *c = n->lft;
  51.             //  родитель самого правого узла 
  52.             node *p = n->lft;
  53.  
  54.             //  двигаемся по правой ветви левого поддерева
  55.             while (c->rgt)
  56.             {
  57.                 p = c;
  58.                 c = c->rgt;
  59.             }
  60.  
  61.             //  левое поддерево самого правого узла становиться правым поддеревом родителя
  62.             p->rgt = c->lft;
  63.             //  рвем отношение
  64.             c->lft = NULL;
  65.             //  переносим ключ
  66.             n->key = c->key;
  67.             //  удаляем самый правый узел
  68.             delete c;
  69.         }
  70.     return n;
  71. }
  72.  
  73. node* remove(node *n, int key)
  74. {
  75.     //  если достигли листа, то узла с данным ключем не существует
  76.     if (n == NULL)
  77.         return 0;
  78.     //  если ключ текущего узла меньше искомого
  79.     if (n->key < key)
  80.     {
  81.         //  идем по правой ветке
  82.         n->rgt = remove(n->rgt, key);
  83.         return n;
  84.     }
  85.     else
  86.         //  если ключ текущего узла больше искомого
  87.         if (key < n->key)
  88.         {
  89.             //  идем по левой ветке
  90.             n->lft = remove(n->lft, key);
  91.             return n;
  92.         }
  93.     //  ключ текущего узла равен искомому
  94.     return destroy(n);
  95. }
  96.  
  97. void print(node *n, int l = 0)
  98. {
  99.     if (n)
  100.     {
  101.         print(n->rgt, l + 2);
  102.         std::cout << std::string(l, ' ') << n->key << '\n';
  103.         //printf(" %s \n", n->key,);
  104.         print(n->lft, l + 2);
  105.     }
  106. }
  107.  
  108. int main()
  109. {
  110.     // исходное дерево
  111.     node *tree = new node(10);
  112.     tree->lft = new node(5);
  113.     tree->lft->rgt = new node(8);
  114.     tree->lft->rgt->lft = new node(6);
  115.     tree->rgt = new node(15);
  116.     // исходное дерево
  117.     print(tree);
  118.     // последовательно удаляем каждый элемент дерева
  119.     remove(tree, 10);
  120.     print(tree);
  121.     tree = remove(tree, 6);
  122.     print(tree);
  123.     tree = remove(tree, 5);
  124.     print(tree);
  125.     tree = remove(tree, 8);
  126.     print(tree);
  127.     tree = remove(tree, 15);
  128.     print(tree);
  129.     delete tree;
  130.  
  131.     return 0;
  132. }

Решение задачи: «Бинарное дерево поиска. Разработать функцию удаления»

textual
Листинг программы 
  1. #include "stdafx.h"
  2. #include <iostream>
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include "locale.h"
  6.  
  7. struct node
  8. {
  9.     int key;
  10.     struct node *left, *right;
  11. };
  12.  
  13. /* Функция для создания нового узла дерева */
  14. struct node *newNode(int item)
  15. {
  16.     struct node *temp = (struct node *)malloc(sizeof(struct node));
  17.     temp->key = item;
  18.     temp->left = temp->right = NULL;
  19.     return temp;
  20. }
  21.  
  22. /* Функция для образования симметричного обхода дерева */
  23. void inorder(struct node *root)
  24. {
  25.     if (root != NULL)
  26.     {
  27.         inorder(root->left);
  28.         printf("%d ", root->key);
  29.         inorder(root->right);
  30.     }
  31. }
  32.  
  33. /* Функция для вставки нового узла с данным ключом в дерево */
  34. struct node* insert(struct node* node, int key)
  35. {
  36.     if (node == NULL) return newNode(key);
  37.     if (key < node->key)
  38.         node->left = insert(node->left, key);
  39.     else
  40.         node->right = insert(node->right, key);
  41.     return node;
  42. }
  43.  
  44. /* Given a non-empty binary search tree, return the node with minimum
  45. key value found in that tree. Note that the entire tree does not
  46. need to be searched. */
  47. struct node * minValueNode(struct node* node)
  48. {
  49.     struct node* current = node;
  50.     while (current->left != NULL)
  51.         current = current->left;
  52.     return current;
  53. }
  54.  
  55. /* Функция удаления ключа и возврата нового корня */
  56. struct node* deleteNode(struct node* root, int key)
  57. {
  58.     if (root == NULL) return root;
  59.     if (key < root->key)
  60.         root->left = deleteNode(root->left, key);
  61.     else if (key > root->key)
  62.         root->right = deleteNode(root->right, key);
  63.     else
  64.     {
  65.         if (root->left == NULL)
  66.         {
  67.             struct node *temp = root->right;
  68.             free(root);
  69.             return temp;
  70.         }
  71.         else if (root->right == NULL)
  72.         {
  73.             struct node *temp = root->left;
  74.             free(root);
  75.             return temp;
  76.         }
  77.         struct node* temp = minValueNode(root->right);
  78.         root->key = temp->key;
  79.         root->right = deleteNode(root->right, temp->key);
  80.     }
  81.     return root;
  82. }
  83.  
  84.  
  85. int main()
  86. {
  87.     /* Дерево:
  88.     50
  89.     /     \
  90.     30      70
  91.     /  \    /  \
  92.     20   40  60   80 */
  93.     struct node *root = NULL;
  94.     root = insert(root, 50);
  95.     root = insert(root, 30);
  96.     root = insert(root, 20);
  97.     root = insert(root, 40);
  98.     root = insert(root, 70);
  99.     root = insert(root, 60);
  100.     root = insert(root, 80);
  101.  
  102.     setlocale(0, "RUS");
  103.  
  104.     if (root < 0)
  105.     {
  106.         root = deleteNode(root, 20);
  107.     }
  108.  
  109.     printf("Дерево списком: \n");
  110.     inorder(root);
  111. ///////////////////////////////////////
  112.     if (root < 0)
  113.     {
  114.         root = deleteNode(root, -20);
  115.     }
  116. //////////////////////////////////////
  117.     /*printf("\nУдаляем 20\n");
  118.     root = deleteNode(root, 20);
  119.     printf("Дерево без 20 \n");
  120.     inorder(root);
  121.  
  122.     printf("\nУдаляем 30\n");
  123.     root = deleteNode(root, 30);
  124.     printf("Дерево без 30 \n");
  125.     inorder(root);
  126.  
  127.     printf("\nУдаляем 50\n");
  128.     root = deleteNode(root, 50);
  129.     printf("Дерево без 50 \n");
  130.     inorder(root);*/
  131.  
  132.     return 0;
  133. }

Объяснение кода листинга программы

  1. Создание нового узла дерева с помощью функции newNode(int item).
  2. Вставка нового узла в дерево с помощью функции insert(struct node* node, int key).
  3. Поиск узла с минимальным значением ключа в дереве с помощью функции minValueNode(struct node* node).
  4. Удаление ключа и возврат нового корня с помощью функции deleteNode(struct node* root, int key).
  5. Создание дерева для тестирования функций:
    • Создание корневого узла с ключом 50.
    • Вставка узлов с ключами 30, 20, 40, 70, 60 и 80 в дерево.
  6. Установка русской локали для вывода.
  7. Вывод списка узлов дерева с помощью функции inorder(struct node* root).
  8. Удаление узла с ключом 20 из дерева.
  9. Удаление узла с ключом 30 из дерева.
  10. Удаление узла с ключом 50 из дерева.
  11. Возвращение локали на английский язык.
  12. Ввод отрицательного значения для ключа, чтобы проверить обработку ошибок в функции deleteNode(struct node* root, int key).
  13. Ввод отрицательного значения для ключа, чтобы проверить обработку ошибок в функции deleteNode(struct node* root, int key).

ИИ поможет Вам:

  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

9   голосов , оценка 4.444 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы