File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
A friendly place for programming greenhorns!
Big Moose Saloon
Register / Login
Win a copy of
The Mikado Method
this week in the
Agile and other Processes
Java in General
Constructing a binary tree from its traversals
Joined: May 21, 2008
Oct 19, 2008 20:51:00
Firstly, thanks to everyone for answering my previous topics, my assignment is going really well. I'm now on part 2, and I need to construct a binary tree from its post-order and in-order traversals. The sample traversals given were:
Inorder traversal: ADHGKLMRUVTW
Postorder traversal: AHDLKGUVRWTM
Can someone please help me with the algorithm to complete this process?
Joined: Jan 01, 2007
Oct 19, 2008 23:21:00
I will give you a clue from which you can deduce the algorithm easily
[B]Inorder traversal: ADHGKLMRUVTW Postorder traversal: AHDLKGUVRWTM Notation: (Left Subtree) root (Right Subtree) Postorder traversal: AHDLKGUVRWTM <-------Traverse this way-------- Work on Inorder traversal while travesring Postorder traversal (ADHGKL) M (RUVTW) (ADHGKL) M ((RUV) T (W)) (ADHGKL) M ((R(UV)) T (W)) (ADHGKL) M ((R((U)V)) T (W)) ((ADH)G(KL)) M ((R((U)V)) T (W)) ((ADH)G(K(L))) M ((R((U)V)) T (W)) (((A)D(H))G(K(L))) M ((R((U)V)) T (W))[/B]
Thanks and Regards
Joined: May 21, 2008
Oct 20, 2008 20:00:00
Hey thanks for the reply. I can't say that your "clue" helped me very much, I already had the tree, but I should have mentioned that. But I managed to get it in the end, so thanks anyway!
Joined: Oct 13, 2005
Oct 21, 2008 01:41:00
How did you do it? Other people can learn from your example.
I agree. Here's the link:
- if it wasn't for jprofiler, we would need to run our stuff on 16 servers instead of 3.
subject: Constructing a binary tree from its traversals
Is it possible to generate Binary Tree from the expression given in Inorder?
When do i say that a binary search tree is unique?!
tree datastructure algorithm
Jquery: Target column text
Recursive / Non-Recursive Function
All times are in JavaRanch time: GMT-6 in summer, GMT-7 in winter
| Powered by
Copyright © 1998-2013