Logo 
Search:

C++ Programming FAQ

Submit Interview FAQ
Home » Interview FAQ » C++ ProgrammingRSS Feeds

Write an algorithm for converting a general tree to a binary tree in dfs (data file structure).

  Shared By: Michael Evans    Date: Apr 29    Category: C++ Programming    Views: 4665

Answer:

PROCEDURE CONVERT
[Given a forest of trees, it is required to convert this forest into an equivalent binary tree with a list head (HEAD)].

1. [Initialize]

HEAD <-- NODE
LPTR(HEAD) <-- NULL
RPTR(HEAD) <-- HEAD
LEVEL[1] <-- 0
LOCATION TOP <-- 1.

2. [Process the input]

Repeat thru step 6 while input is there.

3. [Input a node]

Read(LEVEL,INFO).

4. [Create a tree node]

NEW <-- NODE
LPTR(NEW) <-- RPTR(NEW) <-- NULL
DATA(NEW) <-- INFO.

5. [Compare levels]

PRED_LEVEL <-- LEVEL[TOP]
PRED_LOC <-- LOCATION[TOP]
if LEVEL > PRED_LEVEL
then LPTR(PRED_LOC) <-- NEW
else if LEVEL = PRED_LEVEL
RPTR(PRED_LOC) <-- NEW
TOP <-- TOP – 1
else
Repeat while LEVEL != PRED_LEVEL
TOP <-- TOP – 1
PRED_LEVEL <-- LEVEL[TOP]
PRED_LOC <-- LOCATION[TOP]
if PRED_LEVEL <-- LEVEL
then write (“Invalid Input”)
return



RPTR(PRED_LOC) <-- NEW
TOP <-- TOP – 1.

6. [Pushing values in stack]

TOP <-- TOP + 1
LEVEL[TOP] <-- LEVEL
LOCATION[TOP] <-- NEW.

7. [FINISH]
return.

Share: 
 


Related Topics:

Your Comment
  • Comment should be atleast 30 Characters.
  • Please put code inside [Code] your code [/Code].


Tagged: