Tree Implementation in both custom Linked list and Array stack and Traversal In order, Pre order, Post order, Level order, Level print , Height print:

Code Explanation:

This code is bit complex and will require knowledge on:

1. Struct
2. Linked list
3. Queue
4. Stack
5. Binary Tree ( check this and this too  )

Input Format:

Code:

/*
 * Author: Quickgrid
 * Code: Tree creation, traversal in array & linked list ( inorder/preorder/postorder/levelorder )
 * Description:
 */

#include <stdio.h>

#define size 1000   /* used this for queue array */

struct tree{    /* binary tree structure */
    char data;
    struct tree *left;
    struct tree *right;
};
typedef struct tree node;

struct stack{   /* linear/singly linked list stack to hold tree type data */
    node *nodedata;
    struct stack *next;
};
typedef struct stack vertex;

node* q[size];  /* here our array is node data type that we defined above */
int f = 0, r = 0;
vertex *front = NULL, *rear = NULL;
node *root = NULL;

void enq(node *root){   /* circular queue array modular arithmetic */
    int s = (r+1) % (size+1); /* +1 means we don't use 1 box of the array */
    if(f == s){
        printf("Queue Full.\n");
        return;
    }
    q[s] = root; /* root is node type we put it in our node array */
    r = s;  /* s is temporary variable */
}

node *deq(){
    if(f==r){
        printf("Queue Empty.\n");
        return NULL;
    }
    f = (f+1)%(size+1);
    node *temp = q[f]; /* get the last element of the queue to return for further operations */
    q[f] = 0;
    return temp;
}

void levelOrderArray(node *root){
    enq(root);  /* here we enqueue the root or the node that we want to star from */
    while(f!=r){ /* check if our queue is not empty */
        node *v = deq(); /* dequeue one item */
        printf("%c ", v->data);
        if(v->left!=NULL){ /* check if left branch of tree exists */
           enq(v->left); /* send the left node to queue */
        }
        if(v->right!=NULL){ /* check if right branch of tree exists */
            enq(v->right); /* send the right node to queue */
        }
    }
}

void enqueue(node *root){   /* enqueue function for our stack in linked list */
    if(front == NULL){
        front = new vertex();
        front->nodedata = root;
        front->next = NULL;
        rear = front;
    }else{
        vertex *temp = new vertex();
        temp->nodedata = root;
        temp->next = NULL;
        rear->next = temp;
        rear = temp;
    }
}

vertex *dequeue(){
    if(front == NULL){
        printf("queue empty.\n");
        return front;
    }
    vertex *temp,*tmp = front;
    front = front->next;
    delete temp;
    return tmp;
}

void levelorder (node *root){
    enqueue(root);
    while ( front != NULL ){
        vertex *v = dequeue();  /* we dequeue one vertex type data from our vertex stack */
        if(v!=NULL){
            printf("%c",v->nodedata->data);

            if (v->nodedata->left != NULL){ /* nodedata is our data part which holds node type data */
                enqueue(v->nodedata->left);
            }
            if (v->nodedata->right != NULL){
                enqueue(v->nodedata->right);
            }
        }
    }
}

int treeHeight(node *root){
    if(root == NULL){
        return 0;
    }
    int leftHeight = treeHeight(root->left);
    int rightHeight = treeHeight(root->right);

    if(leftHeight > rightHeight){
        return leftHeight+1;
    }else{
        return rightHeight+1;
    }
}

void printGivenLevel(node *root, int level){
    if(root == NULL){
        return;
    }
    if(level == 1){
        printf("%c ", root->data);
    }else if(level > 1){
        printGivenLevel(root->left, level-1);
        printGivenLevel(root->right, level-1);
    }
}

void createBinaryTree (node *root)
{
    char ans;

    fflush(stdout);
    printf("%c has any left child: ", root->data);
    fflush(stdin);
    ans = getchar();

    if (ans == 'y') /* create left side of a tree node */
    {
        root->left = new node ();
        root->left->left = NULL;
        root->left->right = NULL;
        fflush(stdout);
        printf("Enter left data of %c: ", root->data);
        fflush(stdin);
        scanf("%c",&root->left->data);
        createBinaryTree (root->left);  /* recursive call with created node as root to check if it has left and right */
    }

    fflush(stdout);
    printf("%c has any right child: ", root->data);
    fflush(stdin);
    ans = getchar();

    if (ans == 'y') /* create right side of a tree node */
    {
        root->right = new node ();
        root->right->left = NULL;
        root->right->right = NULL;
        fflush(stdout);
        printf("Enter right data of %c: ", root->data);
        fflush(stdin);
        scanf("%c",&root->right->data);
        createBinaryTree (root->right);
    }
}

void postOrder(node *root){
    if(root->left!=NULL){
        postOrder(root->left);
    }
    if(root->right!=NULL){
        postOrder(root->right);
    }
    printf("%c ", root->data);
}

void preOrder(node *root){
    printf("%c ", root->data);
    if(root->left!=NULL){   /* check if left side of that node exist */
        preOrder(root->left);   /* recursive call of preorder using this node as the root */
    }
    if(root->right!=NULL){
        preOrder(root->right);
    }
}

void inOrder(node *root){
    if(root->left!=NULL){
        inOrder(root->left);
    }
    printf("%c ", root->data);
    if(root->right!=NULL){
        inOrder(root->right);
    }
}

int main ()
{
    char ans;
    fflush(stdout);
    printf("Do u want to create a tree: ");
    fflush(stdin);
    ans = getchar();

    root = new node ();
    fflush(stdout);
    printf("Enter root of tree: ");
    fflush(stdin);
    scanf("%c",&root->data);
    createBinaryTree(root);

    int height = treeHeight(root);
    printf("\nTree Height: %d", height);

    printf("\nLevel order Linked List: ");
    levelorder(root);   /* Instead of sending root we can send another node to level order from that node */
    printf("\nLevel order Array: ");
    levelOrderArray(root);
    printf("\nPre order : ");
    preOrder(root);
    printf("\nIn order : ");
    inOrder(root);
    printf("\nPost order : ");
    postOrder(root);

    printf("\nEnter level to print:");
    int level;
    scanf("%d", &level);
    if(level >= height || level < 1){
        printf("\nGiven level doesn't exist.");
    }else{
        printf("Level %d: ", level);
        printGivenLevel(root, level);
        printf("\n");
    }
    return 0;
}