Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Бинарные деревья в c++  (Прочитано 11624 раз)
0 Пользователей и 1 Гость смотрят эту тему.
eLegAM
Гость
« : 21-06-2009 18:24 » 

Ребят, нужна помощь. В общем, надо построить бинарное дерево (дерево поиска), а потом из него удалить ветвь, начинающуюся с ключа M... есть ф-я построения дерева и ф-я вывода его на экран, помогите написать ф-ю удаления ветки, нач-ся с ключа M, и вывести на экран получившееся дерево...
Код:
#include <iostream.h>
#include <iomanip.h>
#include <stdlib.h>
#include <conio.h>
struct Node  
 { int key;
   Node *l;
   Node *r;
 };
typedef Node* NodePtr;
void AddTree(NodePtr& t, int k);
void TreeOut( NodePtr t, int level=1 );

void main()
{ NodePtr t, tl;
  int n, e;
  t = NULL;
  cout <<"vvedite 4isla,  konec- Ctrl+Z: ";
  while ( cin >>e ) AddTree(t, e);
  cout <<endl;  TreeOut( t );
  TreeOut(t);

}

void AddTree(NodePtr& t, int k)
 
{ if (t == NULL)  
   { t = new Node; t->l = NULL; t->r = NULL; t->key = k; }
   else    
    { if (k >= t->key) AddTree(t->r, k);  
      if (k <  t->key) AddTree(t->l, k);  
    }
}

void TreeOut( NodePtr t, int level )
{ int tab = 5;

  if (t == NULL) cout <<"Derevo pusto \n";
   else
    { if (t->r != NULL) TreeOut(t->r, level+1);
   
      cout <<setw(tab*level) <<t->key <<endl;
      if (t->l != NULL) TreeOut(t->l, level+1);
    }
}
« Последнее редактирование: 29-06-2009 09:18 от Sel » Записан
sss
Специалист

ru
Offline Offline

« Ответ #1 : 23-06-2009 04:26 » 

eLegAM, так как дерево не сбалансированно, можно просто использовать рекурсию...
Код:
void DelNode( NodePtr pNode)
 
{
  if ( pNode->l) DelNode( pNode->l);
  if ( pNode->r) DelNode( pNode->r);
  delete pNode;
}

Так как нет свойства Parent, использовать можно либо от корня (полная очистка),
либо вот так (удаление потомков):
Код:
 
  ... 
  //Откуда-то взяли правильный pNode
  if ( pNode->l)
  {
    DelNode( pNode->l);
    pNode->l = NULL;
  }

  if ( pNode->r)
  {
    DelNode( pNode->r);
    pNode->r = NULL;
  }

}

Записан

while (8==8)
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines