Tree implementation using Linked List

Main Terms

•Path − Path refers to sequence of nodes along the edges of a tree.

•Root − Node at the top of the tree is called root. There is only one root per tree and one path from root node to any node.

•Parent − Any node except root node has one edge upward to a node called parent.

•Child − Node below a given node connected by its edge downward is called its child node.

•Leaf − Node which does not have any child node is called leaf node.

•Subtree − Subtree represents descendents of a node.

•Visiting − Visiting refers to checking value of a node when control is on the node.

•Traversing − Traversing means passing through nodes in a specific order.

•Levels − Level of a node represents the generation of a node. If root node is at level 0, then its next child node is at level 1, its grandchild is at level 2 and so on.

•keys − Key represents a value of a node based on which a search operation is to be carried out for a node.

Binary Tree Representation:

C code for Tree Implementation using Linked List:
 #include<stdio.h>

typedef struct node
{
    int data;
    struct node *left;
    struct node *right;
} node;
node *create();
void preorder(node *t);       
void inorder(node *t);       
void postorder(node *t);       


int main()
{   
    node *root;
    root=create();
    printf("\nThe preorder traversal of tree is:\n");
    preorder(root);
    printf("\nThe inorder traversal of tree is:\n");
    inorder(root);
    printf("\nThe postorder traversal of tree is:\n");
    postorder(root);
   
    return 0;
}
node *create()
{
    node *p;
    int x;
    printf("Enter data(99 for no data):"); // End of Recursion
    scanf("%d",&x);
   
    if(x==99)
        return NULL; // Assign Null for no data to left or right
   
    p=(node*)malloc(sizeof(node));
    p->data=x;
   
    printf("Enter left child of %d:\n",x);
    p->left=create();

    printf("Enter right child of %d:\n",x);
    p->right=create();
   
    return p;
}

void preorder(node *t)       
{
    if(t!=NULL)
    {

        printf("\n%d",t->data);        //visit the root
preorder(t->left);        //preorder traversal on left subtree
        preorder(t->right);        //preorder traversal on right subtree
    }
}

void inorder(node *t)        //address of root node is passed in t
{
    if(t!=NULL)
    {
    inorder(t->left);        //inorder traversal on left subtree
        printf("\n%d",t->data);        //visit the root
        inorder(t->right);        //inorder traversal on right subtree
    }
}

void postorder(node *t)        //address of root node is passed in t
{
    if(t!=NULL)
    {
    postorder(t->left);        //postorder traversal on left subtree
        postorder(t->right);        //postorder traversal on right subtree
        printf("\n%d",t->data);        //visit the root

    }
}
  /*output
 
  Enter data(99 for no data):50
Enter left child of 50:
Enter data(99 for no data):15
Enter left child of 15:
Enter data(99 for no data):10
Enter left child of 10:
Enter data(99 for no data):99
Enter right child of 10:
Enter data(99 for no data):99
Enter right child of 15:
Enter data(99 for no data):25
Enter left child of 25:
Enter data(99 for no data):99
Enter right child of 25:
Enter data(99 for no data):99
Enter right child of 50:
Enter data(99 for no data):75
Enter left child of 75:
Enter data(99 for no data):65
Enter left child of 65:
Enter data(99 for no data):99
Enter right child of 65:
Enter data(99 for no data):99
Enter right child of 75:
Enter data(99 for no data):85
Enter left child of 85:
Enter data(99 for no data):99
Enter right child of 85:
Enter data(99 for no data):99

The preorder traversal of tree is:

50
15
10
25
75
65
85
The inorder traversal of tree is:

10
15
25
50
65
75
85
The postorder traversal of tree is:

10
25
15
65
85
75
50
--------------------------------
Process exited after 48.53 seconds with return value 0
Press any key to continue . . .

*/ 

Postfix Expression evaluation using stack

1. Enter postfix expression
2. Differentiate operand and operator
3. Push operand onto stack till we get operator
4.Whenever we get operator from expression then pop two operand which are already pushed onto stack in  variable A And B respectively.
5.Apply operator onto operand A and B and again push result onto stack.
6. Repeat whole procedure till we get end of expression (here we use '.' for end of expression)

 #include<stdio.h>
#include<ctype.h>

 # define MAX 50       
 # define Expsize 50   

void push(int item);
int pop();
void EvalPostfix(char postfix[]);
 int stack[MAX];
 int top = -1 ;         

 int main()
 {
int i ;

char postfix[Expsize];
printf("Assume: four operators(*, /, +, -) in an expression and operand is single digit only.\n");
printf( " \nEnter postfix expression,\npress full stop '.' for end expression : ");
//Scan Expression
  for (i = 0 ; i <= Expsize - 1 ; i++)
{
scanf("%c", &postfix[i]);

if ( postfix[i] == '.' )
{ break; }
}

  EvalPostfix(postfix);
return 0;
 }

 void push(int item)
 {
if(top >= MAX -1)
{
printf("stack over flow");
return;
}
else
{
top = top + 1 ;
stack[top]= item;
}
 }

 /* define pop operation */
 int pop()
 {
int item;
if(top <0)
{
printf("stack under flow");
}
else
{
item = stack[top];
top = top - 1;
return item;
}
 }

 /* define function that is used to input postfix expression and to evaluate it */
 void EvalPostfix(char postfix[])
 {

int i ;
char ch;
int val;
int A, B ;


/* evaluate postfix expression */
for (i = 0 ; postfix[i] != '.'; i++)
{
ch = postfix[i];
if (isdigit(ch))
{
/* Push operand i.e. the digit onto stack
ch - '0' is used for getting digit rather than ASCII code of digit */
push(ch - '0');
}
else if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
{
/* Ch is an operator
* pop top element A and next-to-top elemnet B
* from stack and compute B operator A
*/
A = pop();
B = pop();

switch (ch)
{
case '*':
val = B * A;
break;

case '/':
val = B / A;
break;

case '+':
val = B + A;
break;

case '-':
val = B - A;
break;
}

/* push the result get from above onto the stack */
push(val);
}
}
printf( " \n Result of expression evaluation : %d \n", pop()) ;
 }

/*Output
Assume: four operators(*, /, +, -) in an expression and operand is single digit only.

Enter postfix expression,

press full stop '.' for end expression : 359*+.

 Result of expression evaluation : 48

*/

Stack Implementation using array

Stack:
Consider a real life example of chair placed one on another first chair can be removed at last
First in Last Out data structure.
Operation on stack:
Top:
Top is a pointer used to locate top most data on stack.
Push: Push/Add data on to stack. Increment top and add data onto position of top
Pop:Pop/remove data from stack. take data in variable then decrement top
Isfull: Check if stack is full or not. check condition Top=>(Size-1)
Isempty: Check if stack is empty or not. check condition Top<=(-1)

  #include<stdio.h>

int stack[50],choice,n,top,x,i;
void push(void);
void pop(void);
void display(void);
int main()
{
top=-1;
printf("\n Enter the size of STACK[MAX=100]:");
scanf("%d",&n);
printf("\n\t STACK OPERATIONS USING ARRAY");
printf("\n\t 1.PUSH\n\t 2.POP\n\t 3.DISPLAY\n\t 4.EXIT");
do
  {
    printf("\n Enter the Choice:");
    scanf("%d",&choice);
   switch(choice)
    {
      case 1:
       {
         push();
         break;
       }
      case 2:
       {
         pop();
         break;
       }
      case 3:
       {
         display();
          break;
       }
       case 4:
       {
         printf("\n\t EXIT POINT ");
         break;
        }
       default:
        {
           printf ("\n\t Please Enter a Valid Choice(1/2/3/4)");
         }

    }
  }while(choice!=4);
return 0;
}

//Check first stack is overflow or not .
//Else scan data to be pushed ,increment top and then add data in stack at top pointer lacation
void push()
{
   if(top>=n-1)
     {
      printf("\n\tSTACK is over flow");
     }
   else
     {
       printf(" Enter a value to be pushed:");
       scanf("%d",&x);
       top++;
       stack[top]=x;
     }
}

//First check stack is underflow or not
// Else first take data of pointer top then decrement top pointer. 
void pop()
{
   if(top<=-1)
    {
     printf("\n\t Stack is under flow");
    }
   else
    {
     printf("\n\t The popped elements is %d",stack[top]);
     top--;
    }
}

// For display first check either stack is Empty or not .
// then print data from array pointer starts from top to 0 location.
void display()
{
   if(top>=0)
    {
      printf("\n The elements in STACK \n");
      for(i=top; i>=0; i--)
      printf("\n%d",stack[i]);
      printf("\n Press Next Choice");
    }
   else
    {
      printf("\n The STACK is empty");
    }
 }

 /*
 Output


 Enter the size of STACK[MAX=100]:10

STACK OPERATIONS USING ARRAY
--------------------------------
1.PUSH
2.POP
3.DISPLAY
4.EXIT
 Enter the Choice:1
 Enter a value to be pushed:56

 Enter the Choice:1
 Enter a value to be pushed:47

 Enter the Choice:1
 Enter a value to be pushed:40

 Enter the Choice:3

 The elements in STACK

40
47
56
 Press Next Choice
 Enter the Choice:2

The popped elements is 40
 Enter the Choice:2

The popped elements is 47
 Enter the Choice:2

The popped elements is 56
 Enter the Choice:2

Stack is under flow
 Enter the Choice:
 */