[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

Help required in a traversal program

Posted on 2006-05-20
3
Medium Priority
?
222 Views
Last Modified: 2010-04-15
I need to write a program in ‘C’ language that could accept inorderr and pre-order traversal outputs of a Binary Tree as input and prints the corresponding Binary tree.

0
Comment
Question by:swtirs
  • 2
3 Comments
 
LVL 45

Accepted Solution

by:
sunnycoder earned 1500 total points
ID: 16725371
What is the help required?

This sounds very much like homework and Membership Agreements fobids posting solutions to homework questions ... If you have some specific query, post here and we will be glad to help but we cant solve the entire problem for you ...

Here are some hints to get you started::

Assume
inorder = g d h b e i a f j c
preorder = a b d g h e i c f j
                ^
Scan the preorder left to right using the inorder to separate left and right subtrees.
a is the root of the tree; gdhbei are in the left subtree; fjc are in the right subtree.

preorder = a b d g h e i c f j
                 ^^
b is the next root; gdh are in the left subtree; ei are in the right subtree.

preorder = a b d g h e i c f j
                 ^^^
d is the next root; g is in the left subtree; h is in the right subtree.

The basic idea hence is ... The first node in preorder traversal is the root ... The nodes on the left of this node in inorder traversal form its left subtree and nodes to the right in inorder traversal form the right sub-tree ...

This algorithm can be recursively applied to each subtree!!

Cheers!
sunnycoder
0
 
LVL 16

Expert Comment

by:PaulCaswell
ID: 16725375
Hi swtirs,

1. Could you clarify 'inorder' and 'pre-order'. I think I know what you mean but just to clarify.

2. What form do you want the output in?

Paul
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 16725383
Hi Paul,

1.
http://en.wikipedia.org/wiki/Tree_search_algorithm

2.
Beware, this is common problem in data structures/ advanced data structures course

Cheers!
sunnycoder
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.
Suggested Courses

872 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question