Drzewo BST, inorder, struktura- HELP!!!

Odpowiedz Nowy wątek
2005-08-17 17:37
sprzatacz
0

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=2
i+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=2
i+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;
}

Pozostało 580 znaków

2005-08-17 23:33
0
sprzatacz napisał(a)

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?).

Kod powinien wyglądać tak:

void inorder(node *temp)
{
  if(!temp)return;

  inorder(temp->left);
  wypisz(temp);
  inorder(temp->right);
}

a wywołujesz go tak:

int main(int argc, char* argv[])
{
        printf("cos\n");

        Add(8);
        Add(10);
        Add(2);
        Add(1);
        Add(12);
        Add(3);
        Add(11);

        inorder(root);
        return 0;
}

Jest jeszcze iteracyjny (w / /). Początek niby dobry- korzeń, potem do skrajnego lewego, tylko co dalej?

Jeżeli sposób iteracyjny nie jest konieczny to daruj go sobie ;)

Pozostało 580 znaków

2005-08-18 17:20
sprzatacz
0

Działa. Dzięki!!!!

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0