โปรแกรม C++ ทำ Inorder Traversal แบบ Recursive บน Binary Tree

Tree Traversal เป็นรูปแบบหนึ่งของ Graph Traversal ตรวจสอบหรือแสดงค่าโหนดแต่ละโหนดในต้นไม้ทีละโหนดเพียงครั้งเดียว Inorder Traversal ของ Binary Search Tree จะเยี่ยมชมโหนดตามลำดับ (Left, Root, Right) คือ ซ้าย - ราก - ขวา

ตัวอย่าง Inorder Traversal:

Binary Tree ที่กำหนด:

Inorder Traversal: 1 4 5 6 8

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

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

struct node *createNode(int val) {
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->data = val;
    temp->left = temp->right = NULL;
    return temp;
}

void inorder(struct node *root) {
    if (root != NULL) {
        inorder(root->left);
        cout << root->data << " ";
        inorder(root->right);
    }
}

struct node* insertNode(struct node* node, int val) {
    if (node == NULL) return createNode(val);
    if (val < node->data)
        node->left = insertNode(node->left, val);
    else if (val > node->data)
        node->right = insertNode(node->right, val);
    return node;
}

int main() {
    struct node *root = NULL;
    root = insertNode(root, 4);
    insertNode(root, 5);
    insertNode(root, 2);
    insertNode(root, 9);
    insertNode(root, 1);
    insertNode(root, 3);
    cout << "In-Order traversal of the Binary Search Tree is: ";
    inorder(root);
    return 0;
}

ผลลัพธ์

In-Order traversal of the Binary Search Tree is: 1 2 3 4 5 9

โครงสร้างโหนด (struct node)

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

ฟังก์ชัน createNode()

struct node *createNode(int val) {
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->data = val;
    temp->left = temp->right = NULL;
    return temp;
}

ฟังก์ชัน inorder()

void inorder(struct node *root) {
    if (root != NULL) {
        inorder(root->left);
        cout << root->data << " ";
        inorder(root->right);
    }
}

ฟังก์ชันแบบเรียกซ้ำ รับ root พิมพ์ค่าโหนดตามลำดับ Inorder (ซ้าย, ราก, ขวา)

ฟังก์ชัน insertNode()

struct node* insertNode(struct node* node, int val) {
    if (node == NULL) return createNode(val);
    if (val < node->data)
        node->left = insertNode(node->left, val);
    else if (val > node->data)
        node->right = insertNode(node->right, val);
    return node;
}

ฟังก์ชัน main()

struct node *root = NULL;
root = insertNode(root, 4);
insertNode(root, 5);
insertNode(root, 2);
insertNode(root, 9);
insertNode(root, 1);
insertNode(root, 3);

cout<<"In-Order traversal of the Binary Search Tree is: ";
inorder(root);