Witam.
Specjalistą od C++ nie jestem, dlatego nie mogę sobie poradzić z poniższym problemem.
Program ma tworzyć niezrównoważone drzewo BST i przeszukiwać je poprzecznie (inorder). Żeby móc spawdzać, czy nowe węzły z liczbami są na swoim miejscu, zrobiłem prosty sposób indeksowania- schemat niżej (liczba oznacza nr indeksu):
1
2 3
4 5 6 7
W main() jest już kilka wartości, wypisz() podaje wartość elementu, wypisz2() jego indeks, spr() wywołuje wypisz() i wypisz2() oraz służy do "poruszania się" po drzewie. Program kompiluje się bez problemu w Visual C++. Niestety, kiedy zamiast liczby 9- Add(9); w main() podam Add(11); program się krzaczy- bo "11" nie ma, gdzie się wcisnąć. Kolejny problem to inorder. Niby są 2- iteracyjny i rekurencyjny. Jeśli chodzi o rekurencyjny, nie wiem jak go wywołać w main()- jest w /* /. Poza tym nie wiem, czy to wystarczy (taki krótki?). Jest jeszcze iteracyjny (w / */). Początek niby dobry- korzeń, potem do skrajnego lewego, tylko co dalej? Rozumiem zasadę funkconowanie tego przeszukiwania, ale rozumieć to jedno, a zaimplementować to drugie (szukałm już gotowych implementacji, ale dla mnie to kosmos- np. w ftp.helion.pl, plik calstr.zip, genBST.h).
Poniżej moje wypociny- może znajdzie się jakiś cudotwórca, który mi pomoże
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <iostream.h>
struct node
{
int index;
int value;
node *left,*right;
node *parent;
};
node *root;
void Add(int x)
{
int i=1;
node new_node;
new_node = new node;
new_node->value=x;
new_node->left=NULL;
new_node->right=NULL;
if(!root)
{
root=new_node;
new_node->index=1;
new_node->parent=NULL;
return;
}
node temp=root;
while ( ( (temp->value>x) && (temp->left) ) ||
( (temp->value<x) && (temp->right) ) )
{
if (temp->value>x)
{
temp=temp->left;
i=2i;
}
else
{
temp=temp->right;
i=2i+1;
}
}
if (temp->value>x)
{
new_node->parent=temp;
temp->left=new_node;
i=2i;
}
else
{
new_node->parent=temp;
temp->right=new_node;
i=2i+1;
}
new_node->index=i;
}
void wypisz2(node *x)
{
cout<<"\t"<<x->index;
cout<<"-index";
}
void wypisz(node *x)
{
cout<<"\n"<<x->value;
cout<<"cos";
}
//-----------------------------------------------------------------
//inorder rekurencyjny
/*void inorder(node temp)
{
if (!temp)
{
inorder(temp->left);
wypisz(temp);
inorder(temp->right);
}
}/
//-----------------------------------------------------------------
//inorder iteracyjny
/*int inorder()
{
node *temp=root; //------------------jestesmy w korzeniu--------
if (!temp) return 0; else
while (temp)
{
while (temp->left) //----------idziemy do skrajnego lewego-
temp=temp->left;
wypisz(temp);
wypisz2(temp);
while(temp->right)
{
temp=temp->parent;
wypisz(temp);
wypisz2(temp);
}
//if (temp)
// temp=temp->right;
}
return 1;
} */
//-----------------------------------------------------------------
int spr()
{
node *temp=root;
if (!temp) return 0; else
wypisz(temp);
wypisz2(temp);
temp=temp->right;
wypisz(temp);
wypisz2(temp);
temp=temp->parent;
temp=temp->left;
wypisz(temp);
wypisz2(temp);
temp=temp->left;
wypisz(temp);
wypisz2(temp);
temp=temp->parent;
temp=temp->right;
wypisz(temp);
wypisz2(temp);
temp=temp->parent;
temp=temp->parent;
temp=temp->right;
temp=temp->left;
wypisz(temp);
wypisz2(temp);
return 1;
}
void main()
{
printf("cos\n");
Add(8);
Add(10);
Add(2);
Add(1);
Add(12);
Add(3);
Add(9); //----jak damy 11 zamiast 9, krzaczy sie----
spr();
// inorder();
//return 0;
}