By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
435,255 Members | 2,717 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,255 IT Pros & Developers. It's quick & easy.

help with tree traversal algorithm

P: 34
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
Expand|Select|Wrap|Line Numbers
  1. H
  2. H,E,L
  3. E,B,F
  4. B,A,C
  5. A,null,null
  6. c,null,D
  7. D,null,null
  8. F,null,G
  9. G,null,null
  10. L,J,M
  11. J,I,K
  12. I,null,null
  13. K,null,null
  14. M,null,null
  15.  
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
Expand|Select|Wrap|Line Numbers
  1. #pragma once
  2. #include <iostream>
  3. #include <fstream>
  4. #include <string>
  5. #include <deque>
  6. #include <queue>
  7. using namespace std;
  8.  
  9. template <class T>
  10. class TreeNode
  11. {
  12.     public:
  13.         TreeNode<T>(T newItem);
  14.         ~TreeNode<T>(void);
  15.         void setItem(T *newItem);
  16.         void setLeft(TreeNode *newLeft);
  17.         void setRight(TreeNode *newRight);
  18.         T getItem();
  19.         T getLeft();
  20.         T getRight();
  21.  
  22.     private:
  23.         T item;
  24.         TreeNode *left;
  25.         TreeNode *right;
  26. };
  27.  
  28.  
  29. template <class T>
  30. TreeNode<T>::TreeNode(T newItem)
  31. {
  32.     item = newItem;
  33.     left = null;
  34.     right = null;
  35. }
  36.  
  37. template <class T>
  38. TreeNode<T>::~TreeNode(void)
  39. {
  40. }
  41.  
  42.  
  43. template <class T>
  44. void TreeNode<T>::setItem(T *newItem) 
  45. {
  46.     // set methods
  47.     item = newItem;
  48. }
  49.  
  50. template <class T>
  51. void TreeNode<T>::setLeft(TreeNode *newLeft) 
  52. {
  53.     left = newLeft;
  54. }
  55.  
  56. template <class T>
  57. void TreeNode<T>::setRight(TreeNode *newRight) 
  58. {
  59.     right = newRight;
  60. }
  61.  
  62. template <class T>
  63. T TreeNode<T>::getItem() 
  64. {
  65.     // get methods
  66.     return item;
  67. }
  68.  
  69. template <class T>
  70. T TreeNode<T>::getLeft() 
  71. {
  72.     return left;
  73. }
  74.  
  75. template <class T>
  76. T TreeNode<T>::getRight() 
  77. {
  78.     return right;
  79. }
  80.  
code for the Tree.h
Expand|Select|Wrap|Line Numbers
  1. #pragma once
  2. #include <iostream>
  3. #include <fstream>
  4. #include <string>
  5. #include <deque>
  6. #include <queue>
  7. #include "TreeNode.h"
  8. using namespace std;
  9.  
  10. template <class T>
  11. class Tree
  12. {
  13.  
  14. public:
  15.         Tree<T>(T rootItem);
  16.         ~Tree<T>(void);
  17.         bool isEmpty();
  18.         T getRoot();
  19.         TreeNode<T> root;
  20.  
  21.     private:
  22.         queue<TreeNode<T>> MyQueueForTreeNodes;
  23. };
  24.  
  25.  
  26. template <class T>
  27. Tree<T>::Tree(T rootItem)
  28. {
  29.     root = new TreeNode(rootItem);
  30. }
  31.  
  32. template <class T>
  33. Tree<T>::~Tree(void)
  34. {
  35. }
  36.  
  37. template <class T>
  38. bool Tree<T>::isEmpty() 
  39. {
  40.     // check emtpy
  41.     return root == null;
  42. }
  43.  
  44. template <class T>
  45. T Tree<T>::getRoot() 
  46. {
  47.     // get tree root
  48.     return root;
  49. }
  50.  
code for the main file
Expand|Select|Wrap|Line Numbers
  1. #include <iostream>
  2. #include <fstream>
  3. #include <string>
  4. #include <queue>
  5. #include <deque>
  6. #include "TreeNode.h"
  7. #include "Tree.h"
  8. using namespace std;
  9.  
  10. Tree<string> *treeObj = NULL;
  11.  
  12. TreeNode<string>* searchTree(string nodeToAdd)
  13. {
  14.     if(treeObj->getRoot() == nodeToAdd)
  15.     {
  16. //        return treeObj->root;
  17.     }
  18.     else if(treeObj->root.getLeft() == nodeToAdd)
  19.     {
  20. //        return treeObj->root.getLeft();
  21.     }
  22.     else if(treeObj->root.getRight() == nodeToAdd)
  23.     {
  24. //        return treeObj->root.getRight();
  25.     }
  26.     return NULL;
  27. }
  28.  
  29. /*
  30. void insertNode1(TreeNode cur, string fatherItem, string sonItem) 
  31. {
  32.     if (cur == null)
  33.         return;
  34.     if (cur.getItem() == fatherItem) 
  35.     {
  36.         if (cur.getLeft() == null) 
  37.             cur.setLeft(createNode(sonItem));
  38.         else if (cur.getRight() == null) 
  39.             cur.setRight(createNode(sonItem));
  40.         return;
  41.     }
  42.     insertNode1(cur.getLeft(), fatherItem, sonItem);
  43.     insertNode1(cur.getRight(), fatherItem, sonItem);
  44. }
  45. */
  46.  
  47. void handleOneLine(string string1)
  48. {
  49.     char * cstr, *p;
  50.     int counter;
  51.     string str (string1);
  52.     string data1, data2, data3;
  53.     TreeNode<string> *treeNodeObj = NULL;
  54.  
  55.     cstr = new char [str.size()+1];
  56.     strcpy (cstr, str.c_str());
  57.  
  58.     // cstr now contains a c-string copy of str
  59.  
  60.     int count = 0;
  61.     p=strtok (cstr,",");
  62.     count++;
  63.     while (p!=NULL)
  64.     {
  65.         p=strtok(NULL,",");
  66.         if( count == 1 )
  67.         {            
  68.             data1.append(p);
  69.             treeNodeObj = new TreeNode(data1);
  70.             treeNodeObj->setItem(data1);
  71.         }
  72.         else if( count == 2 )
  73.         {
  74.             data2.append(p);
  75.             treeNodeObj->setLeft(data2);
  76.         }
  77.         else if( count == 3 )
  78.         {
  79.             data3.append(p);
  80.             treeNodeObj->setRight(data3);
  81.         }
  82.  
  83.  
  84.         count++;
  85.         if( count == 3 )
  86.             break;
  87.     }
  88.  
  89.     delete[] cstr; 
  90. }
  91.  
  92. void readFile(string filename1)
  93. {
  94.     char oneline[256];
  95.     ifstream infile(filename1.c_str());
  96.  
  97.     while(infile.good())
  98.     {
  99.         infile.getline(oneline, 256);
  100.  
  101.         if(strlen(oneline) == 0)
  102.         {
  103.             continue;
  104.         }
  105.         else if(strlen(oneline) == 1)
  106.         {
  107.             treeObj->root = oneline.c_str();
  108.         }
  109.         else
  110.         {
  111.             handleOneLine(oneline);
  112.         }
  113.     }
  114.     infile.close();    
  115.  
  116. int main(int argc, char* argv[])
  117. {
  118. //    list<Shape*>::iterator it1;
  119.     char theOption = '0';
  120.     int shapeIndexToModify, indexDelete;
  121.     string FILENAME, fileToWriteTo, addShapeName;
  122.     char oneline[256];
  123.     while(theOption != 'q' && theOption != 'Q')
  124.     {
  125.         cout << "Please choose one of the following options from the menu below:" << endl;
  126.         cout << "---------------------------------------------------------------" << endl;
  127.         cout << "(1) Load information from a text file to create a binary tree" << endl;
  128.         cout << "(2) Traverse and display the tree in pre-order" << endl;
  129.         cout << "(3) Traverse and display the tree in in-order" << endl;  
  130.         cout << "(4) Traverse and display the tree in post-order" << endl;
  131.         cout << "(5) Use tree traversal to count the number of tree nodes" << endl;
  132.         cout << "(6) Insert a node with known father" << endl;
  133.         cout << "(7) Find grandsons of a particular node" << endl;
  134.         cout << "(8) Traverse a tree in a level by level using a queue" << endl;
  135.         cout << "(9) Write tree information into text file" << endl;
  136.         cout << "(Q) Exit" << endl;
  137.         cout << "---------------------------------------------------------------" << endl;
  138.         cin.getline(oneline, 256,'\n');
  139.         theOption = oneline[0];
  140.  
  141.         switch(theOption)
  142.         {
  143.             case '1':
  144.                 cout << "Please enter the name of the filename" << endl;
  145.                 cin >> FILENAME;
  146.                 readFile(FILENAME);
  147.                 cout << "File has been read in successfully" << endl;
  148.                 break;
  149.  
  150.             case '2':
  151.                 cout << "Please enter the name of the shape that you would like to add" << endl;
  152.                 cin >> addShapeName;
  153.                 //addShape(addShapeName);
  154.                 break;
  155.  
  156.             case '3':
  157.                 cout << "Please enter the shape's index that you would like to delete" << endl;
  158.                 cin >> indexDelete;
  159.                 //it1 = mylist.begin();
  160.                 for( int i = 0; i < (indexDelete-1); i++)
  161.                 {
  162.                     //++it1;
  163.                 }
  164.                 //mylist.erase(it1); //linkedListObj.DeleteNode(indexDelete);
  165.                 cout << "The customer has been deleted" << endl;
  166.                 break;
  167.  
  168.             case '4':
  169.                 cout << "You have chosen the option to modify a shape based on its index" << endl;
  170.                 cout << "Please enter the index of the shape that you would like to modify" << endl;
  171.                 cin >> shapeIndexToModify;
  172.                 //toBeFound->index = shapeIndexToModify;
  173.                 //linkedListObj.FindNode(toBeFound);
  174.                 break;
  175.  
  176.             case '5':
  177.                 cout << "You have chosen the option to display records!" << endl;
  178.                 //DisplayList();
  179.                 break;
  180.  
  181.             case '6':
  182.                 cout << "You have chosen the option to Save To File" << endl;
  183.                 cout << "Please enter the filename that you would like to write to: " << endl;
  184.                 cin >> fileToWriteTo;
  185.                 //writeToFile(fileToWriteTo);
  186.                 cout << endl << "The file has been saved successfully" << endl;
  187.                 break;
  188.  
  189.             case '7':
  190.                 break;
  191.  
  192.             case '8':
  193.                 break;
  194.  
  195.             case '9':
  196.                 break;
  197.  
  198.             case 'q':
  199.             case 'Q':
  200.                 cout << "You have chosen the option to Quit. Goodbye!" << endl;
  201.                 break;
  202.  
  203.             default:
  204.                 cout << "Sorry you have entered an invalid choice! Please enter a valid option!" << endl;
  205.                 break;
  206.         }
  207.     }
  208.     return 0;
  209. }
  210.  
  211.  
the code that needs editing is
Expand|Select|Wrap|Line Numbers
  1. Tree<string> *treeObj = NULL;
  2.  
  3. TreeNode<string>* searchTree(string nodeToAdd)
  4. {
  5.     if(treeObj->getRoot() == nodeToAdd)
  6.     {
  7. //        return treeObj->root;
  8.     }
  9.     else if(treeObj->root.getLeft() == nodeToAdd)
  10.     {
  11. //        return treeObj->root.getLeft();
  12.     }
  13.     else if(treeObj->root.getRight() == nodeToAdd)
  14.     {
  15. //        return treeObj->root.getRight();
  16.     }
  17.     return NULL;
  18. }
  19.  
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 :)
Sep 4 '08 #1
Share this Question
Share on Google+
2 Replies


P: 1
Check the binary search tree traversal implementation in do-ds blog .You can find traversals that don't use recursions.
Sep 20 '08 #2

P: 18

Post your reply

Sign in to post your reply or Sign up for a free account.