Expression Tree printLevel() function

Question

I am implementing a tree which is a Binary Expression Tree. The leaf nodes are numbers, non-leaf nodes are math operators. Succesfully implemented printInorder,PostOrder, PreOrder, evaluate. But stucked with the printLevel().

Here is my int main ()

int main()
{
    EXTree myTree;
    string tests[] = {"2.1*3.1+4.2", "(2.0+1.3)/1.4", "2.*(1.3+1.4)","1.2*(1.3+1.4/0.5)","1.2*(1.3+1.4/0.5)-4.4", "1.2*(1.3+1.4/0.5)- (9/3)"};
    for (int i=0; i < 6; i++)
    {
        myTree.build (tests[i]);
        myTree.printInorder();
        myTree.printPreorder();
        myTree.printPostorder();
        myTree.printLevel(); //Starting from level = 0
        cout << "Evaulating myTree = " << format(myTree.evaluate(),2) << endl;
        myTree.removeAll(); // removes all the nodes
    }
}

printLevel(); only prints the level of the tree given above and its initally 0.

and here is my printLevel function.

void EXTree:: printLevel()
{
    queue<Node*> levelq;

    levelq.push(root);
    cout << "Current Level is: ";
    while( levelq.size() > 0 )
    {
        Node *cur = levelq.front();
        cout << cur->Root << "  ";
        levelq.pop();
        if (cur->Left)  levelq.push(cur->Left);
        if (cur->Right) levelq.push(cur->Right);
    }
    cout << endl;
}

But I really didnt understand how to implement the printLevel. Appreciate for any help to clarify it.

I just implemented the inOrder algorith to my printLevel and tried to change it but still didnt get it.

Answer 1

Since you have no problem with recursion, this would work without queue:

void EXTree:: printLevel()
{
    int currentLevel = 0;
    if (root)
    {
        cout << "Current Level is: ";
        printLevelHelper(root,currentLevel);
    }
    else
        cout << "This BST is Empty\n";
}

// Declare a private method:
void EXTree:: printLevelHelper(Node* &n, int &currentLevel)
{
    cout << currentLevel << ' ';
    if (n->Left)
    {
        currentLevel++;
        printLevelHelper(n->Left,currentLevel);
        currentLevel--;
    }
    if (n->Right)
    {
        currentLevel++;
        printLevelHelper(n->Right,currentLevel);
        currentLevel--;
    }
}

Answer 2

When using Breadth First Search to print the nodes on one level immediately adjacent to each other, you'd just observe when the leftmost child of the leftmost node on the current level pops out of the queue: this must be the start of the next level. I could easily write the code but I'd guess it would incomprehensible for you and this homework is for you (I think you want to label your post appropriately as homework, BTW). Most of your implementation looks like a straight forward implementation. The only thing missing is detecting that the next level is reached.