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

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

ตัวอย่าง Postorder Traversal:

Binary Tree ที่กำหนด:

Postorder Traversal: 1 5 4 8 6

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

#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 postorder(struct node *root) {
    if (root != NULL) {
        postorder(root->left);
        postorder(root->right);
        cout << root->data << " ";
    }
}

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 << "Post-Order traversal of the Binary Search Tree is: ";
    postorder(root);
    return 0;
}

ผลลัพธ์

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

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

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

โครงสร้างนี้เป็น self-referential structure เนื่องจากมี pointer ชี้ไปยัง struct node เอง

ฟังก์ชัน 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;
}

สร้างโหนด temp จองหน่วยความจำด้วย malloc เก็บค่า val ไว้ใน data กำหนด left และ right เป็น NULL

ฟังก์ชัน postorder()

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

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

ฟังก์ชัน 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;
}

แทรกค่าลง Binary Tree ตำแหน่งที่ถูกต้อง ถ้า node เป็น NULL เรียก createNode มิฉะนั้นหาตำแหน่งตามกฎ BST

ฟังก์ชัน main()

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

สร้าง root เริ่มต้นเป็น NULL แล้วแทรกค่าต่างๆ เข้า BST

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

เรียก postorder() ผ่าน root แสดงค่าทั้งหมดแบบ Postorder