help with tree traversal algorithm

[slizorn]

hi guys,
i need to make a tree traversal algorithm that would help me search the tree..
basically i need to read in a text file... shown below

H
H,E,L
E,B,F
B,A,C
A,null,null
c,null,D
D,null,null
F,null,G
G,null,null
L,J,M
J,I,K
I,null,null
K,null,null
M,null,null
 

and then store the 1st line as the root which i can/have done..
next thing is to read the 1st value from the 2nd line and search for it in the tree to see if it exists in the tree.... if it does exist then i should get its position and return the pointer so i can use it later on to store the 2nd and 3rd value of the 2nd line..

i need help in creating this algorithm that searches and returns the pointer to the location of the node that i am searching for...

code for the TreeNode.h

#pragma once
#include <iostream>
#include <fstream>
#include <string>
#include <deque>
#include <queue>
using namespace std;
 
template <class T>
class TreeNode
{
    public:
        TreeNode<T>(T newItem);
        ~TreeNode<T>(void);
        void setItem(T *newItem);
        void setLeft(TreeNode *newLeft);
        void setRight(TreeNode *newRight);
        T getItem();
        T getLeft();
        T getRight();
 
    private:
        T item;
        TreeNode *left;
        TreeNode *right;
};
 
 
template <class T>
TreeNode<T>::TreeNode(T newItem)
{
    item = newItem;
    left = null;
    right = null;
}
 
template <class T>
TreeNode<T>::~TreeNode(void)
{
}
 
 
template <class T>
void TreeNode<T>::setItem(T *newItem) 
{
    // set methods
    item = newItem;
}
 
template <class T>
void TreeNode<T>::setLeft(TreeNode *newLeft) 
{
    left = newLeft;
}
 
template <class T>
void TreeNode<T>::setRight(TreeNode *newRight) 
{
    right = newRight;
}
 
template <class T>
T TreeNode<T>::getItem() 
{
    // get methods
    return item;
}
 
template <class T>
T TreeNode<T>::getLeft() 
{
    return left;
}
 
template <class T>
T TreeNode<T>::getRight() 
{
    return right;
}
 

code for the Tree.h

#pragma once
#include <iostream>
#include <fstream>
#include <string>
#include <deque>
#include <queue>
#include "TreeNode.h"
using namespace std;
 
template <class T>
class Tree
{
 
public:
        Tree<T>(T rootItem);
        ~Tree<T>(void);
        bool isEmpty();
        T getRoot();
        TreeNode<T> root;
 
    private:
        queue<TreeNode<T>> MyQueueForTreeNodes;
};
 
 
template <class T>
Tree<T>::Tree(T rootItem)
{
    root = new TreeNode(rootItem);
}
 
template <class T>
Tree<T>::~Tree(void)
{
}
 
template <class T>
bool Tree<T>::isEmpty() 
{
    // check emtpy
    return root == null;
}
 
template <class T>
T Tree<T>::getRoot() 
{
    // get tree root
    return root;
}
 

code for the main file

#include <iostream>
#include <fstream>
#include <string>
#include <queue>
#include <deque>
#include "TreeNode.h"
#include "Tree.h"
using namespace std;
 
Tree<string> *treeObj = NULL;
 
TreeNode<string>* searchTree(string nodeToAdd)
{
    if(treeObj->getRoot() == nodeToAdd)
    {
//        return treeObj->root;
    }
    else if(treeObj->root.getLeft() == nodeToAdd)
    {
//        return treeObj->root.getLeft();
    }
    else if(treeObj->root.getRight() == nodeToAdd)
    {
//        return treeObj->root.getRight();
    }
    return NULL;
}
 
/*
void insertNode1(TreeNode cur, string fatherItem, string sonItem) 
{
    if (cur == null)
        return;
    if (cur.getItem() == fatherItem) 
    {
        if (cur.getLeft() == null) 
            cur.setLeft(createNode(sonItem));
        else if (cur.getRight() == null) 
            cur.setRight(createNode(sonItem));
        return;
    }
    insertNode1(cur.getLeft(), fatherItem, sonItem);
    insertNode1(cur.getRight(), fatherItem, sonItem);
}
*/
 
void handleOneLine(string string1)
{
    char * cstr, *p;
    int counter;
    string str (string1);
    string data1, data2, data3;
    TreeNode<string> *treeNodeObj = NULL;
 
    cstr = new char [str.size()+1];
    strcpy (cstr, str.c_str());
 
    // cstr now contains a c-string copy of str
 
    int count = 0;
    p=strtok (cstr,",");
    count++;
    while (p!=NULL)
    {
        p=strtok(NULL,",");
        if( count == 1 )
        {            
            data1.append(p);
            treeNodeObj = new TreeNode(data1);
            treeNodeObj->setItem(data1);
        }
        else if( count == 2 )
        {
            data2.append(p);
            treeNodeObj->setLeft(data2);
        }
        else if( count == 3 )
        {
            data3.append(p);
            treeNodeObj->setRight(data3);
        }
 
 
        count++;
        if( count == 3 )
            break;
    }
 
    delete[] cstr; 
}
 
void readFile(string filename1)
{
    char oneline[256];
    ifstream infile(filename1.c_str());
 
    while(infile.good())
    {
        infile.getline(oneline, 256);
 
        if(strlen(oneline) == 0)
        {
            continue;
        }
        else if(strlen(oneline) == 1)
        {
            treeObj->root = oneline.c_str();
        }
        else
        {
            handleOneLine(oneline);
        }
    }
    infile.close();    
} 
 
int main(int argc, char* argv[])
{
//    list<Shape*>::iterator it1;
    char theOption = '0';
    int shapeIndexToModify, indexDelete;
    string FILENAME, fileToWriteTo, addShapeName;
    char oneline[256];
    while(theOption != 'q' && theOption != 'Q')
    {
        cout << "Please choose one of the following options from the menu below:" << endl;
        cout << "---------------------------------------------------------------" << endl;
        cout << "(1) Load information from a text file to create a binary tree" << endl;
        cout << "(2) Traverse and display the tree in pre-order" << endl;
        cout << "(3) Traverse and display the tree in in-order" << endl;  
        cout << "(4) Traverse and display the tree in post-order" << endl;
        cout << "(5) Use tree traversal to count the number of tree nodes" << endl;
        cout << "(6) Insert a node with known father" << endl;
        cout << "(7) Find grandsons of a particular node" << endl;
        cout << "(8) Traverse a tree in a level by level using a queue" << endl;
        cout << "(9) Write tree information into text file" << endl;
        cout << "(Q) Exit" << endl;
        cout << "---------------------------------------------------------------" << endl;
        cin.getline(oneline, 256,'\n');
        theOption = oneline[0];
 
        switch(theOption)
        {
            case '1':
                cout << "Please enter the name of the filename" << endl;
                cin >> FILENAME;
                readFile(FILENAME);
                cout << "File has been read in successfully" << endl;
                break;
 
            case '2':
                cout << "Please enter the name of the shape that you would like to add" << endl;
                cin >> addShapeName;
                //addShape(addShapeName);
                break;
 
            case '3':
                cout << "Please enter the shape's index that you would like to delete" << endl;
                cin >> indexDelete;
                //it1 = mylist.begin();
                for( int i = 0; i < (indexDelete-1); i++)
                {
                    //++it1;
                }
                //mylist.erase(it1); //linkedListObj.DeleteNode(indexDelete);
                cout << "The customer has been deleted" << endl;
                break;
 
            case '4':
                cout << "You have chosen the option to modify a shape based on its index" << endl;
                cout << "Please enter the index of the shape that you would like to modify" << endl;
                cin >> shapeIndexToModify;
                //toBeFound->index = shapeIndexToModify;
                //linkedListObj.FindNode(toBeFound);
                break;
 
            case '5':
                cout << "You have chosen the option to display records!" << endl;
                //DisplayList();
                break;
 
            case '6':
                cout << "You have chosen the option to Save To File" << endl;
                cout << "Please enter the filename that you would like to write to: " << endl;
                cin >> fileToWriteTo;
                //writeToFile(fileToWriteTo);
                cout << endl << "The file has been saved successfully" << endl;
                break;
 
            case '7':
                break;
 
            case '8':
                break;
 
            case '9':
                break;
 
            case 'q':
            case 'Q':
                cout << "You have chosen the option to Quit. Goodbye!" << endl;
                break;
 
            default:
                cout << "Sorry you have entered an invalid choice! Please enter a valid option!" << endl;
                break;
        }
    }
    return 0;
}
 
 

the code that needs editing is

Tree<string> *treeObj = NULL;
 
TreeNode<string>* searchTree(string nodeToAdd)
{
    if(treeObj->getRoot() == nodeToAdd)
    {
//        return treeObj->root;
    }
    else if(treeObj->root.getLeft() == nodeToAdd)
    {
//        return treeObj->root.getLeft();
    }
    else if(treeObj->root.getRight() == nodeToAdd)
    {
//        return treeObj->root.getRight();
    }
    return NULL;
}
 

could u guys tell me how i shd do this properly..? i cant do it and i am lost so as to how i shd go abt solving/doing this method.. please let me know the code for this problem.. thanks :)

[Praxis]

Check the binary search tree traversal implementation in do-ds blog .You can find traversals that don't use recursions.

[sankar2011]

You may check my blog out...

http://bytes.com/topic/c/insights/92...-non-recursive