добавление в Бинарное Дерево
#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();
}
подскажите пожалуйста где я запутался.
Узел дерева имеет 4 точки отсчета - не учитывая this - право-лево, верх-низ. Здесь ты собственно и запутался. кроме лево-право, узел должен иметь ниже-выше (или перед-после, кому как нравится. :) )
Соответственно оператор = надо перегрузить.
кроме лево-право, узел должен иметь ниже-выше (или перед-после, кому как нравится. :) )
Kot_ , а чтоя буду с этими указателями ниже выше делать? У Бинарного дерева указатели на меньший элемент и на больший. Если передаваемое значение уже есть в дереве, вставка не происходит. Дерево сразу упорядоченное, так как при вставке звена сразу определяется левее или правее его добавить. Потом при добавлении следующего опять смотрится левее или правее, начиная с корня. то есть добавляется только концевой узел. По-моему , в этом случае можно обойтись только left и right указателями.
За идею с перегрузкой спасибо
Kot_ , а чтоя буду с этими указателями ниже выше делать? У Бинарного дерева указатели на меньший элемент и на больший. Если передаваемое значение уже есть в дереве, вставка не происходит. Дерево сразу упорядоченное, так как при вставке звена сразу определяется левее или правее его добавить. Потом при добавлении следующего опять смотрится левее или правее, начиная с корня. то есть добавляется только концевой узел. По-моему , в этом случае можно обойтись только left и right указателями.
За идею с перегрузкой спасибо
Да ты прав. В двоичном дереве достаточно левоправых указателей. Тебе необходимо в классе дерева определить функцию сравнения элементов,и добавления узла тогда твоя функция вставки приблизительно будет выглядеть так:
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);
}
теоретически примерно вот так. Приведи его в соответствие со своим кодом, так как писал сходу, мог гдето чего напутать.