Binary Search Tree..

triples1488 · #1 17-Mar-2006, 11:46

i have a problem with BST... i need to use pointers..

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'?)

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

triples1488 · #2 17-Mar-2006, 12:57

i'll give my question here just to tell you guys what i have to do so that somebody might explain better after reading my 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.
}

ok so now.. Tree.h is the following

CPP / C++ / C Code:

 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 };

Tree.cpp is the following

CPP / C++ / C Code:

 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 }

testTree.cpp file is the following

CPP / C++ / C Code:

     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!!

triples1488 · #3 18-Mar-2006, 11:03

can anybody tell me how do i delete an entire tree/node or insert an item in a node or do traversal(inorder) or search for an item or find the minimum item?? i do need the explanation.. the pseudocode also plz??

its quite confusing to implement the functions

triples1488 · #4 19-Mar-2006, 10:09

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!!

CPP / C++ / C Code:

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    
     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 }

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

triples1488 · #5 20-Mar-2006, 11:36

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?

CPP / C++ / C Code:

     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

i tried my level best to figure this out! can anybody help me?

#6 20-Mar-2006, 12:28

Quote:

Originally Posted by triples1488

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?

CPP / C++ / C Code:

     1 #include <iostream>
      2 #include "Tree.h"

i tried my level best to figure this out! can anybody help me?

Don't get your hopes up just yet, but I am reposting your code with some minor modifications and mostly just reformatting so that if anyone is interested in helping you out, they don't have to wade through all of the LINE NUMBERS in your code posts. In the future, don't post code with line numbers.

I'm starting a new policy of not helping anyone who can't figure out that "i" (by itself) is always capitalized and "ur" or "u" is not a word. You want to be lazy and not type it out, I'll be lazy and ignore "u" ...okay? ...especially when you want me to go through and delete all of the line numbers to even be able to implement your "stubbed-out" operations and (presumably) test the code.

:davis:

Tree.h

CPP / C++ / C Code:

#include <stdexcept>
#include <string>
using namespace std;

typedef string TreeItemType;

template <class T> T max (T a, T b)
{
    return a > b ? a : b;
};

class TreeException: public logic_error
{
public:
    TreeException(const string & message="")
    :logic_error(message.c_str())
    {
    }
};


class TreeNode
{

private:
    TreeItemType item_;
    TreeNode *left_;
    TreeNode *right_;
    friend class BinarySearchTree;

public:
    TreeNode(TreeItemType i)
    {
        item_ = i; left_ = right_ = NULL;
    };
};

class BinarySearchTree
{
private:
    TreeNode* root_;

    void DeleteWholeTree(TreeNode*);

    TreeNode* InsertTree(TreeNode*, const TreeItemType&)
    throw (TreeException);
    TreeNode* DeleteTree(TreeNode*, const TreeItemType&)
    throw (TreeException);
    int SearchTree(const TreeNode*, const TreeItemType,int);
    void Traversal(const TreeNode*, int);
    TreeItemType FindMin(const TreeNode*);

public:
    BinarySearchTree()
    {
        root_ = NULL;
    };
    ~BinarySearchTree();

    bool Insert(TreeItemType);
    bool Delete(TreeItemType);
    void DeleteAll();
    int Search(TreeItemType);
    void InorderTraversal();
    TreeItemType FindMinimum();
};

Tree.cpp

CPP / C++ / C Code:

#include <iostream>
#include "Tree.h"

using namespace std;

BinarySearchTree::~BinarySearchTree()
{
    DeleteWholeTree(root_);
}

void BinarySearchTree::DeleteWholeTree(TreeNode* tnPtr)
{
    // add your code here to delete the whole tree
}


TreeNode* BinarySearchTree::InsertTree(TreeNode* tnPtr,
                                       const TreeItemType& item)
throw (TreeException)
{
    // add your code here for insertion of item
}

TreeNode* BinarySearchTree::DeleteTree(TreeNode* tnPtr,
                                       const TreeItemType& item)
throw (TreeException)
{
    // add your code here to delete item
}

int BinarySearchTree::SearchTree(const TreeNode* tnPtr,
                                 const TreeItemType item, int nLinks)
{
    // add your code here to search an item
    // retun the number of links from root
}

void BinarySearchTree::Traversal(const TreeNode* tnPtr,int mode)
{
    // add your code here to traversal (inorder)
}

TreeItemType BinarySearchTree::FindMin(const TreeNode* tnPtr)
{
    // add your code here to find minimum item
}

TreeItemType BinarySearchTree::FindMinimum()
{
    // add your code here to call FindMin
}

bool BinarySearchTree::Insert(TreeItemType item)
{
    // add your code here to call InsertTree
}

bool BinarySearchTree::Delete(TreeItemType item)
{
    // add your code here to call DeteteTree
}

void BinarySearchTree::DeleteAll()
{
    // add your code here to call DeleteWholeTree
}

int BinarySearchTree::Search(const TreeItemType item)
{
    // add your code here to call SearchTree
}

void BinarySearchTree::InorderTraversal()
{

    // add your code here to call Traversal
}

testTree.cpp

CPP / C++ / C Code:

#include <iostream>
#include <cstdio>
#include "Tree.h"

using namespace std;

int main ()
{
    char s[100];
    bool quit = false;
    BinarySearchTree bst;
    int i,n;
    string item;

    while( !quit )
    {
        cin.getline (s, 100);

        switch( s[0] )
        {
            case 'i':
                // insertion
                sscanf (&s[2], "%d ", &n);
                for( i = 0; i < n; i++ )
                {
                    cin >> item;
                    if( !bst.Insert(item) )
                    {
                        cout << item << " not inserted" << endl;
                    }
                }
                break;

            case 'm':
                // print minimum
                item=bst.FindMinimum();
                if( item.empty() )
                {
                    cout << endl;
                }
                else
                {
                    cout << item << endl;
                }
                break;
            case 's':
                // search
                cin >> item;
                n = bst.Search(item);
                cout << item;
                if( n == -1 )
                {
                    cout << " not found" << endl;
                }
                else
                {
                    cout << " found - " << n << " links" << endl;
                }
                break;

            case 'd':
                // delete
                cin >> item;
                if( !bst.Delete(item) )
                {
                    cout << item << " not deleted" << endl;
                }
                break;

            case 'D':
                // delete the whole tree
                bst.DeleteAll();
                break;

            case 'p':
                // inorder print
                bst.InorderTraversal();
                break;

            case 'q':
                // quit
                quit = true;
                break;

        }

    }
    cout << "Program terminated. Bye!" << endl;
    return 0;
} //end main

triples1488 · #7 21-Mar-2006, 05:44

Sorry about the "i", "u" and "ur". I really din't mean to be lazy or din't just wait for the work from you. I was very excited when I finally got my code for the various implementations and at the same time, I was quite desperate about the errors when I thought about compilation. I will now promise you that I will never repeat my mistake again. I hope you will accept my apology.

I want to apologise for including the line numbers also. I will not do it again. Sorry about that. Sorry for making you delete the line numbers. I will not be of any annoyance in the future.

In this post, I have included the code without the line numbers as well as another copy of the same code with the line numbers. I thought that you would need it for finding the error. Correct me if I am wrong.

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 you help me with correcting the errors?

CPP / C++ / C Code:

#include <iostream>
#include "Tree.h"
using namespace std;
BinarySearchTree::~BinarySearchTree()
{
    DeleteWholeTree(root_);
}

void BinarySearchTree::DeleteWholeTree(TreeNode* tnPtr)
{
    // Deleting the whole tree
    DeleteWholeTree(tnPtr->left_);
    DeleteWholeTree(tnPtr->right_);
    delete tnPtr;
    tnPtr=NULL;
}

TreeNode* BinarySearchTree::InsertTree(TreeNode* tnPtr,
                                                  const TreeItemType& item)

throw (TreeException)
{
     // Inserting an item
     if(tnPtr == NULL){
     tnPtr = new TreeNode(item);
     return tnPtr;
  }
     if(item == tnPtr->item_)
     return tnPtr;
     if(item <= tnPtr->item_){
     tnPtr->left_ =  InsertTree(tnPtr->left_, item);
     return tnPtr;
  }
     else if(item > tnPtr->item){
     tnPtr->right_ = InsertTree(tnPtr->right_, item);
     return tnPtr;
  }

}
   
TreeNode* BinarySearchTree::DeleteTree(TreeNode* tnPtr,
                                                   const TreeItemType& item)
{
     if(isEmpty())
     throw (TreeException)("TreeException: Empty tree");
     else
            {
                // Deleting an item
               if(tnPtr->left_ == NULL && tnPtr->right_ == NULL)
               {
                  if(item == tnPtr->item_)
                  return NULL;
               }
              else if(tnPtr->left_ == NULL && tnPtr->right_ != NULL)
               {
                   if(item == tnPtr->item_)
                   return tnPtr->right_;
                   else
                         tnPtr->right_ = delete(item_,tnPtr->right_);
                         return tnPtr;
               }
                   else if(tnPtr->right_ == NULL && tnPtr->left_ != NULL)
                           {
                               if(item == tnPtr->item_)
                               return tnPtr->left_;
                               else
                                     tnPtr->left_ == delete(item_,tnPtr->left_);
                                     return tnPtr;
                           }
                  else if(tnPtr->left_ != NULL && tnPtr->right_ != NULL)
                           {
                               if(item == tnPtr->item_)
                               tnPtr->item_ = FindMin(tnPtr->right_);
                               tnPtr->right_ = delete(tnPtr->item_, tnPtr->right_);
     
                               else if(item < tnPtr->item_)
                               tnPtr->left_ = delete(item, tnPtr->left_);
      
                               else
                                     tnPtr->right_ = delete(item, tnPtr->right_);
                                     return tnPtr;
                           }
              }
     }
int BinarySearchTree::SearchTree(const TreeNode* tnPtr,
                                                  const TreeItemType item, int nLinks)
{
    // Searching an item
   // and also returning the number of links from root

   if(tnPtr == NULL)
      return NULL;
   if(item == tnPtr->item_)
      return nlinks;
   else if (item < tnPtr->item_)
         search(item, tnPtr->left_, nlinks += 1);
         return nlinks;
   else
         search(item, tnPtr->right_, nlinks += 1);
         return nlinks;
   if(item != tnPtr->item_)
        nlinks = -1;
        return nlinks;
  
}
 
void BinarySearchTree::Traversal(const TreeNode* tnPtr,int mode)
{
    // Traversal (inorder)
    if(tnPtr != NULL)
         {
               Traversal(tnPtr->left_);
                cout << tnPtr->item_ << endl;
               Traversal(tnPtr->right_);
          }
}
     
TreeItemType BinarySearchTree::FindMin(const TreeNode* tnPtr)
{
    // Finding the minimum item
    while (tnPtr->left_ != NULL)
    tnPtr = tnPtr->left_;
    return tnPtr->item_;
}
 
TreeItemType BinarySearchTree::FindMinimum()
{
    // Calling FindMin
    FindMin(root_);
}
 
bool BinarySearchTree::Insert(TreeItemType item)
{
    // Calling InsertTree
    InsertTree(root_, item);
}
 
bool BinarySearchTree::Delete(TreeItemType item)
{
    // Calling DeteteTree
    DeleteTree(root_);
}
 
void BinarySearchTree::DeleteAll()
{
    // Calling DeleteWholeTree
    DeleteWholeTree(root_);
}
 
int BinarySearchTree::Search(const TreeItemType item)
{
    // Calling SearchTree
    SearchTree(root_);
}
 
void BinarySearchTree::InorderTraversal()
{
    //  Calling Traversal
    Traversal(root_);
}

Tree.cpp with the line numbers now

CPP / C++ / C Code:


      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 }

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. I hope I do not annoy you anymore. If there is anything that I still need to correct in my etiquette, please do correct me.

#8 21-Mar-2006, 08:16

Quote:

Originally Posted by triples1488

Sorry about the "i", "u" and "ur". I really din't mean to be lazy or din't just wait for the work from you. I was very excited when I finally got my code for the various implementations and at the same time, I was quite desperate about the errors when I thought about compilation. I will now promise you that I will never repeat my mistake again. I hope you will accept my apology.

...okay, don't fall on your sword! We need and want everybody here

Quote:

Originally Posted by triples1488

I want to apologise for including the line numbers also. I will not do it again. Sorry about that. Sorry for making you delete the line numbers. I will not be of any annoyance in the future.

The line numbers do lend some aid in working with error messages, but they make it much more difficult to copy the code into a file on our remote systems and try it, fix it, debug it, etc.

Quote:

Originally Posted by triples1488

In this post, I have included the code without the line numbers as well as another copy of the same code with the line numbers. I thought that you would need it for finding the error. Correct me if I am wrong.

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 you help me with correcting the errors?

Let's take a look:

CPP / C++ / C Code:

                  else if(tnPtr->left_ != NULL && tnPtr->right_ != NULL)
                           {
                               if(item == tnPtr->item_)
                               tnPtr->item_ = FindMin(tnPtr->right_);
                               tnPtr->right_ = delete(tnPtr->item_, tnPtr->right_);
     
                               else if(item < tnPtr->item_)
                               tnPtr->left_ = delete(item, tnPtr->left_);
      
                               else
                                     tnPtr->right_ = delete(item, tnPtr->right_);
                                     return tnPtr;
                           }

..take a look at this code. Here is a nifty little C/C++ coding "secret" that never seems to reach people. ALWAYS enclose conditional statements in braces. In other words NEVER use the "single line" style of coding conditional statements:

CPP / C++ / C Code:

if( something )    // BAD!
    doSomething();

if( something )  // CORRECT
{
    doSomething();
}

This is a very good habit to get into that will easily prevent these kinds of problems...AND it will make it very clear what "blocking/scoping order" you meant when you wrote the code. The only way that I can "fix" your code is to spend a lot of time looking at it and/or debugging it to figure out why there is a problem on line 76. What you've done is:

CPP / C++ / C Code:

if( something )
doSomething();
doSomethingElse();
else if( somethingElse )
doAnotherThing();
else
doYetAnotherThing();
return;

...there isn't even indentation to give us an idea of what you really meant from just a visual observation of the code. If your coding "style" makes it harder to tell from a quick glance what the code is doing, it should probably be improved.

...here is an equivalent to your problem:

CPP / C++ / C Code:


#include <stdio.h>

int main( void )
{
    int i = 0;

    if( 1 )
    i = 100;
    i = -100;
    else if( i )
    i = 47;
    else
    i = 15;
    return i;
}

...and the compiler messages:

Code:

gcc -g -Wall -o ifelse ifelse.c

ifelse.c: In function `main':
ifelse.c:10: error: syntax error before "else"

Quote:

Originally Posted by triples1488

Thank You. I hope I do not annoy you anymore. If there is anything that I still need to correct in my etiquette, please do correct me.

We just want to get you "fixed up" and "coding forward." There are a couple of axioms that really apply well to C and C++.

--Use braces everywhere
--Use parentheses everywhere else

IMO, far too many books (including K&R) over use the "single line" conditional style. Far too many coders in the world happily use single line conditionals EVERYWHERE they possibly can. It makes the code much harder to read when complex and even simple code means stopping to carefully read through it just to figure out the scoping order. Ideally, code should be so easy to read and understand that even a non-programmer can quickly and easily figure out what it does. Obviously, that isn't possible in a lot of cases where the syntax is "difficult," such as in templates and longer scope resolution operator member notations and pointer to pointer...to pointer dereferencing, etc. but we CAN choose to make it easier to read and understand in some rather simple ways, and adding braces is an easy one. Once you start doing it, you'll be glad you did because silly mistakes like those above won't cause totally cryptic compiler messages pointing at something entirely different due to parsing failures somewhere else.

Using the "multiple line" style conditional (even for single lines) is a good thing. For one, it makes it very clear and obvious to everyone what scope everything is supposed to be at, AND it makes it very easy to go back and add a line, inside of the "block" without having to add braces to convert a single line style conditional into a multiline style conditional. Consider the following:

CPP / C++ / C Code:

if( something )
z = (verycomplex=(x/y^2-3*a*y*y+72))?99:47;

This is a "nothing" piece of code to do nothing more than illustrate the idea of a single line conditional being used and someone else (you and other readers here) coming along to read it and somehow make sense of it. Okay, even if we spend the time and figure out how, in this narrow scope all of these variables interact so that we can tell what the value of z is at the end of the statement, we could just as easily have added:

CPP / C++ / C Code:

if( something )
{
    z = (verycomplex=(x/y^2-3*a*y*y+72))?99:47;
    printf( "z = %d\n", z );
}

...had it already been a multiline conditional. Since printf/cout seems to be the beginning programmer's best friend, it seems to suggest that more would use multiline conditionals, but they don't. How many times have you ever gone back to add braces so that you can add a printf inside of some conditional?

When you multiply the complexity by a few factors through adding multiple else if statements, braces should be considered a requirement and not optional even if the language lets you get away with it.

I don't propose that fixing this one problem will fix all of the errors you've shown here, but sometimes in order to really fix something we have to look more closely at the root of some of the ways that problems like this crop up. Coding "style" issues can create a lot of problems or they can remove them by "design."

:davis:

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Counting leaves in a Binary Tree	SnackMan78	C++ Forum	5	06-Oct-2005 15:53
Linear Search	eccoflame	C Programming Language	3	19-Apr-2005 09:36
printing binary search tree	nkhambal	C Programming Language	2	26-Mar-2005 04:01
Please help! Dynamic binary tree problem	robsmith	C Programming Language	3	15-Mar-2005 22:20
Search Engine Positioning 101 and 201 "How To" Tips...	000	Search Engine Optimization Forum	0	29-May-2003 11:34

Binary Search Tree..

Re: Binary Search Tree..

Re: Binary Search Tree..

Re: Binary Search Tree..

Re: Binary Search Tree..

Re: Binary Search Tree..

Re: Binary Search Tree..

Re: Binary Search Tree..