โปรแกรม C++ สำหรับ Inorder Tree Traversal แบบไม่ใช้ Recursion

ถ้าต้นไม้ไบนารีถูกเดินทางแบบ In-order จะเยี่ยมชม subtree ซ้ายก่อน ตามด้วยราก แล้วค่อย subtree ขวา ผลลัพธ์จะได้คีย์เรียงจากน้อยไปมาก นี่คือโปรแกรม C++ สำหรับ Inorder Tree Traversal แบบไม่ใช้ Recursion

อัลกอริทึม

Begin
    Function inOrder():
        Declare stack s
        Declare current node as root
        While current != NULL or stack not empty
            While current != NULL
                Push current onto stack
                current = current->left
            current = s.top()
            s.pop()
            Print current node
            current = current->right
        Insert elements at root, left, right
        Call inOrder() to traverse tree
End.

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

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
    Node(int d) : data(d), left(NULL), right(NULL) {}
};

void inOrder(Node *root) {
    stack<Node*> s;
    Node *current = root;
    while (current != NULL || !s.empty()) {
        while (current != NULL) {
            s.push(current);
            current = current->left;
        }
        current = s.top(); s.pop();
        cout << current->data << " ";
        current = current->right;
    }
}

int main() {
    Node *root = new Node(7);
    root->left = new Node(6);
    root->right = new Node(2);
    root->left->left = new Node(1);
    root->left->right = new Node(9);
    inOrder(root);
    return 0;
}

ผลลัพธ์

1 6 9 7 2