Logo 
Search:

C++ Programming FAQ

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

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

  Shared By: Idelia Miller    Date: Mar 05    Category: C++ Programming    Views: 3564

Answer:

PROCEDURE TREE_DELETE(HEAD,X)
[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 deletion, this procedure deletes the node 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. [Search the node which is marked for deletion]

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 deletion]

If LPTR(CUR) = NULL
Q <-- RPTR(CUR)
else if RPTR(CUR) = NULL
Q <-- LPTR(CUR)
else (check right child is inorder successor or not)
SUC <-- RPTR(CUR)
if LPTR(SUC) = NULL
then Q <-- SUC
else
repeat while LPTR(SUC) != NULL
PRED <-- SUC
SUC <-- LPTR(PRED)
Q <-- SUC
LPTR(PRED) <-- RPTR(SUC)
LPTR(Q) <-- LPTR(CUR)
RPTR(Q) <-- RPTR(CUR)
if D = ‘L’
LPTR(PARENT) <-- Q
else
RPTR(PARENT) <-- Q.

4. [FINISH]
return.

Share: 
 


Related Topics:

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


Tagged: