โปรแกรม C++ ทำ Preorder Non-Recursive Traversal ของ Binary Tree

การท่องต้นไม้ (Tree traversal) เป็นรูปแบบหนึ่งของการท่องกราฟ (graph traversal) เกี่ยวข้องกับการตรวจสอบหรือพิมพ์แต่ละโหนดในต้นไม้ทีละโหนดอย่างถูกต้อง การท่อง preorder ของ binary search tree เกี่ยวข้องกับการเยี่ยมชมโหนดแต่ละโหนดในลำดับ (Root, Left, Right)

ตัวอย่างการท่อง preorder ของ binary tree มีดังนี้

binary tree กำหนดให้ดังนี้

Preorder Traversal คือ: 5 3 2 4 8 9

โปรแกรมสำหรับทำ preorder non-recursive traversal มีดังนี้:

ตัวอย่าง

#include<iostream> 
#include <stack> 
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) 
        return; 
    stack<node *> nodeStack; 
    nodeStack.push(root); 
    while (nodeStack.empty() == false) { 
        struct node *temp_node = nodeStack.top(); 
        cout<< temp_node->data <<" "; 
        nodeStack.pop(); 
        if (temp_node→right) 
            nodeStack.push(temp_node→right); 
        if (temp_node→left) 
            nodeStack.push(temp_node→left); 
    } 
} 

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, 5); 
    insertNode(root, 8); 
    insertNode(root, 3); 
    insertNode(root, 2); 
    insertNode(root, 6); 
    insertNode(root, 9); 
    insertNode(root, 4); 
    cout<<"Pre-Order traversal of the Binary Search Tree is: "; 
    preorder(root); 
}

ผลลัพธ์

Pre-Order traversal of the Binary Search Tree is: 5 3 2 4 8 6 9

ในโปรแกรมนี้ โครงสร้าง node สร้างโหนดของต้นไม้ โครงสร้างนี้เป็น self-referential structure เนื่องจากมีพอยน์เตอร์ชนิด struct node โครงสร้างแสดงดังนี้:

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

ฟังก์ชัน createNode() สร้างโหนด temp และจัดสรรหน่วยความจำด้วย malloc ค่าข้อมูล val ถูกเก็บใน data ของ temp NULL ถูกเก็บในพอยน์เตอร์ left และ right ของ temp โค้ดส่วนนี้มีดังนี้:

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() ใช้ stack เพื่อพิมพ์องค์ประกอบของต้นไม้แบบ preorder ก่อนอื่น ใส่โหนดราก (root) ลงใน stack เริ่มลูป while ที่ทำงานจนกว่า stack จะว่าง ก่อนอื่น แสดงข้อมูลในโหนดบนสุดของ stack จากนั้นนำโหนดออก (pop) ต่อมา ใส่โหนดขวาและซ้ายของโหนดดังกล่าวลงใน stack ตามลำดับ ฟังก์ชันนี้แสดงดังนี้:

void preorder(struct node *root) { 
    if (root == NULL) 
        return; 
    stack<node *> nodeStack; 
    nodeStack.push(root); 
    while (nodeStack.empty() == false) { 
        struct node *temp_node = nodeStack.top(); 
        cout<< temp_node->data <<" "; 
        nodeStack.pop(); 
        if (temp_node→right) 
            nodeStack.push(temp_node→right); 
        if (temp_node→left) 
            nodeStack.push(temp_node→left); 
    } 
}

ฟังก์ชัน insertNode() แทรกค่าที่ต้องการใน binary tree ตำแหน่งที่ถูกต้อง หากโหนดเป็น NULL จะเรียก createNode มิฉะนั้น จะหาตำแหน่งที่ถูกต้องในต้นไม้ โค้ดส่วนนี้มีดังนี้:

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() โหนดรากถูกนิยามเป็น NULL ก่อน จากนั้นนำโหนดทั้งหมดที่มีค่าที่ต้องการไปแทรกใน binary search tree โค้ดส่วนนี้มีดังนี้:

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

สุดท้าย เรียกฟังก์ชัน preorder() โดยใช้โหนดรากของต้นไม้ และค่าทั้งหมดของต้นไม้จะถูกแสดงแบบ preorder โค้ดส่วนนี้มีดังนี้:

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