Chương trình C++ duyệt cây nhị phân Inorder không dùng đệ quy

Duyệt Inorder (trái – gốc – phải) của cây nhị phân tìm kiếm (BST) cho ra khóa theo thứ tự tăng dần. Bài này cài đặt không dùng đệ quy, thay vào đó dùng stack mô phỏng call stack.

Thuật toán (Iterative Inorder)

Bắt đầu
    inOrder(root)
    stack s
    current = root
    Khi (current != NULL HOẶC !s.empty()):
        Khi (current != NULL):
            s.push(current)
            current = current->left
        current = s.top(); s.pop()
        visit(current)  // in key
        current = current->right
Kết thúc

Mã nguồn

#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); // 1 6 9 7 2
    return 0;
}

Kết quả

1 6 9 7 2

Giải thích

• Stack lưu các node cha chưa xử lý bên phải.
• Đi trái尽可能深 (push all left).
• Pop -> visit -> sang phải -> lặp lại.
• Độ phức tạp: O(n) thời gian, O(h) không gian (h = chiều cao cây).

So sánh với đệ quy

Mở rộng: Iterator Inorder

C++11 có thể gói thành iterator để dùng với range-based for:

class InorderIterator {
    stack<Node*> s;
    Node* cur;
    void pushLeft(Node* n) { while (n) { s.push(n); n = n->left; } }
public:
    InorderIterator(Node* root) : cur(root) { pushLeft(cur); }
    int operator*() { return cur->data; }
    InorderIterator& operator++() {
        cur = cur->right;
        pushLeft(cur);
        return *this;
    }
    bool operator!=(const InorderIterator&) { return cur || !s.empty(); }
};