Duyệt cây Preorder (Tiền tự) trong cấu trúc dữ liệu

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

Ví dụ cây:

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

Thuật toán

preorderTraverse(root):
Begin
    if root not empty:
        print root value
        preorderTraversal(left of root)
        preorderTraversal(right of root)
    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 preorder_traversal(node *r);
    node* insert_node(node *root, int key);
};

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

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

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

Kết quả

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