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.

Attachments parse_tree.JPG 4.54 KB

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 *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.

Comments
cute!
This article has been dead for over six months. Start a new discussion instead.