The following C program build a binary tree using linked list. The tree can be traversed in in-order, pre-order or post-order.
Traversal Algorithm:
Preorder :
1) Traverse the root.
2) Traverse the left subtree in preorder.
3) Traverse the right subtree in preorder.
Inorder:
1) Traverse the left subtree in inorder.
2) Traverse the root.
3) Traverse the right subtree in inorder.
Postorder:
1) Traverse the left subtree in postorder.
2) Traverse the right subtree in postorder.
Traversal Algorithm:
Preorder :
1) Traverse the root.
2) Traverse the left subtree in preorder.
3) Traverse the right subtree in preorder.
Inorder:
1) Traverse the left subtree in inorder.
2) Traverse the root.
3) Traverse the right subtree in inorder.
Postorder:
1) Traverse the left subtree in postorder.
2) Traverse the right subtree in postorder.
3) Traverse the root.
//Binary tree using linked list /** * *@author VIKASH VIK VIKKU VIKASHVVERMA * */ #include<stdio.h> int count=1; typedef struct node { int data; struct node*left; struct node*right; }node; void insert(node**bt,int n) { if(*bt==NULL) { *bt=(node*)malloc(sizeof(node)); (*bt)->data=n; (*bt)->left=NULL; (*bt)->right=NULL; count++; } else { if(count%2==0) insert(&((*bt)->left),n); else insert(&((*bt)->right),n); } } //traverse the tree in inorder void inorder(node*bt) { if(bt!=NULL) { inorder(bt->left); printf("%d\t",bt->data); inorder(bt->right); } } //traverse the tree in preorder void preorder(node*bt) { if(bt!=NULL) { printf("%d\t",bt->data); preorder(bt->left); preorder(bt->right); } } //traverse the tree in postorder void postorder(node*bt) { if(bt!=NULL) { postorder(bt->left); postorder(bt->right); printf("%d\t",bt->data); } } void main() { node*bt=NULL; insert(&bt,1); insert(&bt,2); insert(&bt,3); insert(&bt,4); insert(&bt,5); insert(&bt,6); inorder(bt); printf("\n"); preorder(bt); printf("\n"); postorder(bt); }
No comments :
Post a Comment