Write an algorithm and program that accepts a tree as input and converts it into a binary tree
Answers
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.