Struktur Data : Implementasi Tree Tranversal dalam Bahasa C

📋 Daftar Isi

Pada artikel kali ini akan dibahas mengenai implementasi tree tranversal dalam bahasa C. Penasaran kan bagaimana cara menghubungkan antar sub tree dan root-nya? Yuk disimak ulasannya.

Pre-Order (Root, Left, Right)

void displayPreorder(struct node* node)
{
    if (node == NULL)
        return;

    printf("%d ", node->data); //root
    displayPreorder(node->left); //subtree kiri
    displayPreorder(node->right); //subtree kanan
}

In-Order (Left, Root, Right)

void displayInorder(struct node* node)
{
    if (node == NULL)
        return;

    displayInorder(node->left); //subtree kiri
    printf("%d ", node->data); //akar
    displayInorder(node->right); //subtree kanan
}

Post-Order (Left, Right, Root)

void displayPostorder(struct node* node)
{
    if (node == NULL)
        return;

    displayPostorder(node->left); //subtree kiri
    displayPostorder(node->right); //subtree kanan
    printf("%d ", node->data); //root
}

Sorce Code Lengkap

Misalkan akan dibuat Tree seperti gambar di atas. Output urutan yang diinginkan adalah sebagai berikut

In-Order : 25 15 10 4 12 22 18 24 50 35 31 44 70 90
Pre-Order : 25 15 10 4 12 22 18 24 50 35 31 44 70 90
Post-Order : 4 12 10 18 24 22 15 31 44 35 90 70 50 25

#include <stdio.h>

struct node
{
    int data;
    struct node *left;
    struct node *right;
};

struct node* newNode(int data)
{
    struct node* node = (struct node*)malloc(sizeof(struct node));

    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return(node);
};

void displayPreorder(struct node* node)
{
    if (node == NULL)
        return;

    printf("%d ", node->data); //root
    displayPreorder(node->left); //subtree kiri
    displayPreorder(node->right); //subtree kanan
}

void displayInorder(struct node* node)
{
    if (node == NULL)
        return;

    displayInorder(node->left); //subtree kiri
    printf("%d ", node->data); //akar
    displayInorder(node->right); //subtree kanan
}

void displayPostorder(struct node* node)
{
    if (node == NULL)
        return;

    displayPostorder(node->left); //subtree kiri
    displayPostorder(node->right); //subtree kanan
    printf("%d ", node->data); //root
}

int main()
{
    struct node *root = newNode(25);

    root->left = newNode(15);
    root->right = newNode(50);
    root->left->left = newNode(10);
    root->left->right = newNode(22);
    root->right->left = newNode(35);
    root->right->right = newNode(70);
    root->left->left->left = newNode(4);
    root->left->left->right = newNode(12);
    root->left->right->left = newNode(18);
    root->left->right->right = newNode(24);
    root->right->left->left = newNode(31);
    root->right->left->right = newNode(44);
    root->right->right->left - newNode(66);
    root->right->right->right = newNode(90);

    printf("\nIsi dari binary tree (Pre-Order) adalah \n");
    displayPreorder(root);

    printf("\nIsi dari binary tree (In-Order) adalah \n");
    displayInorder(root);

    printf("\nIsi dari binary tree (Post-Order) adalah \n");
    displayPostorder(root);

    return 0;
}

Ouput yang dihasilkan sama dengan yang telah dituliskan sebelumnya