Browse a tree

[Iskandaar]

Hello first sorry for my english I'm French !

I have a question I want to store values of my tree in a table in ascending order but first I just want to store all the values.
Could you help me with that ?

  int i=0;
    noeud *a=r; //noeud are nodes and r are the racine
    noeud *b=r;
    while(a->fg!=NULL) // fg = left son
    {
        T[i]=a->cle; // cle = key (value of the nodes) and T is the table
        i++;
        if(a->fd!=NULL) // fd = right son
        {
            b=a->fd;
            T[i]=b->cle;
        }
        a=a->fg;
    }

[jonnin]

Is the tree sorted already?
usually trees are done with recursion; it is tricky to write a loop to do it.
in pseudo code..

for a tree 
a
/\
b c
    \ 
      d
it prints a b c d
void foo(tree)
{
    if(!tree) return;
     cout << tree.value << endl;
    foo(tree->left);
    foo(tree->right;
}

if its sorted you need to arrange the above to get the values in your sorted order to load the vector. If its not sorted, sort the vector after loading.

[Iskandaar]

Thanks for you answer no the tree is not sorted and also I can't change the prototype of my function my professor don't want.

Also I cannot use vector only a table the .h is imposed by my professor look at it :

class noeud{
	public:
	int cle;
	noeud* fg;
	noeud* fd;
	noeud* pere;
	noeud(int x);
	noeud(int x, noeud* fg, noeud* fd);
	~noeud();
	void Affiche(noeud* x);
};

class AB{
	noeud* r;
	int T[50];
	int n; 	

	public :
	AB(noeud* x);
	~AB();
	noeud* root();
	void AfficheT();
	void Prefixe(noeud* x);
	void Infixe(noeud* x);
	void Postfixe(noeud* x);
	int Hauteur(noeud* x);
	int N(noeud* x);
	void Tri();
	void ABtoABR(noeud* x);
};

[dutch]

void fill_table(Node *root, int table[], int& i) {
    if (!root) return;
    fill_table(root->left, table, i);
    table[i++] = root->key; // infix position
    fill_table(root->right, table, i);
}

int table[100], n = 0;
fill_table(root, table, n);

Then you can sort the table, if necessary.

[Iskandaar]

Thanks you dutch,

I'm trying your function like this :

void AB::fill_table(noeud *root, int table[], int& i) {
    if (!root) return;
    fill_table(root->fg, table, i);
    table[i++] = root->cle; // infix position
    fill_table(root->fd, table, i);
}


void AB::Tri()
{
    int i=0;
    fill(r,T,i);
}

But I don't know why is not working could you help me with that ?
The error is no matching function for call to fill(...)

[dhayden]

You've defined function fill_table() and you're calling function fill(). Function fill is not defined.

Change line 12 to fill_table(r,T,i);

[Iskandaar]

Thanks you dhayden it's working now !

Now I want to sort my table T but when I'm doing this it doesn't change anything

void AB::Tri()
{
    int i=0;
    fill_table(r,T,i);
    //sort(T,T+n); // This doesn't work so I'm trying to sort myself but it's doesn't working also.
    int temp;
    for(int i=0;i<n;i++)
	{		
		for(int j=i+1;j<n;j++)
		{
			if(T[i]>T[j])
			{
				temp  =T[i];
				T[i]=T[j];
				T[j]=temp;
			}
		}
	}
    
}

[jonnin]

use sort().
you have the syntax correct, so check n to ensure it is what you think it should be.
n should be the true size of the array or part you want to sort, eg
int x[10]
sort that with
sort(x, x+10)

n should have been incremented every time you added an item to your array, if you forgot this it will still be zero, and that will do nothing in the sort call...

[Iskandaar]

Thanks jonnin ! Now it's working thanks to you !

The second problem(sorry to bother you all) is to transform my binary tree to a binary search tree

void AB::ABtoABR(noeud* x) //I cannot change this prototype
{
    int i;
    if(!x) return
    ABtoABR(x->fg); //fg = left child
    x->cle=T[i]; // cle is the key (value)
    i++;
    ABtoABR(x->fd); //fd = right child
}

[jonnin]

the only difference is how you store the data.
you change your insert into the tree routine to follow this simple rule, starting at the root: if its less than the current node's sort key value, recursively go left, else go right. (If tree is empty, just put it at root, of course). Then you search the same way: is the item you are looking for less than (go left) or greater (go right) or equal (found it).
note that without some extra routines (balance routine or an advanced type of tree that self balances) the order you insert the data matters; for example if you insert 1,2,3,4 you will get a linked list, not a tree, but if you insert 2,3,1,4 you will get a decent search tree (do this on paper, see what I am saying!).

[Iskandaar]

Like this ?

void AB::ABtoABR(noeud* x)
{
    int i=0;
    if(T[i]<x->cle)
    {
        x->fg->cle=T[i];     // x->leftchild->key=T[i]
        i++;
        ABtoABR(x->fg);
    }
    else
    {
        x->fd->cle=T[i];  // x->rightchild->key=T[i]
        i++;
        ABtoABR(x->fd);
    }
}

[jonnin]

probably not. each recursive copy of the function resets i to zero (if you want to retain the value, it should be static, but attempting to mush the tree insert and the array iteration together looks dangerous/bug prone to me). This does not look right, but it may be, I can't honestly tell without time studying your code that I do not have right now.

if it were me, I would do it explicitly in distinct chunks:
for(i = 0; i < tsize; i++)
insert into tree (T[i]) //this can be named whatever, I am using words to explain not real code.

insert into tree function, then:
if null, insert here
if less than here, insert into tree->left
else
insert into tree tree->right

what it does:
it does recursion until it hits a null, and it inserts there. The logic sorts it, and because its a tree, you only need to search the height to find an item, making it on par with binary search.

not sure about what order you want to do things in.
you can get your data, put it into the array, sort it and insert it. To do that, insert from the center out of the sorted array, eg 1234567 you pick 4 (middle value) then insert 3 and 5, then 2 and 6, then 1 and 7 ... like that.

you can get your data, insert into sorted tree, and then use the correct traversal to load the array, and it will be sorted for you.

you should not be loading 2 trees, one sorted and one not, though, unless its for demonstration purposes. Figure out what you have and what you want to produce, and avoid unnecessary middle steps as much as you can (again, if you need the middle steps for a classroom problem, that is what it is).

[Iskandaar]

Thanks you for you reply jonnin !

I'm totally lost i'm trying everything but it don't want to work if anyone have a clue
for how with a table do a Binary tree search !

Thank you in advance !

[jonnin]

say carefully what it is you want to do, exactly.
you can search a sorted table with a binary search (what you said above, which is unlike what you have been saying so far), or you can make a search tree, which does the binary search by design.

Also you may need to post your latest code, what you have been trying, as the above is several days old and you have been editing it a lot since then?

If its the tree, I don't know how to say it any clearer...
make the insert as described above. Add the data to the tree, and avoiding loading it in sorted order (either acending or decending, both are no good).