Xref: utzoo comp.sources.wanted:10855 comp.lang.pascal:3195 comp.lang.c:26657
Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!swrinde!emory!hubcap!ncrcae!ncrlnk!adds!tanya
From: tanya@adds.newyork.NCR.COM (Tanya Katz)
Newsgroups: comp.sources.wanted,comp.lang.pascal,comp.lang.c
Subject: Binary tree generation from transveral strings
Keywords: General tree binary tree  transversal
Message-ID: <1269@adds.newyork.NCR.COM>
Date: 6 Mar 90 19:13:54 GMT
Organization: Applied Digital Data Systems Hauppauge, NY
Lines: 41


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 |
+------------------------------------------------+