parsing a tree

[mank]

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.

[doublex]

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

[Narue]

>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 *link[2];
};

struct node *insert ( struct node *root, int data )
{
  if ( root == NULL ) {
    root = malloc ( sizeof *root );
    root->data = data;
    root->link[0] = root->link[1] = NULL;
  }
  else if ( root->data == data )
    return root;
  else {
    int dir = root->data < data;
    root->link[dir] = insert ( root->link[dir], 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.