Expression Trees
Inorder Traversal
1. Traverse the left subtree
2. Visit the node
3. Traverse the right subtree
class ExpressionTree
{
public:
void InorderTraverse() const;
...
private:
struct Node { ... };
Node* root;
void InorderTraverse( /* in */ Node* ptr )
const;
};
void
ExpressionTree::InorderTraverse() const
{
InorderTraverse( root );
}
void
ExpressionTree::InorderTraverse( /* in */ Node* ptr ) const
{
if ( ptr != NULL )
{
InorderTraverse( ptr->left );
cout << ptr->key;
InorderTraverse( ptr->right );
}
}
Postorder Traversal
1. Traverse the left subtree
2. Traverse the right subtree
3. Visit the node
class ExpressionTree
{
public:
void PostorderTraverse() const;
...
private:
...
void PostorderTraverse( /* in */ Node* ptr
) const;
};
void
ExpressionTree:: PostorderTraverse() const
{
PostorderTraverse( root );
}
void ExpressionTree::
PostorderTraverse( /* in */ Node* ptr ) const
{
if ( ptr != NULL )
{
PostorderTraverse( ptr->left );
PostorderTraverse( ptr->right );
cout << ptr->key;
}
}