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

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

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

Имеется

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

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

целые числа

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

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

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

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

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

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

Забыл код:

#include "stdafx.h"
#include <iostream>
using namespace std;
 
struct node
{
    int key;
    node* lft;
    node* rgt;
    node(int key) : key(key), lft(0), rgt(0)
    {
    }
    ~node()
    {
        delete lft;
        delete rgt;
    }
    bool isleaf() const
    {
        return (lft == rgt) && (lft == NULL);
    }
};
 
node* destroy(node *n)
{
    //  дерево состоит из одной вершины
    if (n->isleaf())
    {
        delete n;
        return 0;
    }
    else
        //  левое поддерево пусто
        if (n->lft == 0)
        {
            //  сохраняем указатель на правое поддерево
            node* r = n->rgt;
            //  копируем состояние узла находящегося справа
            *n = *r;
            //  удаляем узел
            r->lft = 0;
            r->rgt = 0;
            delete r;
        }
        else
            //  левое поддерево не пусто
        {
            //  ищем узел являющийся самым правым в левом поддереве
            //  самый правый узел
            node *c = n->lft;
            //  родитель самого правого узла 
            node *p = n->lft;
 
            //  двигаемся по правой ветви левого поддерева
            while (c->rgt)
            {
                p = c;
                c = c->rgt;
            }
 
            //  левое поддерево самого правого узла становиться правым поддеревом родителя
            p->rgt = c->lft;
            //  рвем отношение
            c->lft = NULL;
            //  переносим ключ
            n->key = c->key;
            //  удаляем самый правый узел
            delete c;
        }
    return n;
}
 
node* remove(node *n, int key)
{
    //  если достигли листа, то узла с данным ключем не существует
    if (n == NULL)
        return 0;
    //  если ключ текущего узла меньше искомого
    if (n->key < key)
    {
        //  идем по правой ветке
        n->rgt = remove(n->rgt, key);
        return n;
    }
    else
        //  если ключ текущего узла больше искомого
        if (key < n->key)
        {
            //  идем по левой ветке
            n->lft = remove(n->lft, key);
            return n;
        }
    //  ключ текущего узла равен искомому
    return destroy(n);
}
 
void print(node *n, int l = 0)
{
    if (n)
    {
        print(n->rgt, l + 2);
        std::cout << std::string(l, ' ') << n->key << '\n';
        //printf(" %s \n", n->key,);
        print(n->lft, l + 2);
    }
}
 
int main()
{
    // исходное дерево
    node *tree = new node(10);
    tree->lft = new node(5);
    tree->lft->rgt = new node(8);
    tree->lft->rgt->lft = new node(6);
    tree->rgt = new node(15);
    // исходное дерево
    print(tree);
    // последовательно удаляем каждый элемент дерева
    remove(tree, 10);
    print(tree);
    tree = remove(tree, 6);
    print(tree);
    tree = remove(tree, 5);
    print(tree);
    tree = remove(tree, 8);
    print(tree);
    tree = remove(tree, 15);
    print(tree);
    delete tree;
 
    return 0;
}

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

Листинг программы

#include "stdafx.h"
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include "locale.h"
 
struct node
{
    int key;
    struct node *left, *right;
};
 
/* Функция для создания нового узла дерева */
struct node *newNode(int item)
{
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}
 
/* Функция для образования симметричного обхода дерева */
void inorder(struct node *root)
{
    if (root != NULL)
    {
        inorder(root->left);
        printf("%d ", root->key);
        inorder(root->right);
    }
}
 
/* Функция для вставки нового узла с данным ключом в дерево */
struct node* insert(struct node* node, int key)
{
    if (node == NULL) return newNode(key);
    if (key < node->key)
        node->left = insert(node->left, key);
    else
        node->right = insert(node->right, key);
    return node;
}
 
/* Given a non-empty binary search tree, return the node with minimum
key value found in that tree. Note that the entire tree does not
need to be searched. */
struct node * minValueNode(struct node* node)
{
    struct node* current = node;
    while (current->left != NULL)
        current = current->left;
    return current;
}
 
/* Функция удаления ключа и возврата нового корня */
struct node* deleteNode(struct node* root, int key)
{
    if (root == NULL) return root;
    if (key < root->key)
        root->left = deleteNode(root->left, key);
    else if (key > root->key)
        root->right = deleteNode(root->right, key);
    else
    {
        if (root->left == NULL)
        {
            struct node *temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL)
        {
            struct node *temp = root->left;
            free(root);
            return temp;
        }
        struct node* temp = minValueNode(root->right);
        root->key = temp->key;
        root->right = deleteNode(root->right, temp->key);
    }
    return root;
}
 
 
int main()
{
    /* Дерево:
    50
    /     \
    30      70
    /  \    /  \
    20   40  60   80 */
    struct node *root = NULL;
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 70);
    root = insert(root, 60);
    root = insert(root, 80);
 
    setlocale(0, "RUS");
 
    if (root < 0)
    {
        root = deleteNode(root, 20);
    }
 
    printf("Дерево списком: \n");
    inorder(root);
///////////////////////////////////////
    if (root < 0)
    {
        root = deleteNode(root, -20);
    }
//////////////////////////////////////
    /*printf("\nУдаляем 20\n");
    root = deleteNode(root, 20);
    printf("Дерево без 20 \n");
    inorder(root);
 
    printf("\nУдаляем 30\n");
    root = deleteNode(root, 30);
    printf("Дерево без 30 \n");
    inorder(root);
 
    printf("\nУдаляем 50\n");
    root = deleteNode(root, 50);
    printf("Дерево без 50 \n");
    inorder(root);*/
 
    return 0;
}

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

Создание нового узла дерева с помощью функции newNode(int item).
Вставка нового узла в дерево с помощью функции insert(struct node* node, int key).
Поиск узла с минимальным значением ключа в дереве с помощью функции minValueNode(struct node* node).
Удаление ключа и возврат нового корня с помощью функции deleteNode(struct node* root, int key).
Создание дерева для тестирования функций:
- Создание корневого узла с ключом 50.
- Вставка узлов с ключами 30, 20, 40, 70, 60 и 80 в дерево.
Установка русской локали для вывода.
Вывод списка узлов дерева с помощью функции inorder(struct node* root).
Удаление узла с ключом 20 из дерева.
Удаление узла с ключом 30 из дерева.
Удаление узла с ключом 50 из дерева.
Возвращение локали на английский язык.
Ввод отрицательного значения для ключа, чтобы проверить обработку ошибок в функции deleteNode(struct node* root, int key).
Ввод отрицательного значения для ключа, чтобы проверить обработку ошибок в функции deleteNode(struct node* root, int key).