Erasing a Leaf from a Binary Tree

 

 

A binary tree is a virtual tree which has downward leafs. Lower-left leaf's position is calculated by (2*k) and lower-right position is (2*k+1).  These trees are widely used in database systems and compression algorithms.
 

 

 

 

 

 

 

Erasing a leaf from a virtual tree is always a problem. You can not just erase a leaf without considering the lower leafs. A pseudo-code of the solution and source code for this problem can be followed below.

 

        1. Find the place of input X by binary searching.

        2. Erase input X from tree.

        3. Find lower leafs if exist and place them in an array.

        4. Add each array element into binary tree.

 

  

 

Pascal Source Code

 

{
    This program erases a leaf X from a given virtual tree and re-generates the virtual tree.
}
uses crt;
type
    dizi=array[1..200] of integer;
    rec = record
     sayi:integer;
     yer :integer;
    end;
    reco=array[1..50] of rec;
var
  A:dizi; n:integer; B:reco; ch:char;
 
Procedure Read_Array(var n:integer;var A:dizi);
var i,k:integer;
begin
 write('Input the size of tree array: ');readln(n);
 writeln('Input the elements of tree...');
 k:=0;
 for i:=1 to n do
  begin
   gotoxy(1+k,3);
   read(a[i]); k:=k+3;
  end;
 writeln;
end;
 
Procedure Add_To_Tree(x:integer;var n:integer;var A:dizi);
var i:integer;
Begin
 i:=1;
 while (i<=n)and(A[i]<>0) do
  if x>A[i] then i:=i+i+1
      else i:=i+i;
 A[i]:=x;
 if i>n then n:=i;
End;
 
Procedure Erase_From_Tree(var n:integer;var A:dizi);
var i,j,l,x,v:integer;
Begin
 write('Enter the number to be erased:');readln(x);
 i:=1;
 while (i<=n)and(A[i]<>x) do
  if x>A[i] then
    i:=i+i+1
   else
    i:=i+i;
 if x=A[i] then
  begin
   A[i]:=0;
   j:=0;
   if A[i+i]<>0 then
     begin
      inc(j);
      B[1].sayi:=A[i+i];
      B[1].yer:=i+i;
      A[i+i]:=0;
     end
    else if A[i+i+1]<>0 then
     begin
      inc(j);
      B[2].sayi:=A[i+i+1];
      B[2].yer:=i+i+1;
      A[i+i+1]:=0;
     end;
   if j<>0 then
     begin
      v:=1;
      while v<=j do
       begin
        l:=B[v].yer;
        if A[l+l]<>0 then
          begin
           inc(j);
           B[j].sayi:=A[l+l];
           B[j].yer:=l+l;
           A[l+l]:=0;
          end
         else if A[l+l+1]<>0 then
           begin
            inc(j);
            B[j].sayi:=A[l+l+1];
            B[j].yer:=l+l+1;
            A[l+l+1]:=0;
           end;
        inc(v);
       end;
     end;
   for i:=1 to j do  Add_To_Tree(B[i].sayi,n,A);
  end;
End;
 
Procedure Write_Mon(n:integer;A:dizi);
var i:integer;
Begin
  writeln;
  for i:=1 to n do write(A[i]:3);
End;
 
BEGIN
 clrscr;
 Read_Array(n,A);
 Erase_From_Tree(n,A);
 Write_Mon(n,A);
 repeat ch:=readkey until ch=#27; { Esc is exit}
END.

  

Sample Execution

 

 

 

 

Input the size of tree array: 15

Input the elements of tree...

30 10 50 1  15 31 90 0  5  0  0  0  0  0  99

 

Enter the number to be erased:50

 

 30 10 31  1 15  0 90  0  5  0  0  0  0  0 99