VPF::[C] Удаление узла из бинарного дерева

Serious2008

Дата 28.1.2011, 01:19 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 294
Регистрация: 28.1.2011

Репутация: нет
Всего: нет

Задание

Цитата

Разработать программу удаления узла из заданного бинарного дерева. Ключ удаляемого узла необходимо ввести.

Внизу в коде написано, что нужно добавить, я не знаю как это сделать.

Код


#include <stdio.h>
#include <windows.h>
#include <string.h>
#include <conio.h>

typedef long BT;
struct BinTree{
       BT inf;
       BinTree *L; BinTree *R;
        };



BinTree* InsRec(BinTree *Tree, BT x)
{
  if (!Tree) {Tree = (BinTree *) malloc(sizeof(BinTree));
          Tree->inf=x; Tree->L=0; Tree->R=0;
         }
  else if (x < Tree->inf) Tree->L=InsRec(Tree->L, x);
       else Tree->R=InsRec(Tree->R, x);
  return Tree;
}

BinTree * Delete(BinTree *Tree, BT x)
{ BinTree* P, *v;
  if (!Tree) printf("òàêîãî ýëëåìåíòà â ñïèñêå íåò\n");
  else if (x < Tree->inf) Tree->L = Delete(Tree->L, x);
       else if (x > Tree-> inf) Tree->R = Delete(Tree->R, x);
        else {P = Tree;
          if (!Tree->R) Tree = Tree->L;
          else if (!Tree->L) Tree = Tree->R;
               else
                            { v = Tree->L;
                              if (v->R)
                              {
                  while (v->R->R) v = v->R;
                  Tree->inf = v->R->inf;
                  P = v->R; v->R = v->R->L;
                              }
                              else
                              {
                               Tree->inf = v->inf;
                               P = v;
                               Tree->L=Tree->L->L;
                              }
                }
          free(P);
         }
 return Tree;
}


//вот эту функцию преобразовать в вывод древа на чистом Си, без плюсов
void PrintTree(BinTree *T)
{
    if (T) {PrintTree(T->L); cout <<T->inf<< " "; PrintTree(T->R);}
}


main()
{

BinTree tree;
    for (int i=0; i<30; ++i) InsRec(&tree,i); //Древо из 30 элементов создаётся

//вот здесь вывести созданное дерево

    printf("Vvedite kod ellementa kotorie nugno udalit\n");
    int i=getchar(); Delete(&tree,i);
// заново вывести с уже удалённым
}

Это сообщение отредактировал(а) Serious2008 - 28.1.2011, 08:26

t_gran

Дата 28.1.2011, 07:32 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 621
Регистрация: 13.11.2007
Где: г.Усть-Илимск

Репутация: 33
Всего: 37

Как я понимаю нужно было только исправить ваши ляпы, чтобы программа заработала, так?

Код


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

typedef long BT;

typedef struct _BinTree
{
   BT inf;
   struct _BinTree *L;
   struct _BinTree *R;
}  BinTree;

//----------------------------------------------//
BinTree *InsRec(BinTree **Tree, BT x)
{
   if (!*Tree)
   {
      *Tree = (BinTree *) malloc(sizeof(BinTree));
      (*Tree)->inf = x;
      (*Tree)->L = 0;
      (*Tree)->R = 0;
   }
   else if (x < (*Tree)->inf)
   {
      (*Tree)->L = InsRec(&(*Tree)->L, x);
   }
   else
   {
      (*Tree)->R = InsRec(&(*Tree)->R, x);
   }
   return (*Tree);
}
//----------------------------------------------//
BinTree *Delete(BinTree *Tree, BT x)
{
   BinTree* P, *v;
   if (!Tree)
      printf("warning: tree is empty\n");
   else if (x < Tree->inf)
      Tree->L = Delete(Tree->L, x);
   else if (x > Tree-> inf)
      Tree->R = Delete(Tree->R, x);
   else
   {
      P = Tree;
      if (!Tree->R) Tree = Tree->L;
      else if (!Tree->L)
         Tree = Tree->R;
      else
      {
         v = Tree->L;
         if (v->R)
         {
            while (v->R->R) v = v->R;
            Tree->inf = v->R->inf;
            P = v->R;
            v->R = v->R->L;
         }
         else
         {
            Tree->inf = v->inf;
            P = v;
            Tree->L = Tree->L->L;
         }
      }
      free(P);
   }
   return Tree;
}
//----------------------------------------------//
//вот эту функцию преобразовать в вывод древа
void PrintTree(BinTree *T)
{
   if (T)
   {
      PrintTree(T->L);
      printf("%3d", T->inf);
      PrintTree(T->R);
   }
}
//----------------------------------------------//
int main()
{
   srand(time(0));

   BinTree *tree = NULL;
   int i;
   for (i=0; i<30; ++i)
      InsRec(&tree, rand()%99 + 1); //Древо из 30 элементов создаётся

   //вот здесь вывести созданное дерево
   PrintTree(tree);

   printf("\nInput deleted node: ");
   scanf("%d", &i);

   Delete(tree, i);

   PrintTree(tree);

// заново вывести с уже удалённым
   return 0;
}

Результат выполнения

Бинарник с исходником ниже

Присоединённый файл ( Кол-во скачиваний: 24 )

tree.zip 1,85 Kb

--------------------

Я знаю, что ничего не знаю© Сократ
user posted image

Serious2008

Дата 28.1.2011, 08:03 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 294
Регистрация: 28.1.2011

Репутация: нет
Всего: нет

t_gran
Гигантское тебе спасибо, чисто человеческое. Глянь ЛС, там просьба о маленьком дополнении.

t_gran

Дата 28.1.2011, 08:22 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 621
Регистрация: 13.11.2007
Где: г.Усть-Илимск

Репутация: 33
Всего: 37

Цитата

Глянь ЛС, там просьба о маленьком дополнении.

По просьбе трудящихся smile

Присоединённый файл ( Кол-во скачиваний: 43 )

tree.zip 1,89 Kb

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »