Các kiểu duyệt cây nhị phân (Binary Tree Traversals) - Tổng hợp

Phần này tổng hợp các thuật toán duyệt khóa trong cây tìm kiếm nhị phân: Inorder, Preorder, Postorder, Level-order.

Ví dụ cây:

• Inorder (Trung tự): 5 8 10 15 16 20 23
• Preorder (Tiền tự): 10 5 8 16 15 20 23
• Postorder (Hậu tự): 8 5 15 23 20 16 10
• Level-order (Cấp độ): 10, 5, 16, 8, 15, 20, 23

Thuật toán tổng hợp

inorderTraverse(root):  if root: inorder(left); print root; inorder(right)
preorderTraverse(root): if root: print root; preorder(left); preorder(right)
postorderTraverse(root): if root: postorder(left); postorder(right); print root
levelOrderTraverse(root): queue que; push root; while que: item=front; print; push left/right; pop

Ví dụ C++ hoàn chỉnh

#include <iostream>
#include <queue>
using namespace std;

class node {
public:
    int h_left, h_right, bf, value;
    node *left, *right;
};

class tree {
private:
    node* get_node(int key);
public:
    node *root;
    tree() { root = NULL; }
    void inorder_traversal(node *r);
    void preorder_traversal(node *r);
    void postorder_traversal(node *r);
    void levelorder_traversal(node *r);
    node* insert_node(node *root, int key);
};

// get_node, insert_node giống các bài trước

void tree::inorder_traversal(node *r) {
    if(r != NULL) { inorder_traversal(r->left); cout << r->value << " "; inorder_traversal(r->right); }
}
void tree::preorder_traversal(node *r) {
    if(r != NULL) { cout << r->value << " "; preorder_traversal(r->left); preorder_traversal(r->right); }
}
void tree::postorder_traversal(node *r) {
    if(r != NULL) { postorder_traversal(r->left); postorder_traversal(r->right); cout << r->value << " "; }
}
void tree::levelorder_traversal(node *root) {
    queue<node*> que; node *item;
    que.push(root);
    while(!que.empty()) {
        item = que.front(); cout << item->value << " ";
        if(item->left) que.push(item->left);
        if(item->right) que.push(item->right);
        que.pop();
    }
}

int main() {
    tree my_tree;
    my_tree.root = my_tree.insert_node(my_tree.root, 10);
    my_tree.root = my_tree.insert_node(my_tree.root, 5);
    my_tree.root = my_tree.insert_node(my_tree.root, 16);
    my_tree.root = my_tree.insert_node(my_tree.root, 20);
    my_tree.root = my_tree.insert_node(my_tree.root, 15);
    my_tree.root = my_tree.insert_node(my_tree.root, 8);
    my_tree.root = my_tree.insert_node(my_tree.root, 23);
    cout << "In-Order: "; my_tree.inorder_traversal(my_tree.root);
    cout << "\nPre-Order: "; my_tree.preorder_traversal(my_tree.root);
    cout << "\nPost-Order: "; my_tree.postorder_traversal(my_tree.root);
    cout << "\nLevel-Order: "; my_tree.levelorder_traversal(my_tree.root);
}

Kết quả

In-Order Traversal: 5 8 10 15 16 20 23
Pre-Order Traversal: 10 5 8 16 15 20 23
Post-Order Traversal: 8 5 15 23 20 16 10
Level-Order Traversal: 10 5 16 8 15 20 23