Binary Search Tree.. can help with the pseudocode?


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Page 1 of 2 12 LastLast
Results 1 to 15 of 16

Thread: Binary Search Tree.. can help with the pseudocode?

Hybrid View

  1. #1
    Join Date
    Mar 2006
    Posts
    24

    Binary Search Tree.. can help with the pseudocode?

    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

  2. #2
    Join Date
    Mar 2006
    Posts
    24
    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

  3. #3
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    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 ...
    Last edited by nspils; 03-17-2006 at 02:00 PM.

  4. #4
    Join Date
    Mar 2006
    Posts
    24
    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

  5. #5
    Join Date
    Mar 2006
    Posts
    24
    . 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 };

  6. #6
    Join Date
    Mar 2006
    Posts
    24
    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 }

  7. #7
    Join Date
    Mar 2006
    Posts
    24
    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!!

  8. #8
    Join Date
    Aug 2005
    Location
    Melbourne...Australia
    Posts
    279
    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 ]

  9. #9
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    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 ...

  10. #10
    Join Date
    Mar 2006
    Posts
    24
    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!!

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

  11. #11
    Join Date
    Mar 2006
    Posts
    24
    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++!??

  12. #12
    Join Date
    Dec 2003
    Posts
    3,366
    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

  13. #13
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    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
    Code:
    {
         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.

  14. #14
    Join Date
    Mar 2006
    Posts
    24
    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?
    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
    thxx

  15. #15
    Join Date
    Mar 2006
    Posts
    24
    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.
    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 }
    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.

Similar Threads

  1. Replies: 1
    Last Post: 12-17-2005, 03:50 PM
  2. Replies: 4
    Last Post: 12-05-2005, 07:58 PM
  3. Binary Tree Help
    By TheJVM_1970 in forum Java
    Replies: 2
    Last Post: 12-05-2005, 01:23 AM
  4. Serialization in Binary Tree
    By diva_thilak in forum Java
    Replies: 0
    Last Post: 02-21-2005, 04:47 AM
  5. Binary Search Tree implementation
    By Liza in forum Java
    Replies: 0
    Last Post: 10-23-2001, 12:21 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center