How to implement if-else branch in a abstract syntax tree using C++

Question

I have a mini AST structure in which each node may have a left and a right child, for example:

class AstNode;
typedef std::shared_ptr<AstNode> AstNodePtr;

class AstNode
{
public:
    AstNode()
        : m_children(2)
    {
    }

    virtual ~AstNode()
    {
    }

    virtual void accept(AstNodeVisitor& visitor) = 0;

    void addLeft(const AstNodePtr& child);
    void addRight(const AstNodePtr& child);
    const AstNodePtr left() const;
    const AstNodePtr right() const;

private:
    std::vector<AstNodePtr> m_children;
};

It works great for the operations I need so far, but when it comes to a branch statement, I don't know how to implement it with this binary tree structure. According to wiki, a branch statement will have 3 leaves:

I can get away with it for now because most of my if statement has no else, so the condition will be the left child, and if-body will be the right child. But it's not going to work with a else-body. I can potentially embed condition in the branch node itself, which means do a pre-order traversal on branch node, but it feels uncomfortable because no other type of nodes involve potential subtree traversal when evaluating itself.

Maybe the AST should not be a binary tree, rather each node can have any number of children, but that will(I think) make the implementation a bit awkward. Any suggestions please?

Answer 1

By the nature, ASTs should be implemented in multi-child trees to support if-condition-then expressions. But a workaround could be having 2 types for IF;

• if-block(left:condition, right:if-body)
• if-body(left:any, right: any)

left child of the if-body is used if condition of the parent is true, right child is used otherwise.