Duyệt cây Postorder (Hậu tự) trong cấu trúc dữ liệu

Phần này trình bày kỹ thuật duyệt post-order (hậu tự) (đệ quy) cho cây tìm kiếm nhị phân.

Ví dụ cây:

Thứ tự duyệt postorder: 8, 5, 15, 23, 20, 16, 10

Thuật toán

postorderTraverse(root):
Begin
    if root not empty:
        postorderTraversal(left of root)
        postorderTraversal(right of root)
        print root value
    end if
End

Ví dụ C++

#include <iostream>
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 postorder_traversal(node *r);
    node* insert_node(node *root, int key);
};

// get_node, insert_node giống bài BST

void tree::postorder_traversal(node *r) {
    if(r != NULL) {
        postorder_traversal(r->left);
        postorder_traversal(r->right);
        cout << r->value << " ";
    }
}

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 << "Post-Order Traversal: ";
    my_tree.postorder_traversal(my_tree.root);
}

Kết quả

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