Binary tree not operational

[Alex Edwards]

I don't understand... I thought that it would be functional based on the logic, and I was fairly careful with my syntax but it's still not working.

Sometimes values will compare to as being "equal" even though they're not. I'm using troolean compareTo method (an int, returns -1, 0 or 1) and if two values are equal the value isn't set in the tree but it's testing two values incorrectly at some times...

Furthermore the pointer temp in the insert method doesn't seem to be reassigning itself properly.

Can someone please help me understand my error?

#include <cstdlib>
#include <iostream>

using namespace std;

/*

*/

struct Base
{
       
};

template<typename T>
class Tree
{
      private:
             struct Node
             {
                 friend class Tree;
                 
                 Node *left;
                 Node *right;
                 T value;
                 
                 Node(){left = 0; right = 0;};
                 T &getValue(){
                     return value;
                 };
                 void setValue(T &arg){value = arg;};
                 Node &getLeft(){return *left;};
                 Node &getRight(){return *right;};
                 bool setLeft(Node &l){
                      if(&l != 0){  
                         left = &l;
                         return true;
                      }
                      else return false;
                 };
                 bool setRight(Node &r){
                      if(&r != 0){
                         right = &r;
                         return true;
                      }
                      else return false;
                 };
                 int compareTo(Node &other){
                     if(other.getValue() == getValue())
                         return 0;
                     else if(other.getValue() < getValue())
                         return 1;
                     else return -1;
                 }
             };
             Node *root;
             void displayInOrder(Node &arg)
             {
                  if(&arg == 0)
                      return;
                  
                  displayInOrder(arg.getLeft());
                  std::cout << arg.getValue() << std::endl;
                  displayInOrder(arg.getRight());
                  
             }
             void displayPreOrder(Node &arg)
             {
                  if(&arg == 0)
                      return;
                      
                  std::cout << arg.getValue() << std::endl;
                  displayInOrder(arg.getLeft());
                  displayInOrder(arg.getRight());
                  
             }
             void displayPostOrder(Node &arg)
             {
                  if(&arg == 0)
                      return;
                  
                  displayInOrder(arg.getLeft());
                  displayInOrder(arg.getRight());
                  std::cout << arg.getValue() << std::endl;
                  
             }                       
             
              
      public:
             
             Tree(){root = 0;};
             
             bool insert(T &value)
             {
                Node *myNode = new Node;
                
                myNode->setValue(value);  
                  
                if(&value != 0)
                {  
                   if(root == 0)
                   {
                       root = myNode;
                       return true; 
                   }
                   else
                   {
                       cout << "Checking else statement..." << endl;
                       
                       Node *temp = root;
                       
                       while(&temp->getLeft() != 0 && &temp->getRight() != 0){
                                              
                           if(temp->compareTo(*myNode) == -1)
                           {
                               cout << "Shifting to the right of: " << temp->getValue() << endl;
                               temp = &temp->getRight();
                           }
                           else if(temp->compareTo(*myNode) == 1)
                           {
                               cout << "Shifting to the left of: " << temp->getValue() << endl; 
                               temp = &temp->getLeft();
                           }
                           else
                           {
                               cout << "No duplicates allowed! Aborting." << endl;
                               delete myNode;
                               return false;
                           }
                       }
                       if(temp->compareTo(*myNode) == -1){
                           
                           cout << "Setting next right node to: " << myNode->getValue() << endl;
                           temp->setRight(*myNode);
                           return true;
                       }
                       else if(temp->compareTo(*myNode) == 1){
                       
                           cout << "Setting next left node to: " << myNode->getValue() << endl;
                           temp->setLeft(*myNode);
                           return true;
                       }
                       else{
                           cout << "No duplicates allowed! "  << temp->getValue();
                           cout << " == "<< myNode->getValue() <<" -- Aborting." << endl;
                           delete myNode;
                           return false;
                       }           
                   }
                }
                else
                {
                    delete myNode;
                    return false;
                }      
             }
             
             void displayTree(char *condition)//this will be one complex method
             {
               //   if(std::strcmp(condition, "Inorder"))
              //    {
                     std::cout << "Displaying Tree...\n" << std::endl;                       
                     displayPreOrder(*root);               
              //    }
             }
             
};

int main(int argc, char *argv[])
{
    Tree<int> myTree;
    int a = 10, b = 2, c = 11, d = 7, e = 3, f = 19;
    myTree.insert(a);
    myTree.insert(b);
    myTree.insert(c);
    myTree.insert(d);
    myTree.insert(e);
    myTree.insert(f);
    myTree.insert(e);
    char *con = "Inorder";
  //  std::cout << std::strcmp("") << std::endl;
    myTree.displayTree(con);
    
    cin.get();
    return 0;
}

[Radical Edward]

Your use of pointers seems a little backwards, but the tree in your sample program is valid. Ed used a formatted display algorithm to see how it's structured. Here's something that is a bit more conventional in terms of how the pointers and values are handled:

#include <iostream>
#include <iomanip>

using namespace std;

template<typename T>
class Tree {
  struct Node {
    friend class Tree;

    Node *left;
    Node *right;
    T value;

    Node() { left = 0; right = 0; }
    T &getValue() { return value; }
    void setValue(T &arg) { value = arg; }
    Node *getLeft() { return left; }
    Node *getRight() { return right; }
    void setLeft(Node *l) { left = l; }
    void setRight(Node *r) { right = r; }

    int compareTo(Node *other) {
      return compareTo(other->getValue());
    }

    int compareTo(T other) {
      if (other == getValue())
        return 0;
      else if (other < getValue())
        return 1;
      else
        return -1;
    }
  };

  Node *root;
public:
  Tree() { root = 0; }

  bool insert(T value)
  { 
    if (root == 0) {
      root = new Node;
      root->setValue(value);
      return true; 
    }
    else {
      Node *temp = root;

      while (temp->getLeft() != 0 && temp->getRight() != 0) {
        if (temp->compareTo(value) == -1)
          temp = temp->getRight();
        else if (temp->compareTo(value) == 1)
          temp = temp->getLeft();
        else if (temp->compareTo(value) == 0)
          return false;
      }

      Node *myNode = new Node;

      myNode->setValue(value);

      if(temp->compareTo(value) == -1)
        temp->setRight(myNode);
      else if(temp->compareTo(value) == 1)
        temp->setLeft(myNode);  

      return true;
    }
  }

  void displayTree()
  {
    DisplayFormatted(root, 0);
  }

  void DisplayFormatted(Node *root, int level)
  {
    if (root == 0)
      std::cout << std::setw(level * 8) << "(null)\n";
    else {
      DisplayFormatted(root->right, level + 1);
      std::cout << std::setw(level * 8) << root->value << '\n';
      DisplayFormatted(root->left, level + 1);
    }
  }
};

int main(int argc, char *argv[])
{
  Tree<int> myTree;
  int a = 10, b = 2, c = 11, d = 7, e = 3, f = 19;

  myTree.insert(a);
  myTree.insert(b);
  myTree.insert(c);
  myTree.insert(d);
  myTree.insert(e);
  myTree.insert(f);
  myTree.insert(e);

  myTree.displayTree();

  return 0;
}

It's still your code, just tweaked a little bit. ;)

[Alex Edwards]

Thank you for the revision, but the main problem is that it seems the tree loses track of some of the values I insert.

Edit: Nevermind, I miscounted...

I better get some sleep.

Edit 2: Wait actually yeah 7 is not being input...

[Radical Edward]

Ahh, yes, you're right. The problem is in the insertion method where you insert if either branch of the temp node is null. The tree should look like this:

(null)
              19
                 (null)
      11
         (null)
10
                 (null)
               7
                         (null)
                       3
                         (null)
       2
         (null)

And it does until you try to insert 3. Because 2's left branch is null, and 3 is greater than 2, you overwrite 7. It might be a case of trying to be too clever. Instead of only using temp, you can use another temporary pointer that holds the previous node. That way you can walk temp off the tree and when temp is null, the other pointer holds the parent of where you want to insert:

bool insert(T value)
  { 
    if (root == 0) {
      root = new Node;
      root->setValue(value);
      return true; 
    }
    else {
      Node *temp = root;
      Node *last = 0;

      while (temp != 0) {
        last = temp;

        if (temp->compareTo(value) > 0)
          temp = temp->getLeft();
        else if (temp->compareTo(value) < 0)
          temp = temp->getRight();
        else
          return false;
      }

      Node *myNode = new Node;

      myNode->setValue(value);

      if(last->compareTo(value) == -1)
        last->setRight(myNode);
      else if(last->compareTo(value) == 1)
        last->setLeft(myNode);  

      return true;
    }
  }

That's easier to follow than the alternative, which is looking further down the tree in your tests:

bool insert(T value)
  { 
    if (root == 0) {
      root = new Node;
      root->setValue(value);
      return true; 
    }
    else {
      Node *temp = root;

      while (true) {
        if (temp->compareTo(value) > 0) {
          // Going left
          if (temp->getLeft() == 0)
            break;

          temp = temp->getLeft();
        }
        else if (temp->compareTo(value) < 0) {
          // Going right
          if (temp->getRight() == 0)
            break;

          temp = temp->getRight();
        }
        else
          return false;
      }

      Node *myNode = new Node;

      myNode->setValue(value);

      if(temp->compareTo(value) == -1)
        temp->setRight(myNode);
      else if(temp->compareTo(value) == 1)
        temp->setLeft(myNode);  

      return true;
    }
  }

[Alex Edwards]

I knew it was the condition in the while loop! I kept thinking "what if both leaf nodes aren't null" but couldn't wrap my head around the problem.

You rock!