I want to parse a tree
the tree is like (((1,2)3,4)5,6)
see the attached parse tree
the program would produce an array from root to each leaf
[IMG]http://aycu25.webshots.com/image/35944/2002642992068581724_th.jpg[/IMG]

So I would like to have 4 arrays

``````a[]={5,3,1}
b[]={5,3,2}
c[]={5,4}
d[]={6}``````

I would like to have a general format that would produce such arrays for any given parse tree.

i think you can use a backtracking algorithm. i don't have time to write some code, but you get the idea.

you will need a linked list instead of arrays, for better memory usage. every element in the list will be another list containing a sequence like those in the arrays

>I would like to have a general format that would
>produce such arrays for any given parse tree.
It looks fairly simple. Just recursively traverse the tree and save the paths as you go:

``````#include <stdio.h>
#include <stdlib.h>

struct node {
int data;
};

struct node *insert ( struct node *root, int data )
{
if ( root == NULL ) {
root = malloc ( sizeof *root );
root->data = data;
}
else if ( root->data == data )
return root;
else {
int dir = root->data < data;
}

return root;
}

void get_paths ( struct node *root, int depth )
{
static int path[100] = {0};

if ( root == NULL ) {
int i;

for ( i = 0; i < depth; i++ )
printf ( "%d,", path[i] );
puts ( "\b " );
}
else {
path[depth] = root->data;
get_paths ( root->link[0], depth + 1 );
get_paths ( root->link[1], depth + 1 );
}
}

void dump_r ( struct node *root, int level )
{
int i;

if ( root == NULL ) {
for ( i = 0; i < level; i++ )
putchar ( '\t' );
puts ( "~" );
}
else {
dump_r ( root->link[1], level + 1 );

for ( i = 0; i < level; i++ )
putchar ( '\t' );
printf ( "%d\n", root->data );

dump_r ( root->link[0], level + 1 );
}
}

void dump ( struct node *tree )
{
dump_r ( tree, 0 );
}

int main ( void )
{
struct node *tree = NULL;

tree = insert ( tree, 5 );
tree = insert ( tree, 6 );
tree = insert ( tree, 3 );
tree = insert ( tree, 4 );
tree = insert ( tree, 1 );
tree = insert ( tree, 2 );
dump ( tree );
get_paths ( tree, 0 );

return 0;
}``````

There are a few implementation issues, so that doesn't do exactly what you want, but it should give you an idea of how to proceed.

commented: cute! +13
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.