C++ Program to Perform Inorder Non-Recursive Traversal of a Given Binary Tree

ถ้า binary tree ถูก traverse แบบ in-order จะเยี่ยม left subtree ก่อน แล้ว root และภายหลัง right sub-tree Output จะได้ key เรียงจากน้อยไปมากใน in-order traversal นี่คือ C++ Program สำหรับ Inorder Tree Traversal โดยไม่ใช้ Recursion

Algorithm

Begin
    Declare a structure n.
        Declare d of the integer datatype.
        Declare a pointer l against structure n.
        Declare a pointer r against structure n.
        Declare a constructor of structure n.
            Pass an integer variable d to parameter.
            this->d = d
            l = r = NULL
    Declare inOrder(struct n *root) function.
        Declare a stack s.
        Declare a pointer current against structure n.
            Initialize n *current = root.
        while (current != NULL || s.empty() == false)
            while (current != NULL)
                s.push(current)
                current = current->l
            current = s.top()
            s.pop()
            print current->d.
            current = current->r.
    insert values in nodes of tree.
    Call inOrder(root) function to traverse the tree.
End.

ตัวอย่าง

#include<bits/stdc++.h>
using namespace std;
struct n {
    int d;
    struct n* l;
    struct n* r;
    n (int d) {
        this->d = d;
        l = r = NULL;
    }
};
void inOrder(struct n *root) {
    stack<n *> s;
    n *current = root;
    while (current != NULL || s.empty() == false) {
        while (current != NULL) {
            s.push(current);
            current = current->l;
        }
        current = s.top();
        s.pop();
        cout << current->d << " ";
        current = current->r;
    }
}
int main() {
    struct n* root = new n(6);
    root->l = new n(4);
    root->r= new n(7);
    root->l->l = new n(8);
    root->l->r= new n(5);
    root->r->l = new n(9);
    root->r->r = new n(10);
    inOrder(root);
    return 0;
}

ผลลัพธ์

8 4 5 6 9 7 10