[comp.lang.pascal] Binary tree generation from transveral strings

tanya@adds.newyork.NCR.COM (Tanya Katz) (03/07/90)

Does anyone have an algorithm (or a reference to one)
that creates a unique binary tree from the prefix & postfix 
transversal strings of a general tree?

Given the prefix & postfix transversal of a general tree, you are
supposed to be able to generate a unique binary tree. The infix 
transversal string of this binary tree equals the postfix string 
of the general tree.  This can be done recursively, I am told. 

eg:  
General tree definition:
Prefix string:  abdgcehif
Postfix string:	gdbhiefca  = Infix string of binary tree

binary tree:
		  a
	         /
		b
	       / \
	      d   c
             /   / 
            g   e
	       / \
	      h   f
	       \
		i

Any help would be appreciated.  Ideas/pseudo code, 'C', Pascal... help...

-Tanya


+------------------------------------------------+
| Tanya Katz                  (516)231-5400 x430 |
|                                                |
|          ...uunet!ncrlnk!adds!tanya            |
|         tanya.katz@adds.newyork.ncr.com        |
|                                                |
| ADDS Inc, 100 Marcus Blvd, Hauppauge, NY 11788 |
+------------------------------------------------+