Advertisement
Guest User

Binary tree, preorder, inorder, postorder, insert, delete.

a guest
Nov 18th, 2019
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 3.46 KB | None | 0 0
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. typedef struct node Node;
  4. struct node{
  5.     int data;
  6.     Node *left,*right;
  7. };
  8. Node* getmin(Node *root)
  9. {
  10.     Node *ptr = root;
  11.     while(ptr && ptr->left!=NULL)
  12.     {
  13.         getmin(ptr->left);
  14.     }
  15.     return ptr;
  16. }
  17. Node* deletenode(Node *root,int data)
  18. {
  19.     if(root ==NULL)
  20.         return root;
  21.     if(root->data>data)
  22.         root->left = deletenode(root->left,data);
  23.     else if(root->data<data)
  24.         root->right = deletenode(root->right,data);
  25.     else
  26.     {
  27.         if(root->left == NULL)
  28.         {
  29.             Node *temp = root->right;
  30.             free(root);
  31.             return temp;
  32.         }
  33.         else if(root->right == NULL)
  34.         {
  35.             Node *temp = root->left;
  36.             free(root);
  37.             return temp;
  38.         }
  39.         Node *temp = getmin(root->right);
  40.         root->data = temp->data;
  41.         root->right = deletenode(root->right,temp->data);
  42.  
  43.     }
  44. }
  45. Node* in(Node *root,int data)
  46. {
  47.     int x = 0;
  48.     if(root == NULL)
  49.     {
  50.         Node *newnode = (Node*)malloc(sizeof(Node));
  51.         newnode->data = data;
  52.         newnode->left = NULL;
  53.         newnode->right = NULL;
  54.         root = newnode;
  55.         x = 1;
  56.     }
  57.     if(root->data==data && x == 0)
  58.     {
  59.         printf("%d found at address %x.",data,root);
  60.     }
  61.     else if(root->data==data && x != 0)
  62.     {
  63.         printf("%d not found. It has been inserted in the tree at address %x.",data,root);
  64.     }
  65.  
  66.     else if(data>root->data)
  67.         root->right = in(root->right,data);
  68.     else if(data<root->data)
  69.         root->left = in(root->left,data);
  70.     return root;
  71. }
  72. Node* insert(Node *root, int data)
  73. {
  74.     if(root == NULL)
  75.     {
  76.         Node *newnode = (Node*)malloc(sizeof(Node));
  77.         newnode->data = data;
  78.         newnode->left = NULL;
  79.         newnode->right = NULL;
  80.         root = newnode;
  81.     }
  82.     else if(data>=root->data)
  83.         root->right = insert(root->right,data);
  84.     else if(data<root->data)
  85.         root->left = insert(root->left,data);
  86.     return root;
  87. }
  88. void preOrder(Node *root){
  89.     if(root==NULL)
  90.         return ;
  91.     printf("%d ",root->data);
  92.     preOrder(root->left);
  93.     preOrder(root->right);
  94. }
  95. void inOrder(Node *root){
  96.     if(root == NULL)
  97.         return ;
  98.     inOrder(root->left);
  99.     printf("%d ",root->data);
  100.     inOrder(root->right);
  101. }
  102. void postOrder(Node *root){
  103.     if(root == NULL)
  104.         return ;
  105.     postOrder(root->left);
  106.     postOrder(root->right);
  107.     printf("%d ",root->data);
  108. }
  109. void nodeswithtwochild(Node *root){
  110.     if(root == NULL)
  111.         return ;
  112.     if(root->left!=NULL && root->right!=NULL)
  113.     printf("%d ",root->data);
  114.     nodeswithtwochild(root->left);
  115.     nodeswithtwochild(root->right);
  116. }
  117. int main(){
  118.     int n,data;
  119.     Node *root = NULL;
  120.     printf("Enter number of nodes : ");
  121.     scanf("%d",&n);
  122.     printf("Enter %d data : ",n);
  123.     while(n--){
  124.         scanf("%d",&data);
  125.         root = insert(root,data);
  126.     }
  127.     printf("PreOrder traversal : ");
  128.     preOrder(root);
  129.     printf("\nInOrder traversal : ");
  130.     inOrder(root);
  131.     printf("\nPostOrder traversal : ");
  132.     postOrder(root);
  133.     printf("\nNodes with two child : ");
  134.     nodeswithtwochild(root);
  135.     printf("\nEnter a data to search : ");
  136.     scanf("%d",&data);
  137.     root = in(root,data);
  138.     preOrder(root);
  139.     printf("\nEnter a data to delete : ");
  140.     scanf("%d",&data);
  141.     root = deletenode(root,data);
  142.     preOrder(root);
  143.     return 0;
  144. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement