Tree Traversals

In-Order: depth-first

Visit left, visit root, visit right

Note: in-order traversals is only applicable to binary trees (not for N-ary trees)

template<typename Type>
void Binary_tree<Type>::in_order_traversal() const {
    if (empty()) {
        return;
    }

    left()->in_order_traversal();
    cout << retrieve();
    right()->in_order_traversal();
}

Example: Pretty Printing

class Expression_node;

void Expression_node::pretty_print() {
    if (!left()) {
        if (parent()->predence() > precedence()) {
            cout << "(";
        }
    }

    left()->pretty_print();
}



In [ ]: