Animated GIF of binary tree insertion

Question

I am trying to produce an animated gif of simple binary tree insertion using the dot and convert utilities of ubuntu. But it is not exactly working as I want. The animated gif which I get at the end does not show the complete tree and only shows the root node.

To test the program, just put some random integers and stop the input part with -1.

#include<stdio.h>
#include<stdlib.h>

struct node{
    int value;
    struct node *left,*right;
};

typedef struct node node;

node *root;
FILE *out;

node *insert(node *,int);
node *new_node(int);

int main()
{
    root = NULL;

    int temp;
    int k = 0;

    while(1)
    {
        scanf("%d",&temp);
        if( temp == -1) break;

        root = insert(root,temp);

        take_snap(k++); // this function writes the dot file and create a jpg image for the current tree
    }

    animate();
    // this function use convert utility to combine all the images made earlier and create a animated gif
    return 0;
}

node *new_node(int x)
{
    node *new = (node *) malloc(sizeof(node));
    new->left = new->right = NULL;
    new->value = x;
    return new;
}

node *insert(node *s,int temp)
{
    if( s == NULL)
        return new_node(temp);
    else if( s->value < temp )
        s->right = insert(s->right,temp);
    else if( s->value > temp )
        s->left = insert(s->left,temp);
    return s;
}

take_snap(int index)
{
    out = fopen("temp.dot","w");
    fprintf(out,"graph {\n");
    if( root )
        fprintf(out,"%d\n",root->value);
    dottify(root);
    fprintf(out,"}\n");

    fclose(out);
    char tempstr[100];
    sprintf(tempstr,"dot -Tjpg temp.dot -o image%d.jpg",index);
    system(tempstr);
}

dottify(node *s)
{
    if( s )
    {
        if(s->left)
        {
            fprintf(out,"%d -- %d\n",s->value,(s->left)->value);
            dottify(s->left);
        }

        if(s->right)
        {
            fprintf(out,"%d -- %d\n",s->value, (s->right)->value);
            dottify(s->right);
        }
    }
}


animate()
{
    //system("convert *.jpg -resize 200x200 *.jpg");
    system("convert -delay 100 -loop 0 image*.jpg animation.gif");
    system("eog ./animation.gif");
}

What am I doing wrong?

I tried using the resize operator yet I did not get what I wanted.

http://i.stack.imgur.com/e1rPD.gif

EDITED:

I have commented out the resize part, somehow it was making more than necessary jpgs.But the problem still remains.

Answer 1

There are two problems with convert *.jpg -resize 200x200 *.jpg:

• you need to add exclamation to force convert to mess aspect ratio
• convert can't do bulk conversions, just one image a time.

Like this:

for i in *.jpg ; do convert $i -resize 200x200! $i ; done

But due to scaling the result will be not very nice.

The other thing you can do is to force graphviz to generate fixed size images, just add some graph attributes: ratio=fill, size="2,2!", resolution=100.

Like this:

take_snap(int index)
{
    out = fopen("temp.dot","w");
    fprintf(out,"graph {\n");
    fprintf(out,"graph [ratio=fill, size=\"2,2!\", resolution=100];\n");

The problem is that all images will be 200x200px size, except the one for a single-node graph.
I don't know why this is the case. But you can fix this one image with convert.

convert image0.jpg -resize 200x200! image0.jpg

The result looks like this:

Answer 2

Here is my take on this: build the entire tree into memory, then output the entire .dot file for each additional node but set the attributes of 'not yet added' nodes to "invisible". Since all trees are now the same size, no resizing of individual files is necessary.

For this, the 'creation index' needs to be stored into the node as well. Note that I changed the output file format to "GIF" -- as you can see, storing such as simple image as a JPEG introduces ugly artefacting.

Entire code again (sorry, lots of little changes overall):

#include <stdio.h>
#include <stdlib.h>

struct node {
    int value;
    int index;
    struct node *left,*right;
};

typedef struct node node;

node *root;
FILE *out;

node *insert(node *,int,int);
node *new_node(int,int);

int main()
{
    root = NULL;

    int temp;
    int k = 0, i;

    while(1)
    {
        scanf("%d",&temp);
        if( temp == -1) break;

        root = insert(root,temp, k);
        k++;
    }

    for (i=0; i<k; i++)
    {
        take_snap (i);
    }

    // this function use convert utility to combine all the images made earlier and create a animated gif
    animate();
    return 0;
}

node *new_node (int x, int index)
{
    node *new = (node *) malloc(sizeof(node));
    new->left = new->right = NULL;
    new->value = x;
    new->index = index;

    return new;
}

node *insert(node *s,int temp, int index)
{
    if( s == NULL)
        return new_node(temp, index);
    else if( s->value < temp )
        s->right = insert(s->right,temp, index);
    else if( s->value > temp )
        s->left = insert(s->left,temp, index);
    return s;
}

take_snap (int index)
{
    char tempstr[100];
    sprintf (tempstr, "temp%d.dot", index);
    out = fopen(tempstr,"w");

    fprintf(out,"graph {\n");
    if( root )
    {
        fprintf(out,"%d\n",root->value);
        dottify(root, index);
    }
    fprintf(out,"}\n");

    fclose(out);

    sprintf(tempstr,"dot -Tgif temp%d.dot -o image%d.gif",index,index);
    system(tempstr);
}

dottify(node *s, int index)
{
    if( s )
    {
        if(s->left)
        {
            if (s->left->index <= index)
                fprintf(out,"%d -- %d\n",s->value,s->left->value);
            else
            {
                fprintf(out,"%d [style=invis]\n", s->left->value);
                fprintf(out,"%d -- %d [style=invis]\n", s->value, s->left->value);
            }
            dottify(s->left, index);
        }

        if(s->right)
        {
            if (s->right->index <= index)
                fprintf(out,"%d -- %d\n",s->value, s->right->value);
            else
            {
                fprintf(out,"%d [style=invis]\n", s->right->value);
                fprintf(out,"%d -- %d [style=invis]\n", s->value, s->right->value);
            }
            dottify(s->right, index);
        }
    }
}


animate()
{
    //system("convert *.jpg -resize 200x200 *.jpg");
    system("convert -delay 100 -loop 0 image*.jpg animation.gif");
    system("eog ./animation.gif");
}

and this is how it looks with the same input max taldykin used: 3 1 6 2 8 4 5 0 -2 -1

[Edit] Oh let's have some fun with coloring. Add this

if (s->left->index == index)
    fprintf(out,"%d [style=filled, color=cyan]\n", s->left->value);

and the same for right->value into the dottify routine to get this:

Answer 3

this is a Binary tree code in Java.

IT HAS ALL FEATURES LIKE INSERTING PREORDER POSTORDER IT HAS ANIMATION OF THE BINARY TREE AND ITS MIRROR IMAGE TOO. IT ALSO HAS SEARCH FEATURE WITH ANIMATION. KINDLY CONTACT ME IF YOU HAVE ANY TROUBLE UNDERSTANDING THE CODE.

package classassignmentalgo;

import java.awt.*;
import java.awt.event.*;
import java.io.IOException;
import java.util.*;
import javax.swing.*;
// * @author gauraangkhurana

public class ClassAssignmentAlgo extends JFrame implements ActionListener{

// Adding all panels, text boxes and labels here.
JPanel panel1 = new JPanel(new GridLayout(0,2));
JPanel panel2 = new JPanel(new GridLayout(0,2));
JTextField txtBox = new JTextField();
static JLabel lbl1 = new JLabel();
static JLabel lbl2 = new JLabel();
static JLabel lbl3 = new JLabel();
static JLabel lbl4 = new JLabel();
static JLabel lbl5 = new JLabel();
static JLabel lblExtra = new JLabel();
static String preorder = new String();
static String inorder = new String();
static String postorder = new String();


// Adding all buttons here 
JButton btnTree = new JButton("Tree");
JButton btnPreorder = new JButton(("Preorder"));
JButton btnInorder = new JButton("Inorder");
JButton btnPostorder = new JButton("postorder");
JButton btnLeafNodes = new JButton("Leaf Nodes");
JButton btnNonLeaf = new JButton("Non- leaf nodes");
JButton btnMirror = new JButton("Mirror");
JButton btnSearch = new JButton("Search");
JTextField txtSearch = new JTextField();
static int[][] coordinateArray;


  //Constructor to add all panels and buttons to frame.
  public ClassAssignmentAlgo(){
    panel2.add(btnTree);
    panel2.add(txtBox);
    panel2.add(btnPreorder);
    panel2.add(lbl1);
    panel2.add(btnInorder);
    panel2.add(lbl2);
    panel2.add(btnPostorder);
    panel2.add(lbl3);
    panel2.add(btnLeafNodes);
    panel2.add(lbl4);
    panel2.add(btnNonLeaf);
    panel2.add(lbl5);
    panel2.add(btnMirror);
    panel2.add(lblExtra);
    panel2.add(btnSearch);
    panel2.add(txtSearch);
    getContentPane().setLayout(new GridLayout(2,0));
    add(panel1);
    add(panel2);
    // Adding methods to all buttons.
    btnTree.addActionListener(this);
    btnPreorder.addActionListener(this);
    btnInorder.addActionListener(this);
    btnPostorder.addActionListener(this);
    btnLeafNodes.addActionListener(this);
    btnNonLeaf.addActionListener(this);
    btnMirror.addActionListener(this);
    btnSearch.addActionListener(this);
}


public static void main(String[] args) {

    JFrame frame = new ClassAssignmentAlgo();
    frame.setSize(900,700);
    frame.setVisible(true);
    frame.setDefaultCloseOperation(EXIT_ON_CLOSE);
}




@Override
public void actionPerformed(ActionEvent e) {
    // When Button Tree is pressed 
    if(e.getSource() == btnTree){
        String input = txtBox.getText();
        insertInBtree(input,8);
    }
    //When button preorder is pressed.
    if(e.getSource() == btnPreorder){
        String input = txtBox.getText();
        insertInBtree(input,0);
    }
    //When button postorder is pressed.
    if(e.getSource() == btnPostorder){
        String input = txtBox.getText();
        insertInBtree(input,2);
    }
    //When button inorder is pressed.
    if(e.getSource() == btnInorder){
        String input = txtBox.getText();
        insertInBtree(input,1);
    }
    //When button leaf nodes is pressed.
    if(e.getSource() == btnLeafNodes){
        String input = txtBox.getText();
        insertInBtree(input,4);
    }
    //When button non leaf nodes is pressed.
    if(e.getSource() == btnNonLeaf){
        String input = txtBox.getText();
        insertInBtree(input,5);
    }
    //When button button mirror is pressed.
    if(e.getSource() == btnMirror){
        String input = txtBox.getText();
        insertInBtree(input,3);
    }
    //When button search is pressed.
    if(e.getSource() == btnSearch){
        String input = txtBox.getText();
        insertInBtree(input,6);
    }

}

public  void insertInBtree(String a,int b){
    BTree instance = new BTree();
    instance.imp(a,b);
}

  // BTREE Class which is a subclass of the main class.  
    public  class BTree {

BTree root = null;
BTree temp1;
BTree temp2;
int data;
BTree right,left;
 int[] array = new int[20];

 // Constructor to add empty Btree.
public BTree(){
right = null;
left = null;
data = 0;
}

//Constructor to add Btree with some data. 
public BTree(int n){
    data = n;
    right = null;
    left = null;
  }

//This string is to print the output when postorder, preorder or inorder button is pressed.
String print = new String();

//This function adds the input to the Btree.
 void imp(String received,int a) {
   try{
     String[] array = received.split(",");
     coordinateArray = new int[array.length][2];
     for(int i=0;i<array.length;i++){
        InBTree(Integer.parseInt(array[i]));
     }  
   }
   //If the input entered is in wrong format.
     catch(Exception e){
     JOptionPane.showMessageDialog(null,"Wrong Input");
     System.exit(0);
     }

     temp1 = root;
     temp2 = root;

     switch(a){
         // Switch case for the buttons pressed.
         case 0 : preorderOfBtree(root);
           break;

         case 1 : inorderOfBtree(root);
           break;

         case 2 : postorderOfBtree(root);
           break;

         case 3 :mirrorImageOfBtree(temp2);
                 printMirror(temp2);
          break;

         case 4: leafNodesOfBtree(root);
             break;
         case 5 : nonleafNodesOfBtree(root);
             break;

         case 6 : searchInBtree(root);
             break;

         case 8 : drawingBtree(root,180);
             break;
         default: 
             break;

  }
 }
 int a = 40;
 int radiusOfNode = 20;
 int gapHeight = 50;

   // When search button is pressed.  
   void searchInBtree(BTree node){
   Graphics g = getGraphics();
   displayInPanel(g,node,180,80,80);
   if(flag == 0){
       JOptionPane.showMessageDialog(null,"Element not found");
   }
  }
   //This function is called when the Tree button is pressed.    
  void drawingBtree(BTree node,int a){
    drawBtree(node,a);
  }    

    void drawBtree(BTree node,int startingPoint){
   Graphics g = getGraphics();
     if(node != null){
         displayTreeInorderMirror(g,node,startingPoint,80,80);

  }

  }
 int flag = 0;

 //To Draw BTree in normal order.
  void displayInPanel(Graphics f, BTree node,int xCoordinates,int yCoordinates,int gapWidth){

     String s = txtSearch.getText();
     int sInt = Integer.parseInt(s);
     if(sInt == node.data){
         f.setColor(Color.green);
         flag = 1;
     }
     else{
         if(flag ==0){
             f.fillOval(xCoordinates-radiusOfNode, yCoordinates-radiusOfNode, 2*radiusOfNode,   2*radiusOfNode);
             f.setColor(Color.red);
         }
         else{
             f.drawOval(xCoordinates-radiusOfNode, yCoordinates-radiusOfNode, 2*radiusOfNode, 2*radiusOfNode);
             f.setColor(Color.lightGray);
         }
     }

     f.drawString(String.valueOf(node.data), xCoordinates-6, yCoordinates+4);
     f.setColor(Color.black);

     if(node.left!=null){
         drawLeftLine(f,xCoordinates-gapWidth,yCoordinates+gapHeight,xCoordinates,yCoordinates);
         displayInPanel(f,node.left,xCoordinates-gapWidth,yCoordinates+gapHeight,gapWidth/2);
     }

     if(node.right!=null){
         drawRightLine(f,xCoordinates+gapWidth,yCoordinates+gapHeight,xCoordinates,yCoordinates);
         displayInPanel(f,node.right,xCoordinates+gapWidth,yCoordinates+gapHeight,gapWidth/2);
     }

  }

 //This function is called to print the mirror image of the btree.


 void printMirror(BTree temporary){
    drawingBtree(temporary,650);
 }
 //this function is used to display the mirror image  of the btree
 void displayTreeInorderMirror(Graphics f, BTree node,int xCoordinates,int yCoordinates,int   gapWidth){
     f.fillOval(xCoordinates-radiusOfNode, yCoordinates-radiusOfNode, 2*radiusOfNode, 2*radiusOfNode);
     f.setColor(Color.LIGHT_GRAY);
     f.drawString(String.valueOf(node.data), xCoordinates-6, yCoordinates+4);
     f.setColor(Color.BLACK);
     if(node.left!=null){
         drawLeftLine(f,xCoordinates-gapWidth,yCoordinates+gapHeight,xCoordinates,yCoordinates);
         displayTreeInorderMirror(f,node.left,xCoordinates-gapWidth,yCoordinates+gapHeight,gapWidth/2);
     }

     if(node.right!=null){
         drawRightLine(f,xCoordinates+gapWidth,yCoordinates+gapHeight,xCoordinates,yCoordinates);
         displayTreeInorderMirror(f,node.right,xCoordinates+gapWidth,yCoordinates+gapHeight,gapWidth/2);
     }

 }

 //this function draws the left line extending from the node

 void drawLeftLine(Graphics f,int coordinateX,int coordinateY,int coordinateX2,int coordinateY2){

     double d = Math.sqrt(gapHeight*gapHeight+(coordinateX2-coordinateX)*(coordinateX2-coordinateX));
     int startingX = (int)(coordinateX+radiusOfNode*(coordinateX2-coordinateX)/d);
     int startingY = (int)(coordinateY-radiusOfNode * gapHeight/d);
     int endingX = (int)(coordinateX2 - radiusOfNode * (coordinateX2-coordinateX)/d);
     int endingY = (int)(coordinateY2+radiusOfNode * gapHeight /d);
    try {
        Thread.sleep(600);
    } catch (InterruptedException ex) {
    }
     f.drawLine(startingX,startingY,endingX,endingY);
 }

 //this function draws the right line extending from the node
 void drawRightLine(Graphics f,int coordinateX,int coordinateY,int coordinateX2,int coordinateY2){
      double d = Math.sqrt(gapHeight*gapHeight+(coordinateX2-coordinateX)*(coordinateX2-coordinateX));
     int startingX = (int)(coordinateX-radiusOfNode*(coordinateX-coordinateX2)/d);
     int startingY = (int)(coordinateY-radiusOfNode * gapHeight/d);
     int endingX = (int)(coordinateX2 - radiusOfNode * (coordinateX-coordinateX2)/d);
     int endingY = (int)(coordinateY2+radiusOfNode * gapHeight /d);
     try {
        Thread.sleep(600);
    } catch (InterruptedException ex) {
    }
     f.drawLine(startingX,startingY,endingX+5,endingY-8);
 }


void InBTree(int n){
    root = insertInBtree(root,n);

}

//Function to insert elements the elements in the btree.

BTree insertInBtree(BTree node,int da){
    if(node == null ){
        node = new BTree(da);
    }
    else{
        if(node.data > da){
            node.left = insertInBtree(node.left,da);
        }
        else{
           node.right = insertInBtree(node.right,da);
        }
    }
    return node;
  }
    //Preorder tranversal of btree
void preorderOfBtree(BTree r)
 {
     if (r != null)
     {
         print += r.data +"      ";
         preorderOfBtree(r.left);       
         preorderOfBtree(r.right);

     }
     lbl1.setText(print);
 }

//To print the  leaf nodes of the btree.
void leafNodesOfBtree(BTree r){

    if(r == null){
        return;
    }
    if(r.left!=null || r.right!=null){
        leafNodesOfBtree(r.left);
        leafNodesOfBtree(r.right); 
    }
    else{
        print += r.data+"      ";
    }

    lbl4.setText(print);
}


//to print leaf nodes
void nonleafNodesOfBtree(BTree r){
    if(r==null){
        return;
    }
    if(r.left ==null && r.right == null){
        return;
    }
    else{
        nonleafNodesOfBtree(r.left);
        nonleafNodesOfBtree(r.right);
        print += r.data+"      ";
    }
    lbl5.setText(print);
  }

void postorderOfBtree(BTree r){
 if(r!=null){
     postorderOfBtree(r.left);
     postorderOfBtree(r.right);
     print += r.data+"      ";
 }
          lbl3.setText(print);

}
//inorder traversal of the btree
 void inorderOfBtree(BTree r){
 if(r != null){
     inorderOfBtree(r.left);
     print += r.data+"      ";
     inorderOfBtree(r.right);
   }
          lbl2.setText(print);

   }



 //This function creates a mirror image of the Btree.
   BTree mirrorImageOfBtree(BTree n){
    if(n == null){
     return null;
    }
    else{
     BTree tree =  new BTree();
      mirrorImageOfBtree(n.left);
      mirrorImageOfBtree(n.right);

      tree = n.left;
      n.left = n.right;
      n.right = tree;
    }
   return n;
   }
   }
   }