Binary Search Tree.. can help with the pseudocode?

[sylvia]

i have a problem with BST...

can anybody explain the algorithm or pseudocode for the following?

1) searching for a value in a tree
2) inserting specified number of values to a tree
3) deleting a value/values from a tree
4) printing out the minimum value in a tree
5) printing out the BST using inorder
6) removing all nodes from BST
7) quitting the program(how do i quit the program when the user inputs 'q'?)
8) how i do traversal(inorder)?
9) deleting the entire tree

and how do i call a function?
i wanna try out the code by calling certain functions in a class.

thx in advance

[sylvia]

i am supposed to use pointers.. so is it ok if u could explain with the help of pointers?

sorry about this new reply.. forgot to include in my prev. post

[nspils]

How much do you understand about general tree/search algorithms? There is ALOT of information which you need to master in order to understand these. Use your text book, find a book, search on the internet. You are not likely to find someone willing to just give you the work that he/she did and which you are trying to get out of ...

The binary tree is based upon the concept that the "root" node has a larger value then its left child, and a smaller value than its right child

therefore, if you move to a left child you are moving to a smaller value, to a right child you are moving to a larger value.

Search:

Is the root the value I'm looking for? If yes, I'm done
Is the value in root larger than the value I'm looking for?
if yes,
if there is no left child, stop - you did not find the value in the tree
if there is a left child, move to the left child , recursively call this search using the left child as the "root"
else
if there is no right child, stop - you did not find the value in the tree
if there is a right child, move to the right child, recursively call this search using the right child as the "root"

Insert:
Is the value in the root equal to the value? If yes, I'm done (if this is a set)
Is the value in the root larger than the value I'm looking for?
if yes,
if there is no left child, insert this value in the tree as the left child
if there is a left child, move to the left child, recursively call this insert
else
if there is no right child, insert the value in the tree as the right child
if there is a right child, move to the right child, recursively call this insert

OTHERWISE, use search, if the value is not in the tree, return the node which was the last node you looked at, it will become the "root" of this sub-tree, the place where you will be inserting, then insert at that location as left or right child, as appropriate ...

Delete - search - if found, delete, making appropriate new parent/child connection as your situation may require

Print minimum - go root, move left, move left, move left until there is no left child - that is your minimum value

Your inorder searches are a recursive call to move left, visit, move right ... whether your visit is to print out or do some other function ...

[sylvia]

i'll give my question here just to tell you guys what i have to do so that you might better understand the question...

Description:
You will need to implement the BST functions in Tree.cpp.
For the BinarySearchTree class, the Root node is kept as a pointer .
The major functions are:
bool Insert(TreeItemType item)
- Input: an item to be inserted to the BST. Note that TreeItemType is defined to be string.
- Return Type: true/false depends on whether the insertion is successful.
- Purpose: Insert "item" into the BST. If "item" already exists in BST, return false.
bool Delete(TreeItemType item)
- Input: an item to be deleted from the BST.
- Return Type: true/false depends on whether the deletion is successful.
- Purpose: Remove "item" from the BST. If "item" is not in the BST, the deletion request fails and return false.
int Search(TreeItemType item)
- Input: item to be searched in the BST.
- Return: -1 if item cannot be found
n where n is the number of links followed.
e.g. for the BST
6
4 8
1 5

Search for 9, result is -1 (not found)
Search for 6, result is 0 (found, no link is traversed)
Search for 5, result is 2 (found, 2 links followed:6->4 then 4->5)
Search for 8, result is 1 (found, 1 link followed:6-> 8 )
- Purpose: Search for "item" in the BST.
void InorderTraversal()
- Input: None.
- Return: None.
- Purpose: Prints all nodes in the BST following the inorder
for example, given the same BST in the example above:
6
4 8
1 5
the output will be: 1 4 5 6 8
for the BST below:
6
4
1
the output will be: 1 4 6
for an empty BST, the output will be a new line
void DeleteAll()
- Input: None.
- Return: None.
- Purpose: Delete all nodes from the BST.
TreeItemType BinarySearchTree::FindMinimum()
- Input: None
- Return: The minimum item in BST or an empty string
- Purpose: Find the minimum item of BST
Since BST is built on top of manually allocated tree nodes, you need to implement the destructor to deallocate the nodes properly:
~BinarySearchTree()
- Purpose: Deallocate all tree nodes.
you are given a main program (testTree.cpp) to test your implementation. The main program should accept the following commands:
i n #"i" followed by a number n. e.g. "i 4". Where n is the number of values to be inserted into the BST.
#after this command, you can accept n items.

m # to print the minimum item
# if BST is empty, print "endl".

s # to search, e.g. "s"
# after this command, you can accept one item to search.

d # to delete, e.g. "d ".
# after this command, you can accept one item to be deleted

p #Print out the BST using inorder.

D #remove ALL nodes from BST

q #quit the program

Sample input/output:
Typical Session(note that you are NOT supposed to print out the word "I:" and "O:" and whater precedes by "//"):
I:i 1 //(1 value to be inserted)
I:huang //huang is inserted to BST
I: p
O:huang
I:i 3 //(3 values to be entered)
I:li huang chua
O:huang not inserted
I: p
O:chua huang li
I:i 2
I:wong leong
I: p
O:chua huang leong li wong
I:m
O:chua
I:s
I:huang
O:huang found - 0 links
I:s
I:neo
O:neo not found
I:d
I:leong
I: p
O:chua huang li wong
I:d
I:leong
O:leong not deleted
I: D
I: p
O: // an empty line
I:m
O: // an empty line
I:q
O: Program terminated. Bye!
Hints:
You need to implement the recursive functions as private functions in the BinarySearchTree class. And the public methods like Insert(), Delete() etc are just a wrapper functions. e.g.
class BinarySearchTree
{
....
private:
TreeNode* DeleteTree(TreeNode*, const TreeItemType&)
throw (TreeException);
public:
bool Insert(TreeItemType); //this method utilize the DeleteTree to do the job.
}

.cpp and .h files in the next post.. sorry

[sylvia]

. Tree.h is the following

1 #include <stdexcept>
2 #include <string>
3 using namespace std;
4
5 typedef string TreeItemType;
6
7 template <class T> T max (T a, T b) {return a > b ? a : b;};
8
9 class TreeException: public logic_error
10 {
11 public:
12 TreeException(const string & message="")
13 :logic_error(message.c_str())
14 {}
15 };
16
17
18 class TreeNode {
19
20 private:
21 TreeItemType item_;
22 TreeNode *left_;
23 TreeNode *right_;
24 friend class BinarySearchTree;
25
26 public:
27 TreeNode(TreeItemType i){ item_ = i; left_ = right_ = NULL;};
28 };
29
30 class BinarySearchTree
31 {
32 private:
33 TreeNode* root_;
34
35 void DeleteWholeTree(TreeNode*);
36
37 TreeNode* InsertTree(TreeNode*, const TreeItemType&)
38 throw (TreeException);
39 TreeNode* DeleteTree(TreeNode*, const TreeItemType&)
40 throw (TreeException);
41 int SearchTree(const TreeNode*, const TreeItemType,int);
42 void Traversal(const TreeNode*, int);
43 TreeItemType FindMin(const TreeNode*);
44
45 public:
46 BinarySearchTree() {root_ = NULL;};
47 ~BinarySearchTree();
48
49 bool Insert(TreeItemType);
50 bool Delete(TreeItemType);
51 void DeleteAll();
52 int Search(TreeItemType);
53 void InorderTraversal();
54 TreeItemType FindMinimum();
55 };

[sylvia]

Tree.cpp is the following

1 #include < iostream >
2 #include "Tree.h"
3
4 using namespace std;
5
6 BinarySearchTree::~BinarySearchTree()
7 {
8 DeleteWholeTree(root_);
9 }
10
11 void BinarySearchTree::DeleteWholeTree ( TreeNode* tnPtr )
12 {
13 // add your code here to delete the whole tree
14 }
15
16
17 TreeNode* BinarySearchTree::InsertTree ( TreeNode* tnPtr,
18 const TreeItemType& item )
19 throw ( TreeException )
20 {
21 // add your code here for insertion of item
22 }
23
24 TreeNode* BinarySearchTree::DeleteTree ( TreeNode* tnPtr,
25 const TreeItemType& item )
26 throw ( TreeException )
27 {
28 // add your code here to delete item
29 }
30
31 int BinarySearchTree::SearchTree ( const TreeNode* tnPtr,
32 const TreeItemType item, int nLinks )
33 {
34 // add your code here to search an item
35 // retun the number of links from root
36 }
37
38 void BinarySearchTree::Traversal ( const TreeNode* tnPtr,int mode )
39 {
40 // add your code here to traversal ( inorder )
41 }
42
43 TreeItemType BinarySearchTree::FindMin ( const TreeNode* tnPtr )
44 {
45 // add your code here to find minimum item
46 }
47
48 TreeItemType BinarySearchTree::FindMinimum()
49 {
50 // add your code here to call FindMin
51 }
52
53 bool BinarySearchTree::Insert ( TreeItemType item )
54 {
55 // add your code here to call InsertTree
56 }
57
58 bool BinarySearchTree::Delete ( TreeItemType item )
59 {
60 // add your code here to call DeteteTree
61 }
62
63 void BinarySearchTree::DeleteAll()
64 {
65 // add your code here to call DeleteWholeTree
66 }
67
68 int BinarySearchTree::Search ( const TreeItemType item )
69 {
70 // add your code here to call SearchTree
71 }
72
73 void BinarySearchTree::InorderTraversal()
74 {
75
76 // add your code here to call Traversal
77 }

[sylvia]

testTree.cpp file is the following

9 #include <iostream>
10 #include <cstdio>
11 #include "Tree.h"
12
13 using namespace std;
14
15 int main () {
16 char s[100];
17 bool quit = false;
18 BinarySearchTree bst;
19 int i,n;
20 string item;
21
22 while (!quit)
23 {
24 cin.getline (s, 100);
25
26
27 switch (s[0])
28 {
29 case 'i':
30 // insertion
31 sscanf (&s[2], "%d ", &n);
32 for (i = 0; i < n; i++){
33 cin >> item;
34 if (!bst.Insert(item)){
35 cout << item << " not inserted" << endl;
36 }
37 }
38 break;
39
40 case 'm':
41 // print minimum
42 item=bst.FindMinimum();
43 if (item.empty())
44 cout << endl;
45 else
46 cout << item << endl;
47 break;
48 case 's':
49 // search
50 cin >> item;
51 n = bst.Search(item);
52 cout << item;
53 if (n == -1){
54 cout << " not found" << endl;
55 } else {
56 cout << " found - " << n << " links" << endl;
57 }
58 break;
59
60 case 'd':
61 // delete
62 cin >> item;
63 if (!bst.Delete(item)){
64 cout << item << " not deleted" << endl;
65 }
66 break;
67
68 case 'D':
69 // delete the whole tree
70 bst.DeleteAll();
71 break;
72
73 case 'p':
74 // inorder print
75 bst.InorderTraversal();
76 break;
77
78 case 'q':
79 // quit
80 quit = true;
81 break;
82
83 }
84
85 }
86 cout << "Program terminated. Bye!" << endl;
87 return 0;
88 } //end main
89

The above .cpp and .h files are all given by the professor. I did not create them. All I have to do is just implement them. Can anybody help me with this?? plz!!

[Code_Nerd]

I have written some Binary Tree classes in Java if your interested just let me know..
May give you an idea!!

(I know Java :( :( I had to take a class in it for 1 semester... )

PS: Sylvia pleae use code tags!!!!![code]Code goes here!!!!!![/code ]

[nspils]

Your instructor has provided most of the methods you need to rely on in coding your methods - you just need to discern how to use which ones ...

there is the max method ... which allows you to compare two values ...

You put values into TreeNodes and build BinarySearchTrees using the TreeNodes ... how would you add a TreeNode to the root - as a left child, or as a right child ...?

how do you get values to compare?
how do you "move" to the left or right child?
how do you "insert" as a left or right child?
how do you "delete" a node - what do you do with your left or right children?
think about how you can walk down a tree while at the same time remember where you've just been ...

[sylvia]

I've tried out the code for deleting the whole tree and for inserting a new item. I want help in checking what's wrong in this code? i hope the entire code is not wrong!!

       1 #include <iostream>
      2 #include "Tree.h"
      3 
      4 using namespace std;
      5 
      6 BinarySearchTree::~BinarySearchTree()
      7 {
      8     DeleteWholeTree(root_);
      9     if(root_)delete root_;
     10 }
     11 
     12 void BinarySearchTree::DeleteWholeTree(TreeNode* tnPtr)
     13 {
     14     // add your code here to delete the whole tree
     15     DeleteWholeTree(tnPtr->left_);
     16     DeleteWholeTree(tnPtr->right_);
     17     if(tnPtr)
     18     {
     19         if(tnPtr->item_)delete tnPtr->item_;
     20         delete tnPtr;
     21     }
     22 }
     23 
     24 
     25 TreeNode* BinarySearchTree::InsertTree(TreeNode* tnPtr,
     26                                         const TreeItemType& item)
     27 throw (TreeException)
     28 {
     29     // add your code here for insertion of item
     30     if(tnPtr == NULL)
     31         tnPtr = new TreeNode(item);
     32         else if(new TreeNode->item <= tnPtr->item)
     33             InsertTree(tnPtr->left_, new TreeNode);
     34             else if(new TreeNode->item > tnPtr->item)
     35                 InsertTree(tnPtr->right_, new TreeNode);
     36 }
     37 
     38 TreeNode* BinarySearchTree::DeleteTree(TreeNode* tnPtr,
     39                                     const TreeItemType& item)
     40 throw (TreeException)
     41 {
     42     // add your code here to delete item
     43 }
     44 
     45 int BinarySearchTree::SearchTree(const TreeNode* tnPtr,
     46                                     const TreeItemType item, int nLinks)
     47 {
     48     // add your code here to search an item
     49     // retun the number of links from root
     50 }
     51 
     52 void BinarySearchTree::Traversal(const TreeNode* tnPtr,int mode)
     53 {
     54     // add your code here to traversal (inorder)
     55 }
     56 
     57 TreeItemType BinarySearchTree::FindMin(const TreeNode* tnPtr)
     58 {
     59    // add your code here to find minimum item
     60    while
     61 }
     62 
     63 TreeItemType BinarySearchTree::FindMinimum()
     64 {
     65     // add your code here to call FindMin
     66 }
     67 
     68 bool BinarySearchTree::Insert(TreeItemType item)
     69 {
     70     // add your code here to call InsertTree
     71 }
     72 
     73 bool BinarySearchTree::Delete(TreeItemType item)
     74 {
     75     // add your code here to call DeteteTree
     76 }
     77 
     78 void BinarySearchTree::DeleteAll()
     79 {
     80     // add your code here to call DeleteWholeTree
     81 }
     82 
     83 int BinarySearchTree::Search(const TreeItemType item)
     84 {
     85     // add your code here to call SearchTree
     86 }
     87 
     88 void BinarySearchTree::InorderTraversal()
     89 {
     90 
     91     // add your code here to call Traversal
     92 }
     93

and how do i call this function in testTree.cpp? how do i include it there?
:confused:

[sylvia]

To Code_Nerd.. I do not know Java. So, I'm afraid I cannot understand a word in it. Thanks for your interest to help me. I hope you can help me with c++!??

[jonnin]

To delete the whole tree, do a left/right/root traversal (preorder I think) and delete each node when you hit the "root" phase.
Too much code for too simple a task for the entire tree project -- I am also confused

[nspils]

the delete is a "postorder" function - delete as you leave the subtree, can't leave stuff underneath (think of the memory leak ...).

The test cannot be "if you have a value" - just delete the node

{
     DeleteNode (left_)
     DeleteNode (right_);
     delete tnPtr;
}

your new functions are actually called by the public, "wrapper" functions - this is a common coding schema - don't put your work into public functions which make up the class's interface, code the "work" in private methods which are not exposed or reachable by those who don't have your code.

[sylvia]

1.how about this code? can somebody correct this code?
2.I'm not too sure about calling still? Can u explain with this example?
3.How do i find and print the number of links after finding the number i was searching for?
4.How do i delete a single node? and
5.What is the tree exception for insertion?

      
      1 #include <iostream>
      2 #include "Tree.h"
      3 
      4 using namespace std;
      5 
      6 BinarySearchTree::~BinarySearchTree()
      7 {
      8     DeleteWholeTree(root_);
      9 }
     10 
     11 void BinarySearchTree::DeleteWholeTree(TreeNode* tnPtr)
     12 {
     13     // add your code here to delete the whole tree
     14     DeleteNode (left_);
     15     DeleteNode (right_);
     16     delete tnPtr;
     17 }
     18 
     19 
     20 TreeNode* BinarySearchTree::InsertTree(TreeNode* tnPtr,
     21                                         const TreeItemType& item)
     22 
     23 throw (TreeException)
     24 {
     25     // add your code here for insertion of item
     26     if(tnPtr == NULL)
     27         tnPtr = new TreeNode(item);
     28         else if(new TreeNode->item <= tnPtr->item)
     29             InsertTree(tnPtr->left_, new TreeNode);
     30             else if(new TreeNode->item > tnPtr->item)
     31                 InsertTree(tnPtr->right_, new TreeNode);
     32 }
     33 
     34 TreeNode* BinarySearchTree::DeleteTree(TreeNode* tnPtr,
     35                                         const TreeItemType& item)
     36 {
     37     if(isEmpty())
     38       throw (TreeException)("TreeException: Empty tree");
     39       else
     40 {
     41     // add your code here to delete item
     42 }
     43 
     44 int BinarySearchTree::SearchTree(const TreeNode* tnPtr,
     45                                     const TreeItemType item, int nLinks)
     46 {
     47     // add your code here to search an item
     48     while(!isEmpty())
     49         if (TreeNode.item_ == item)
     50             return TreeNode;
     51        else if (TreeNode.item_ > item)
     52             TreeNode = TreeNode.left_;
     53             else
     54                 TreeNode = TreeNode.right_;
     55    return NULL;
     56 
     57     // retun the number of links from root
     58 }
     59 
     60 void BinarySearchTree::Traversal(const TreeNode* tnPtr,int mode)
     61 {
     62     // add your code here to traversal (inorder)
     63     if(tnPtr != NULL)
     64     {
     65         Traversal(tnPtr->left_);
     66         cout << tnPtr->item_ << endl;
     67         Traversal(tnPtr->right_);
     68     }
     69 }
     70 
     71 TreeItemType BinarySearchTree::FindMin(const TreeNode* tnPtr)
     72 {
     73    // add your code here to find minimum item
     74    while (TreeNode.left_ != NULL)
  75        TreeNode = TreeNode.left_;
     76        return TreeNode.item_;
     77 }
     78 
     79 TreeItemType BinarySearchTree::FindMinimum()
     80 {
     81     // add your code here to call FindMin
     82     FindMin(root_);
     83 }
     84 
     85 bool BinarySearchTree::Insert(TreeItemType item)
     86 {
     87     // add your code here to call InsertTree
     88     InsertTree(root_);
     89 }
     90 
     91 bool BinarySearchTree::Delete(TreeItemType item)
     92 {
     93     // add your code here to call DeteteTree
     94 }
     95 
     96 void BinarySearchTree::DeleteAll()
     97 {
     98     // add your code here to call DeleteWholeTree
     99     DeleteWholeTree(root_);
    100 }
    101 
    102 int BinarySearchTree::Search(const TreeItemType item)
    103 {
    104     // add your code here to call SearchTree
    105     SearchTree(root_);
    106 }
    107 
    108 void BinarySearchTree::InorderTraversal()
    109 {
    110     // add your code here to call Traversal
    111     Traversal(root_);
    112 }
    113

thxx

[sylvia]

Hi again! I am getting many errors when I compile this code. I am almost done with the coding part of the program. I have pasted the errors also. Can anybody help me with correcting the errors?

In my next post, I have included the code without the line numbers and in this one, I have pasted the same code with the line numbers. I thought that you would need it for finding the error. Correct me if I am wrong.

Tree.cpp with the line numbers.

   1 #include <iostream>
      2 #include "Tree.h"
      3 
      4 using namespace std;
      5 
      6 BinarySearchTree::~BinarySearchTree()
      7 {
      8     DeleteWholeTree(root_);
      9 }
     10 
     11 void BinarySearchTree::DeleteWholeTree(TreeNode* tnPtr)
     12 {
     13     // add your code here to delete the whole tree
     14     DeleteWholeTree(tnPtr->left_);
     15     DeleteWholeTree(tnPtr->right_);
     16     delete tnPtr;
     17     tnPtr=NULL;
     18 }
     19 
     20 
     21 TreeNode* BinarySearchTree::InsertTree(TreeNode* tnPtr,
     22                                         const TreeItemType& item)
     23 
     24 throw (TreeException)
     25 {
     26     // add your code here for insertion of item
     27     if(tnPtr == NULL){
     28         tnPtr = new TreeNode(item);
     29         return tnPtr;
     30     }
     31      if(item == tnPtr->item_)
     32         return tnPtr;
     33         if(item <= tnPtr->item_){
     34         tnPtr->left_ =  InsertTree(tnPtr->left_, item);
     35         return tnPtr;
     36     }
     37             else if(item > tnPtr->item){
     38                 tnPtr->right_ = InsertTree(tnPtr->right_, item);
     39               return tnPtr;
     40              }
     41 
     42 }
     43 
     44 TreeNode* BinarySearchTree::DeleteTree(TreeNode* tnPtr,
     45                                         const TreeItemType& item)
     46 {
     47     if(isEmpty())
     48       throw (TreeException)("TreeException: Empty tree");
     49       else
     50   {
     51     // add your code here to delete item
     52    if(tnPtr->left_ == NULL && tnPtr->right_ == NULL)
     53    {
     54        if(item == tnPtr->item_)
     55         return NULL;
     56    }
     57    else if(tnPtr->left_ == NULL && tnPtr->right_ != NULL)
     58           {
     59               if(item == tnPtr->item_)
     60                return tnPtr->right_;
     61                else
     62                    tnPtr->right_ = delete(item_,tnPtr->right_);
     63                    return tnPtr;
     64           }
     65                else if(tnPtr->right_ == NULL && tnPtr->left_ != NULL)
     66                   {
     67                       if(item == tnPtr->item_)
     68                        return tnPtr->left_;
     69                        else
     70                            tnPtr->left_ == delete(item_,tnPtr->left_);
     71                            return tnPtr;
     72                   }
     73                      else if(tnPtr->left_ != NULL && tnPtr->right_ != NULL)
     74                        {
     75                          if(item == tnPtr->item_)
     76                          tnPtr->item_ = FindMin(tnPtr->right_);
     77                          tnPtr->right_ = delete(tnPtr->item_, tnPtr->right_);
     78 
     79                            else if(item < tnPtr->item_)
     80                                  tnPtr->left_ = delete(item, tnPtr->left_);
     81 
     82                                 else
     83                                    tnPtr->right_ = delete(item, tnPtr->right_);
     84                                    return tnPtr;
     85                         }
     86   }
     87 }
     88 int BinarySearchTree::SearchTree(const TreeNode* tnPtr,
     89                                     const TreeItemType item, int nLinks)
     90 {
     91     // add your code here to search an item
     92     // return the number of links from root
     93 
     94   if(tnPtr == NULL)
     95        return NULL;
     96        if(item == tnPtr->item_)
     97            return nlinks;
     98            else if (item < tnPtr->item_)
     99                 search(item, tnPtr->left_, nlinks += 1);
    100                 return nlinks;
    101              else
    102                 search(item, tnPtr->right_, nlinks += 1);
    103                 return nlinks;
    104                 if(item != tnPtr->item_)
    105                    nlinks = -1;
    106                    return nlinks;
    107 
    108 }
    109 
    110 void BinarySearchTree::Traversal(const TreeNode* tnPtr,int mode)
    111 {
    112     // add your code here to traversal (inorder)
    113     if(tnPtr != NULL)
    114     {
    115         Traversal(tnPtr->left_);
    116         cout << tnPtr->item_ << endl;
    117         Traversal(tnPtr->right_);
    118     }
    119 }
    120 
    121 TreeItemType BinarySearchTree::FindMin(const TreeNode* tnPtr)
    122 {
    123    // add your code here to find minimum item
    124    while (tnPtr->left_ != NULL)
    125        tnPtr = tnPtr->left_;
    126        return tnPtr->item_;
    127 }
    128 
    129 TreeItemType BinarySearchTree::FindMinimum()
    130 {
    131     // add your code here to call FindMin
    132     FindMin(root_);
    133 }
    134 
    135 bool BinarySearchTree::Insert(TreeItemType item)
    136 {
    137     // add your code here to call InsertTree
    138     InsertTree(root_, item);
    139 }
    140 
    141 bool BinarySearchTree::Delete(TreeItemType item)
    142 {
    143     // add your code here to call DeteteTree
    144     DeleteTree(root_);
    145 }
    146 
    147 void BinarySearchTree::DeleteAll()
    148 {
    149     // add your code here to call DeleteWholeTree
    150     DeleteWholeTree(root_);
    151 }
    152 
    153 int BinarySearchTree::Search(const TreeItemType item)
    154 {
    155     // add your code here to call SearchTree
    156     SearchTree(root_);
    157 }
    158 
    159 void BinarySearchTree::InorderTraversal()
    160 {
    161     // add your code here to call Traversal
    162     Traversal(root_);
    163 }

My errors:
Tree.cpp: In member function `TreeNode* BinarySearchTree::InsertTree(TreeNode*,
const TreeItemType&)':
Tree.cpp:37: error: 'class TreeNode' has no member named 'item'
Tree.cpp: At global scope:
Tree.cpp:46: error: declaration of `TreeNode*
BinarySearchTree::DeleteTree(TreeNode*, const TreeItemType&)' throws
different exceptions
Tree.h:40: error: than previous declaration `TreeNode*
BinarySearchTree::DeleteTree(TreeNode*, const TreeItemType&) throw
(TreeException)'
Tree.cpp: In member function `TreeNode* BinarySearchTree::DeleteTree(TreeNode*,
const TreeItemType&)':
Tree.cpp:47: error: `isEmpty' undeclared (first use this function)
Tree.cpp:47: error: (Each undeclared identifier is reported only once for each
function it appears in.)
Tree.cpp:62: error: `item_' undeclared (first use this function)
Tree.cpp:77: warning: left-hand operand of comma expression has no effect
Tree.cpp:77: error: void value not ignored as it ought to be
Tree.cpp:79: error: parse error before `else'
Tree.cpp: In member function `int BinarySearchTree::SearchTree(const TreeNode*,
std::basic_string<char, std::char_traits<char>, std::allocator<char> >, int)
':
Tree.cpp:95: warning: return to non-pointer type `int' from NULL
Tree.cpp:95: warning: argument to non-pointer type `int' from NULL
Tree.cpp:97: error: `nlinks' undeclared (first use this function)
Tree.cpp:101: error: parse error before `else'
Tree.cpp: In member function `void BinarySearchTree::Traversal(const TreeNode*,
int)':
Tree.cpp:115: error: no matching function for call to `BinarySearchTree::
Traversal(TreeNode* const&)'
Tree.cpp:111: error: candidates are: void BinarySearchTree::Traversal(const
TreeNode*, int)
Tree.cpp:117: error: no matching function for call to `BinarySearchTree::
Traversal(TreeNode* const&)'
Tree.cpp:111: error: candidates are: void BinarySearchTree::Traversal(const
TreeNode*, int)
Tree.cpp: In member function `bool
BinarySearchTree::Delete(std::basic_string<char, std::char_traits<char>,
std::allocator<char> >)':
Tree.cpp:144: error: no matching function for call to `BinarySearchTree::
DeleteTree(TreeNode*&)'
Tree.cpp:46: error: candidates are: TreeNode*
BinarySearchTree::DeleteTree(TreeNode*, const TreeItemType&)
Tree.cpp: In member function `int
BinarySearchTree::Search(std::basic_string<char, std::char_traits<char>,
std::allocator<char> >)':
Tree.cpp:156: error: no matching function for call to `BinarySearchTree::
SearchTree(TreeNode*&)'
Tree.cpp:90: error: candidates are: int BinarySearchTree::SearchTree(const
TreeNode*, std::basic_string<char, std::char_traits<char>,
std::allocator<char> >, int)
Tree.cpp: In member function `void BinarySearchTree::InorderTraversal()':
Tree.cpp:162: error: no matching function for call to `BinarySearchTree::
Traversal(TreeNode*&)'
Tree.cpp:111: error: candidates are: void BinarySearchTree::Traversal(const
TreeNode*, int)
make: *** [Tree.o] Error 1
make: Target `all' not remade because of errors.

Thank You.