Logo 
Search:

C++ Programming FAQ

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

Write an algorithm for Inserting a node from a Binary Tree in dfs (data file structure).

  Shared By: Lurleen Fischer    Date: Oct 17    Category: C++ Programming    Views: 3805

Answer:

PROCEDURE TREE_INSERT(HEAD,X,Y)
[Given a binary tree whose root node address is given by the pointer value HEAD and the information value (X) of the node marked for insertion, this procedure inserts the node (Y) whose information field is equal to X].

1. [Initialize]

If LPTR(HEAD) != NULL
then CUR <-- LPTR(HEAD)
PARENT <-- HEAD
else
write (“Empty tree”)
return.

2. [Traverse to the destination node]

FOUND <-- false
Repeat while not FOUND and CUR != NULL
if X = DATA(CUR)
FOUND <-- true
else if X > DATA(CUR)
then (branch right)
PARENT <-- CUR
CUR <-- RPTR(CUR)
D <-- ‘R’
else
then (branch left)
PARENT <-- CUR
CUR <-- LPTR(CUR)
D <-- ‘L’
if FOUND = false
then write (“Node not found”)
return.

3. [Performing the insertion]

If LPTR(CUR) = NULL
DATA(LPTR(CUR)) <-- Y
else if RPTR(CUR) = NULL
DATA(RPTR(CUR)) <-- Y
else
TEMP <-- LPTR(CUR)
LPTR(CUR) <-- NEW
LPTR(NEW) <-- TEMP.

4. [FINISH]
return.

Share: 
 


Related Topics:

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


Tagged: