Connecting Tech Pros Worldwide Help | Site Map
bytes > topic > c > answers

help with creating a method to search a tree to find the position of node and..

Member
  
Join Date: Jul 2008
Posts: 34
#1: Sep 5 '08
hi guys,
i need to make a tree traversal algorithm that would help me search the tree..
creating a method to search a tree to find the position of node and to return its pointer value
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.  
  117. int main(int argc, char* argv[])
  118. {
  119. //    list<Shape*>::iterator it1;
  120.     char theOption = '0';
  121.     int shapeIndexToModify, indexDelete;
  122.     string FILENAME, fileToWriteTo, addShapeName;
  123.     char oneline[256];
  124.     while(theOption != 'q' && theOption != 'Q')
  125.     {
  126.         cout << "Please choose one of the following options from the menu below:" << endl;
  127.         cout << "---------------------------------------------------------------" << endl;
  128.         cout << "(1) Load information from a text file to create a binary tree" << endl;
  129.         cout << "(2) Traverse and display the tree in pre-order" << endl;
  130.         cout << "(3) Traverse and display the tree in in-order" << endl;  
  131.         cout << "(4) Traverse and display the tree in post-order" << endl;
  132.         cout << "(5) Use tree traversal to count the number of tree nodes" << endl;
  133.         cout << "(6) Insert a node with known father" << endl;
  134.         cout << "(7) Find grandsons of a particular node" << endl;
  135.         cout << "(8) Traverse a tree in a level by level using a queue" << endl;
  136.         cout << "(9) Write tree information into text file" << endl;
  137.         cout << "(Q) Exit" << endl;
  138.         cout << "---------------------------------------------------------------" << endl;
  139.         cin.getline(oneline, 256,'\n');
  140.         theOption = oneline[0];
  141.  
  142.         switch(theOption)
  143.         {
  144.             case '1':
  145.                 cout << "Please enter the name of the filename" << endl;
  146.                 cin >> FILENAME;
  147.                 readFile(FILENAME);
  148.                 cout << "File has been read in successfully" << endl;
  149.                 break;
  150.  
  151.             case '2':
  152.                 cout << "Please enter the name of the shape that you would like to add" << endl;
  153.                 cin >> addShapeName;
  154.                 //addShape(addShapeName);
  155.                 break;
  156.  
  157.             case '3':
  158.                 cout << "Please enter the shape's index that you would like to delete" << endl;
  159.                 cin >> indexDelete;
  160.                 //it1 = mylist.begin();
  161.                 for( int i = 0; i < (indexDelete-1); i++)
  162.                 {
  163.                     //++it1;
  164.                 }
  165.                 //mylist.erase(it1); //linkedListObj.DeleteNode(indexDelete);
  166.                 cout << "The customer has been deleted" << endl;
  167.                 break;
  168.  
  169.             case '4':
  170.                 cout << "You have chosen the option to modify a shape based on its index" << endl;
  171.                 cout << "Please enter the index of the shape that you would like to modify" << endl;
  172.                 cin >> shapeIndexToModify;
  173.                 //toBeFound->index = shapeIndexToModify;
  174.                 //linkedListObj.FindNode(toBeFound);
  175.                 break;
  176.  
  177.             case '5':
  178.                 cout << "You have chosen the option to display records!" << endl;
  179.                 //DisplayList();
  180.                 break;
  181.  
  182.             case '6':
  183.                 cout << "You have chosen the option to Save To File" << endl;
  184.                 cout << "Please enter the filename that you would like to write to: " << endl;
  185.                 cin >> fileToWriteTo;
  186.                 //writeToFile(fileToWriteTo);
  187.                 cout << endl << "The file has been saved successfully" << endl;
  188.                 break;
  189.  
  190.             case '7':
  191.                 break;
  192.  
  193.             case '8':
  194.                 break;
  195.  
  196.             case '9':
  197.                 break;
  198.  
  199.             case 'q':
  200.             case 'Q':
  201.                 cout << "You have chosen the option to Quit. Goodbye!" << endl;
  202.                 break;
  203.  
  204.             default:
  205.                 cout << "Sorry you have entered an invalid choice! Please enter a valid option!" << endl;
  206.                 break;
  207.         }
  208.     }
  209.     return 0;
  210. }
  211.  
  212.  
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 :)
Moderator
  
Join Date: Mar 2007
Location: North Bend Washington USA
Posts: 5,366
#2: Sep 5 '08

re: help with creating a method to search a tree to find the position of node and..

Is this for a class you are taking?

If not, you should be using a map.
Moderator
  
Join Date: Mar 2007
Location: North Bend Washington USA
Posts: 5,366
#3: Sep 5 '08

re: help with creating a method to search a tree to find the position of node and..

Please do not double post: help with tree traversal algorithm.
Reply

« previous question | next question »

Similar C / C++ bytes

/bytes/development

/bytes/it

/bytes/about

We are a network of experts and professionals in IT and software development that help one another with answers to tough questions and share insights. Get the best answers to your questions from over 226,358 network members.

dev questions:
algorithms | asp | asp.net | c/c++ | coldfusion | c# | flash | html/css | java | javascript |
mobile dev | .net | perl | php | python | ruby | software dev | vb.net | visual basic | xml
it questions:
access | apache | careers | db2 | iis | macosx | mysql | networking | oracle | postgresql | sql server | unix | windows

About Bytes | Copyright 1995-2009 BYTES. All rights Reserved