Binary Tree representation and Primitive Operations on a Binary Tree in C

Binary Trees are one of the core data structures used in any programming language to implement complex systems. C programming language offers various binary tree operations that could be used by the developer.

Binary Trees can be dynamically represented in C as shown below –

      
       struct nodetype{
                      int info;
                struct nodetype * left;
                struct nodetype * right;
                struct nodetype * father;
                     };
      typedef struct nodetype * NODEPTR;

If pointer ‘p’ points to a particular node of a binary tree, then the following operations are possible with a binary tree.

1. maketree(x) -> returns the pointer p with x at its info field and its left and right nodes as NULL
2. getnode()     -> allocates space in memory for a node with an info field and left and right nodes
3. setleft(p,x)   -> first checks for/creates a left node ‘nd’ from the node pointed by ‘p’ and adds x to the info field of nd
4. setright(p,x)-> first checks for/creates a right node ‘nd’ from the node pointed by ‘p’ and adds x to the info field of nd
5. setfather(p,x)-> first checks for/creates a father node ‘nd’ from the node pointed by ‘p’ and adds x to the info field of nd
6. freenode(p)  -> frees the node pointer
7. info(p)           -> returns info field of node pointed by ‘p’
8. left(p)            -> returns left son of p->node
9. right(p)         -> returns right son of p->node
10. father(p)       -> returns father of p->node
11. isleft(p)         -> returns TRUE if p->node is a left son
12. isright(p)      -> returns TRUE if p->node is a right son
13. isbrother(p,q) -> returns TRUE if p and q are brothers

Below are C routines for implementing above operations, Enjoy!

1. maketree()

     NODEPTR maketree(int x){
              NODEPTR getnode (void); NODEPTR p;
              p = getnode();
              p->info = x;
              p->left = p->right = NULL;
              p->father = NULL;
              return(p);
     }

2. getnode()

     NODEPTR getnode(void){              
              return((NODEPTR) malloc(size of struct nodetype));
          }

3. setright()

     void setright(NODEPTR p, int x){
              NODEPTR maketree(int);
              if(p == NULL)
                    printf("\nVoid insertion\n");
              elseif(p->right != NULL)
                    printf("\nInvalid insertion\n");
              else
                    p->right = maketree(x);
              return;
           }

4. setfather()

     void setfather(NODEPTR p, int x){
              NODEPTR maketree(int);
              if(p == NULL)
                    printf("\nVoid insertion\n");
              elseif(p->left != NULL)
                    printf("\nInvalid insertion\n");
              else
                    p->father = maketree(x);
              return;
           }

5. freenode()

     void freenode(NODEPTR p){              
              free(p);
          }

6. info()

     int info(NODEPTR p){              
              return(p->info);
          }

7. left()

     NODEPTR  left(NODEPTR p){              
              return(p->left);
          }

8. right()

     NODEPTR  right(NODEPTR p){              
              return(p->right);
          }

9. father()

     NODEPTR  father(NODEPTR p){              
              return(p->father);
          }

10. isleft()

     int isleft(NODEPTR p){              
              if(p->father == NULL)
                  return FALSE;
              else 
                  return (p->(father->left) == p ? TRUE : FALSE);
          }

11. isright()

     int isright(NODEPTR p){              
              if(p->father == NULL)
                  return FALSE;
              else 
                  return (p->(father->right) == p ? TRUE : FALSE);
          }

12. isbrother()

     int isbrother(NODEPTR p, NODEPTR p){              
              if(p->father == NULL || q->father == NULL)
                  return FALSE;
              elseif(p->father == q->father)
                  return TRUE;
          }