DaniWeb Forum Index > Software Development > C++

C++ RSS

Tree Traversal

Please support our C++ advertiser: Intel Parallel Studio Home

•

Join Date: Nov 2006

Posts: 202

Reputation: n.aggel is an unknown quantity at this point

Solved Threads: 11

n.aggel

Offline

Posting Whiz in Training

Tree Traversal

Aug 12th, 2007

In order to traverse a tree you could use something like this:

For inorder traversal:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
 
inorder(TreeNode* currentNode)
{
    if (currentNode) {
       inorder(currentNode->LeftChild);
       cout << currentNode->data;
       inorder(currentNode->RightChild);
    }
}
inorder(TreeNode* currentNode)
{
    if (currentNode) {
       inorder(currentNode->LeftChild);
       cout << currentNode->data;
       inorder(currentNode->RightChild);
    }
}

For preorder traversal:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
preorder(TreeNode* currentNode)
{
    if (currentNode) {
        cout << currentNode->data;
        preorder(currentNode->LeftChild);
        preorder(currentNode->RightChild);
    }
}
preorder(TreeNode* currentNode)
{
    if (currentNode) {
        cout << currentNode->data;
        preorder(currentNode->LeftChild);
        preorder(currentNode->RightChild);
    }
}

For post order traversal:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
postorder(TreeNode* currentNode)
{
    if (currentNode) {
        postorder(currentNode->LeftChild);
        postorder(currentNode->RightChild);
        cout << currentNode->data;
    }
}
postorder(TreeNode* currentNode)
{
    if (currentNode) {
        postorder(currentNode->LeftChild);
        postorder(currentNode->RightChild);
        cout << currentNode->data;
    }
}

For level order traversal:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
LevelOrder(TreeNode* root)
{
   Queue q<TreeNode*>;
   TreeNode* currentNode = root;
 
    while (currentNode) {
        cout << currentNode->data;
        if (currentNode->LeftChild) q.Add(currentNode->LeftChild);
        if (currentNode->RightChild) q.Add(currentNode->RightChild);
        currentNode = q.Delete(); //q.Delete returns a node pointer
    }
}
LevelOrder(TreeNode* root)
{
   Queue q<TreeNode*>;
   TreeNode* currentNode = root;
       
    while (currentNode) {
        cout << currentNode->data;
        if (currentNode->LeftChild) q.Add(currentNode->LeftChild);
        if (currentNode->RightChild) q.Add(currentNode->RightChild);
        currentNode = q.Delete(); //q.Delete returns a node pointer
    }
}

The question is:

How can i make it a bit more graphical......
i mean that with the above methods the output is a list of numbers... is there anyway to modify this code so that i can have a nicer output?

PS: if you give example for one kind of traversal i will find the others by myself

Thanks again for your help....

•

Join Date: Aug 2005

Posts: 5,264

Reputation: iamthwee is a splendid one to behold

Solved Threads: 377

iamthwee

Offline

Posting Expert

Re: Tree Traversal

Aug 12th, 2007

I don't think this is easy, the ones that I have seen that look half ok are the ones that plot the tree on its side.

The ones that work the best use a gdi. Drawing that in the console window is always going to be a pain in the ...

*Voted best profile in the world*