472,989 Members | 2,773 Online

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

34
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.
13. {
15.     {
16. //        return treeObj->root;
17.     }
19.     {
20. //        return treeObj->root.getLeft();
21.     }
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.
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;
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;
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;
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.                 }
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;
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.
4. {
6.     {
7. //        return treeObj->root;
8.     }
10.     {
11. //        return treeObj->root.getLeft();
12.     }
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 5 '08 #1
2 2609
weaknessforcats
9,208 Expert Mod 8TB
Is this for a class you are taking?

If not, you should be using a map.
Sep 5 '08 #2
weaknessforcats
9,208 Expert Mod 8TB