Building Binary Trees

Given the preorder and inorder traversal of a binary tree of N nodes, what is the code to create the binary tree?  (pointer-based please)
Who is Participating?

Commented:
I made a simple program to make a binrary tree from its preoder and inorder traversal, pls check it.
(I use vc6)

#include <stdio.h>
#include <Stdlib.h>

typedef struct node
{
int value;
struct node * left, * right;
} Node, * PNode;

char PreOrder[] = "ABDEGCFHI";                        // 9 nodes tree
char InOrder[]  = "DBGEACHFI";
int scan = 0;

int find(int from, int to, char ch)
{
int i;

for (i=from;i<=to;i++)
if (InOrder[i]==ch)
return i;

return -1;
}

void step(int left, int root, int right, PNode * parent)
{
int pos;
PNode p = new Node;

p->value = InOrder[root]; p->left = p->right = NULL;
* parent = p;

if (0 != left)
{
pos = find(root - left, root - 1, PreOrder[scan]);
if (-1 == pos)
{
printf("Input error");
exit(-1);
}
else
{
scan ++;
step(left - (root - pos), pos, root - pos - 1, &(p->left));
}
}

if (0 != right)
{
pos = find(root + 1, root + right, PreOrder[scan]);
if (-1 == pos)
{
printf("Input error");
exit(-1);
}
else
{
scan ++;
step(pos - root - 1, pos, right - (pos - root), &(p->right));
}
}
}

void main()
{
int pos;

pos = find(0, 8, PreOrder[scan]);
scan ++;
step(pos , pos, 8 - pos, &head);
}
0

Commented:
You'll need to have more to go on.

If you ask this question like this, you'd be getting trees of which only the left branches are filled.

A tree can have many forms, while the preorder and inorder traversals still stay the same.
0

Commented:
no, if u give any two of the three order of a tree, this tree is unique, and there is a standard recursion method to make the whole tree from these two order.
0

Commented:
The tree is ((DB(GE-))A(-C(HFI)))
0

Commented:
yz, This is a C++ question, why not try some C++ code.
0

Commented:
which code can be called C++ code? use class ? use iostream ? can u tell me? I feel some confused.
0

Commented:
It was just that the program you presented is pure C. A class or two would be  nice.
0

Commented:
? why give me a C ? does my code goes something wrong ? Please tell me and let me to gain progress.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.