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 . . .

*/