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

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

ตัวอย่าง Preorder Traversal:

Binary Tree ที่กำหนด:

Preorder Traversal: 6 4 1 5 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 preorder(struct node *root) {
    if (root != NULL) {
        cout << root->data << " ";
        preorder(root->left);
        preorder(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 << "Pre-Order traversal of the Binary Search Tree is: ";
    preorder(root);
    return 0;
}

ผลลัพธ์

Pre-Order traversal of the Binary Search Tree is: 4 2 1 3 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;
}

ฟังก์ชัน preorder()

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

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

ฟังก์ชัน 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<<"Pre-Order traversal of the Binary Search Tree is: ";
preorder(root);