Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

добавление в Бинарное Дерево

14K
21 ноября 2005 года
Rockie
6 / / 21.11.2005
Здравствуйте. Есть класс Бинарного дерева и класс его узла. AddUzel - функция , добавляющая узел в корень дерева (если дерево пустое) и далее по указателям левее или правее в зависимости от того, число нового узла меньше или больше старого. Если к примеру больше, то нужно пройти по указателю right и посмотреть, установлен ли он в NULL. Если правый указатель не указывает на следующее звено, то добавляем туда наш узел. Если указывает, проходим вправо и делаем то же самое что и для корня. подскажите пожалуйста где я запутался. Сие творение создавалось под Cbuilder - ом на С++.


Код:
#include <vcl.h>
#pragma hdrstop
#include<stdio.h>
#include<iostream.h>
#include<stdlib.h>
#include<conio.h>

#define  space cout<<endl;
#define  space1 cout<<endl<<endl;


class BinUzel{               // UZEL CLASS
public:
 int value;
 BinUzel *left;
 BinUzel *right;
 BinUzel();
 BinUzel(int);
};

BinUzel::BinUzel(){
value = 0;
BinUzel *left=NULL;
BinUzel *right=NULL;
}

BinUzel::BinUzel(int a1){
value = a1;
BinUzel *left=NULL;
BinUzel *right=NULL;
}

class BinTree{
  public:
  BinUzel *FirstUzel;
  BinTree();
  void AddUzel(int);
};                                      


BinTree::BinTree()
{}


void BinTree::AddUzel(int v){
 BinUzel * UzelNew = new BinUzel(v);
 BinUzel * UzelTemp = new BinUzel;
 UzelTemp=FirstUzel;


 int flag=0;
while(flag!=1)
 {
 if (UzelTemp->value==UzelNew->value)
 { cout<<UzelNew->value<<" is already in tree"<<endl;
   flag=1;
 }

 if (UzelNew->value>UzelTemp->value)
   {
     if ( (UzelTemp->left==NULL) && (UzelTemp->right==NULL) )
               { UzelTemp->right = UzelNew;
                 flag=1;
                 cout<<"it was > "; space
               }
    else
               {  UzelTemp=UzelTemp->right;            // dvigaemsa
                  space cout<<"Moving after >";  space
               }
   }

 }
}

void main(){
 int i,n,a, flag;
 BinTree t;

 cout<<"Enter the number of tree elements ";  
 cin>>n;
 for(i=0;i<n;i++)
   { cout<<"element "<<i<<" = ";
     cin>>a;
     t.AddUzel(a);
   }
   space1   cout<<"Any key..";
   getch();
}
1
21 ноября 2005 года
kot_
7.3K / / 20.01.2000
Цитата:
Originally posted by Rockie
подскажите пожалуйста где я запутался.


Узел дерева имеет 4 точки отсчета - не учитывая this - право-лево, верх-низ. Здесь ты собственно и запутался. кроме лево-право, узел должен иметь ниже-выше (или перед-после, кому как нравится. :) )
Соответственно оператор = надо перегрузить.

14K
21 ноября 2005 года
Rockie
6 / / 21.11.2005
Цитата:
Originally posted by kot_
кроме лево-право, узел должен иметь ниже-выше (или перед-после, кому как нравится. :) )



Kot_ , а чтоя буду с этими указателями ниже выше делать? У Бинарного дерева указатели на меньший элемент и на больший. Если передаваемое значение уже есть в дереве, вставка не происходит. Дерево сразу упорядоченное, так как при вставке звена сразу определяется левее или правее его добавить. Потом при добавлении следующего опять смотрится левее или правее, начиная с корня. то есть добавляется только концевой узел. По-моему , в этом случае можно обойтись только left и right указателями.
За идею с перегрузкой спасибо

1
21 ноября 2005 года
kot_
7.3K / / 20.01.2000
Цитата:
Originally posted by Rockie
Kot_ , а чтоя буду с этими указателями ниже выше делать? У Бинарного дерева указатели на меньший элемент и на больший. Если передаваемое значение уже есть в дереве, вставка не происходит. Дерево сразу упорядоченное, так как при вставке звена сразу определяется левее или правее его добавить. Потом при добавлении следующего опять смотрится левее или правее, начиная с корня. то есть добавляется только концевой узел. По-моему , в этом случае можно обойтись только left и right указателями.
За идею с перегрузкой спасибо


Да ты прав. В двоичном дереве достаточно левоправых указателей. Тебе необходимо в классе дерева определить функцию сравнения элементов,и добавления узла тогда твоя функция вставки приблизительно будет выглядеть так:

Код:
void BinTree::AddUzel(int v){
if(FirstUzel == NULL){
 FirstUzel = new BinUzel(v);
 return;
}
else{
 int rezalt;
 BinUzel *nodecurr,*noderoot = FirstUzel;
while(noderoot){
 nodecurr = noderoot;
 rezalt = compare(v,nodecurr->value);
 if(rezalt < 0)
  noderoot = nodecurr->left;
 else if(rezalt > 0)
  noderoot = nodecurr->right;
 else
  return;
}
if(resalt < 0)
 nodecurr->left = new BinUzel(v);
else
 nodecurr->right = new BinUzel(v);

}

теоретически примерно вот так. Приведи его в соответствие со своим кодом, так как писал сходу, мог гдето чего напутать.
14K
28 ноября 2005 года
Rockie
6 / / 21.11.2005
Спасибо, kot_! =) Единственное что ты напутал это resalt и rezalt =)Код полностью рабочий, может чуть позже выложу что в итоге получилось
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог