Chương trình C++ duyệt tiền thứ tự (Preorder) không đệ quy của cây nhị phân

Duyệt cây (Tree traversal) là dạng duyệt đồ thị. Kiểm tra/in mỗi nút đúng một lần. Duyệt tiền thứ tự (Preorder) của cây nhị phân tìm kiếm: Root → Left → Right.

Ví dụ cây nhị phân:

Preorder Traversal: 5 3 2 4 8 9

Ví dụ chương trình

#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);
    return 0;
}

Kết quả

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

Cấu trúc node

Cấu trúc tự tham chiếu (self-referential) với data, left, right.

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

Hàm createNode()

Cấp phát bộ nhớ, gán data, left/right = NULL.

struct node* createNode(int val) {
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->data = val;
    temp->left = temp->right = NULL;
    return temp;
}

Hàm preorder() - Duyệt không đệ quy dùng stack

Đẩy root vào stack. Lặp khi stack không rỗng: lấy top, in data, pop. Đẩy right trước, rồi left (để left được xử lý trước do stack LIFO).

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);
    }
}

Hàm insertNode() - Chèn vào cây nhị phân tìm kiếm

Nếu node NULL → tạo mới. Nếu val < node->data → chèn trái. Nếu val > node->data → chèn phải.

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;
}

Hàm main() - Xây cây và duyệt

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);