Implementation of Binary Tree - C/C++

A binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to the "root" node (the ancestor of all nodes), if it exists. Any node in the data structure can be reached by starting at root node and repeatedly following references to either the left or right child. A tree which does not have any node other than root node is called a null tree. In a binary tree, a degree of every node is maximum two. A tree with n nodes has exactly n−1 branches or degree.





#include<stdio.h>
#include<conio.h>
#include<malloc.h>
 
typedef struct tree
{
 int data;
 struct tree *lptr;
 struct tree *rptr;
}
btree;
btree *getnode(int no)
{
 btree *t;
 t = (btree*)malloc(sizeof(btree));
 t->lptr = NULL;
 t->rptr = NULL;
 t->data = no;
 return t;
}
 
void create(btree **rootint a)
{
 if (*root == NULL)
 {
  *root = getnode(a);
  return;
 }
 else if (a < (*root)->data)
  create(&(*root)->lptr, a);
 else
  create(&(*root)->rptr, a);
}
 
void inorder(btree *root)
{
 if (root == NULL)
 {
  return;
 }
 inorder(root->lptr);
 printf("%d "root->data);
 inorder(root->rptr);
}
 
void preorder(btree *root)
{
 if (root == NULL)
 {
  return;
 }
 
 printf("%d "root->data);
 preorder(root->lptr);
 preorder(root->rptr);
}
 
void postorder(btree *root)
{
 if (root == NULL)
 {
  return;
 }
 postorder(root->lptr);
 postorder(root->rptr);
 printf("%d "root->data);
}
 
void main()
{
 int a;
 btree *root = NULL;
 clrscr();
 printf("\n enter nos,for end type -999");
 do
 {
  scanf("%d", &a);
  if (a == -999)
   break;
  else
  if (root == NULL)
   root = getnode(a);
  else
   create(&root, a);
 }
 
 while (1);
 printf("\n inorder traversal is:");
 inorder(root);
 printf("\n preorder traversal is:");
 preorder(root);
 printf("\n postorder traversal is:");
 postorder(root);
 getch();
}

Post a Comment