Pages - Menu

Thursday, 23 May 2019

Tree traversal in C | Inorder, Preorder, Postorder tree traversal

HERE IS THE CODE
#include <stdio.h>
#include <stdlib.h>
struct node {
    struct node *leftChild;
    char data;
    struct node *rightChild;
};

struct node * buildTree(int);
void inorderTraversal(struct node *);
void preorderTraversal(struct node *);
void postorderTraversal(struct node *);
char treeArray[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', '\0', '\0','H', '\0',
            '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0'};
int main() {
    struct node *root;
    root = buildTree(0);
    printf("In order traversal \n");
    inorderTraversal(root);
    printf("\nPre order traversal \n");
    preorderTraversal(root);
    printf("\nPost order traversal \n");
    postorderTraversal(root);
    return 0;
}

struct node * buildTree(int index) {
    struct node *temp = NULL;
    if (treeArray[index] != '\0') {
        temp = (struct node *)malloc(sizeof(struct node));
        temp -> data = treeArray[index];
        temp -> leftChild = buildTree(2*index + 1);
        temp -> rightChild = buildTree(2*index + 2);
    }
    return temp;
}

void inorderTraversal(struct node *root) {
    if (root != NULL) {
        if (root->leftChild != NULL) {
            inorderTraversal(root->leftChild);
        }
        printf("%c\t", root->data);
        if (root->rightChild != NULL) {
            inorderTraversal(root->rightChild);
        }
    }
}

void preorderTraversal(struct node *root) {
    if (root != NULL) {
        printf("%c\t", root -> data);
        preorderTraversal(root -> leftChild);
        preorderTraversal(root -> rightChild);
    }
}

void postorderTraversal(struct node *root) {
    if (root == NULL) {
        return;
    }
    if (root -> leftChild != NULL) {
        postorderTraversal(root -> leftChild);
    }
    if (root -> rightChild != NULL) {
        postorderTraversal(root -> rightChild);
    }
    printf("%c\t", root -> data);
}


No comments:

Post a Comment