Menu
How can I construct a tree given its inorder and preorder traversal? I am just looking for an efficient algorithm.
490
Create a new tree node tNode with the data as the picked element. Find the picked element's index in Inorder. Let the index be inIndex. Call buildTree for elements before inIndex and make the built tree as a left subtree of tNode.
Yes it is possible to construct a binary search tree from an inorder traversal. Observe that an inorder traversal of a binary search tree is always sorted. There are many possible outcomes, but one can be particularly interested in producing a tree that is as balanced as possible, so to make searches in it efficient.
A blatant copy and paste from Sun's (Oracle now, I guess...) forum:
Question:
Can anybody help me on how to construct Binary tree from inorder and postorder traversals,i just want to know the algorithm so that i can apply it.Answer:
Letp_1,p_2...p_nbe the postorder traversal and leti_1,i_2...i_nbe the inorder traversal. From the postorder traversal we know that the root of the tree isp_n. Find this element in the inorder traversal, sayi_1,i_2...i_k-1p_ni_k+1...i_n. From the inorder traversal we find all the elements in the left subtree, i.e.i_1,i_2...i_k-1and in the right subtree, i.e.i_k+1...i_nrespectively.Remove element
p_n(and elementi_k==p_n). Find the rightmost elementp_jinp_1,p_2...p_j...p_n-1wherep_jis an element ini_1,i_2...i_k-1. This is the root of the left subtree of the original tree. Splitp_1,p_2...p_jandp_j+1...p_n-1andi_1,i_2...i_k-1andi_k+1...i_n. Now you have two subsequences representing the postorder and inorder traversal of the two subtrees of the original tree.
Author: JosAH.
I've implemented the algorithm once following Jos' instructions, and it worked perfectly!
151
Since this is homework, I won't give you a full answer, but hopefully, enough to get you moving.
Imagine you have preorder traversal of, say this tree.
The traversal gives you 2-7-2-6-5-11-5 ... etc. Notice that the 5 is actually the right child of the root.
Obviously, you can't tell that from just looking at the numbers, so either you will be told about the structure of the tree, or you need to store some additional data (ie, whether the a node is the left child or right child, for example).
Parsing the tree is simply a recursive function that takes the preorder traversal as input (think about your scope when you are passing the input). As I mentioned earlier, your preorder traversal should have some additional data attached.
Efficiency:
consider how many times each node is visited when you build this tree, but also consider the operation of reading the input. Is there a way to reorganize the input faster than you can build the tree? What structure would you have to use if you need to manipulate the data.
In Order: You will need the same idea to get you through it, so I won't cover it. I'm sure someone else will, if you are desperate for it.
23
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
