Question

Write an algorithm and program that accept a tree as input and convert it into binary tree. Binary tree should be printed to standard output.

Answer 1

a.[Initialize]

HEAD <-- NODE

LPTR(HEAD) <-- NULL

RPTR(HEAD) <-- HEAD

LEVEL[1] <-- 0

LOCATION TOP <-- 1.

b.[Process the input]

Repeat

c.[Input a node]

Read(LEVEL,INFO).

d.[Create a tree node]

NEW <-- NODE

LPTR(NEW) <-- RPTR(NEW) <-- NULL

DATA(NEW) <-- INFO.

e.[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.

f.[Pushing values in stack]

TOP <-- TOP + 1

LEVEL[TOP] <-- LEVEL

LOCATION[TOP] <-- NEW.

g.[FINISH]