Question

Write algorithm and program that accepts any Tree as Input and
Converts it into Binary Tree.

Answer 1

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.