Don't know where to begon

[degamer106]

OK.......right now i'm learning about binary tree traversal and this problem looks like a total killer to me. Here's it is:

Write a program that takes as input the preorder and inorder traversals of a binary tree, and produces as output the level-order traversal of the tree.

All i gotta say to that is :eek:

I've built a skeleton of the program and so far I've been able to take the preorder traversal of a tree as input and generate the original tree. As for inorder, I really have no clue what to do :sad:

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

#define SIZE 50

typedef struct node *link;

struct node {
	int item;
	struct node *link[2];
};

link make_node(int data)
{
	link x = (link)malloc(sizeof *x);
	x->item = data;
	x->link[0] = NULL; x->link[1] = NULL;
	return x;
}

link make_tree(link root, int data)
{
	if (root == NULL)
		root = make_node(data);
	if (root->item == data)
		return root;
	else
	{
		int dir = root->item < data;
		root->link[dir] = make_tree(root->link[dir], data);
	}
	return root;
}

void disp_tree(link tree, int level)
{
	int i;

  if ( tree == NULL ) {
    for ( i = 0; i < level; i++ )
      printf ( "\t" );
    printf ( "~\n" );

    return;
  }

	disp_tree ( tree->link[1], level + 1 );

  for ( i = 0; i < level; i++ )
    printf ( "\t" );
  printf ( "%d\n", tree->item );

	disp_tree ( tree->link[0], level + 1 );
}

/*
static int N, head, tail;
struct node *q[50];

void put(link item) 
{
	q[tail++] = item;
	tail = tail % N;
}

link get() 
{
	head = head % N;
	return q[head++];
}
*/
// preorder
void preorder(link root, int a[])
{
	while (*a != 0)
	{
		make_tree(root, *a);
		a++;
	}

	disp_tree(root, 1);
}
// inorder
void inorder()
{}

int main(void) 
{
	int num;
	puts("1: Preorder Traversal");
	puts("2: Inorder Traversal");
	puts("Enter your choice:");
	scanf("%d", &num);
	fflush(stdin);

	int i = 0, j = 0, val[SIZE] = {0};
	char trav[SIZE];
	puts("Enter the traversal order");
	fgets(trav, SIZE, stdin);
	while (isdigit(trav[i]))
	{
		val[j++] = 10*val[i] + (trav[i++]-'0');		
		while (trav[i] == ' ') 
			i++;
	}

	if (num == 1) 
	{
		link root = make_node(val[0]);
		preorder(root, val);
	}
	else 
		inorder();

	return 0;
}

[iamthwee]

>As for inorder, I really have no clue what to do

You mean you don't know how inorder traversal would look or you don't know how to code it?

Inorder
1. Traverse the left subtree
2. Visit the root
3. Traverse the right subtree

That's the basic idea...

[degamer106]

No that's not what I meant. I'm supposed to change an inorder traversal into the original binary tree and then produce a level order traversal. Sorry for any misunderstanding.

[iamthwee]

Well if the user explicitly gives you the preorder and inorder traversals of a binary tree, then recovery of the original binary can be done like thus:

Clearly the first element in the preorder is the root. We can then search for this element in the inorder traversal. The elements of the tree are now uniquely partitioned into left and right subtrees by this element. (ie., the subsequence of elements preceding the root in the inorder sequence is the inorder sequence for the left sub-tree and similarly the subsequence of elements succeeding the root is the inorder sequence for the right sub-tree) We can then recursively construct the left and right sub-trees from the preorder and inorder subsequences.

And Once we have the original binary tree, then we can use the Al-Gore-it-him for level-traversal which is well documented on the web me thinks.

[ricky0161]

I Agree With Iamthwee

[degamer106]

Well if the user explicitly gives you the preorder and inorder traversals of a binary tree, then recovery of the original binary can be done like thus:

And Once we have the original binary tree, then we can use the Al-Gore-it-him for level-traversal which is well documented on the web me thinks.

Oo that seems to make a bit more sense. Where did you get that quote btw?