Binary Tree

[monkeybutt]

OK, I'm trying to create a binary tree. I'm sure I have a bunch of unhappiness going on in my program but I'm mainly concerned that the input is not going into the node. I don't understand why. It compiles but fails when run. Please help.




#include <iostream>
using namespace std;

struct node
{
node* leftCh;
int data;
node* rightCh;
};

struct node* root = NULL;

void inorderPrint(node*);


int main()
{
//node* root = NULL;
int num;
int data;

cout << "Enter a sequence of different integers, followed by -9999" << endl;
cin >> num;
data = num;
root->data = data;
root->leftCh = NULL;
root->rightCh = NULL;
cin >> num;
while(num != -9999)
{
if(num < (root->data))
{
node* left;
left->data = num;
}
else if(num > (root->data))
{
node* right;
right->data = num;
}
else
{
cout << "Error. You entered a repeat number." << endl;
}
cin >> num;
}

inorderPrint(root);

return 0;
}


void inorderPrint(node *root)
{
if (root->data != NULL)
{
inorderPrint(root->leftCh); // Print items in left subtree.
cout << root->data << " "; // Print the root item.
inorderPrint(root->rightCh); // Print items in right subtree.
}
}

[histrungalot]

You need to allocate memory for each of the nodes that you are trying to assign values to. Like in the first part of your code:

// ....
struct node* root = NULL;
void inorderPrint(node*);
int main()
{
// ....
   cout << "Enter a sequence of different integers, followed by -9999" << endl;
   cin >> num;
   data = num;
   //-----------------------------------------------------------------------------
   // Right here you are using the value of root, but it has the value
   // of NULL which is going to cause a segfault.
   //
   root->data = data;
   //^^^^^ BAD ^^^^^^
   root->leftCh = NULL;
   root->rightCh = NULL;
   cin >> num;

You need to allocate memory to root before you can use it like:

   // Allocating memory
   root = new node;

You have to allocate memory each time you try to add a node. You also need to traverse the tree each time you get a new value to see were it should go. Then new node a new node to store the data and assign that pointer to the node to the correct pointer (leftCh or rightCh)
You should put a try/catch but get the other stuff working first.

[Albatross]

Oh, on a very important note...
You have to make sure you delete any memory you allocate with new. If you don't, you're probably going to wind up with a memory leak. >:|

-Albatross

[monkeybutt]

It debugs and the input goes to the data of root but my recursion for the left and right nodes isn't working and I can't understand why. If I initialize root->leftCh, I can store the data into that node but it doesn't work recursively. Any thoughts?

#include "stdafx.h"
#include <iostream>
using namespace std;

struct node
{
node* leftCh;
int data;
node* rightCh;
};

struct node* root = NULL;

void inorderPrint(node*);


int main()
{
root = new node;
int num;
int data;

cout << "Enter a sequence of different integers, followed by -9999" << endl;
cin >> num;
data = num;
root->data = num;
root->leftCh = NULL;
root->rightCh = NULL;
cin >> num;
while(num != -9999)
{
if(num < data)
{
struct node* leftCh = NULL;
leftCh = new node;
data = num;
leftCh->data = num;
leftCh->leftCh = NULL;
leftCh->rightCh = NULL;
}
else if(num > data)
{
struct node* rightCh = NULL;
rightCh = new node;
data = num;
rightCh->data = num;
rightCh->leftCh = NULL;
rightCh->rightCh = NULL;
}
else
{
cout << "Error. You entered a repeat number." << endl;
}
cin >> num;
}

inorderPrint(root);

return 0;
}


void inorderPrint(node *root)
{
if(root->data != NULL)
{
inorderPrint(root->leftCh); // Print items in left subtree.
delete root->leftCh;
cout << root->data << " "; // Print the root item.
inorderPrint(root->rightCh); // Print items in right subtree.
delete root->rightCh;
root->data = NULL;
}
}

[histrungalot]

You need to walk down the tree to find the right spot to put it.
In the example below the code uses recursion to do the "walking" down the tree.
http://en.m.wikipedia.org/wiki/Binary_search_tree

 /* Inserts the node pointed to by "newNode" into the subtree rooted at "treeNode" */
 void InsertNode(Node* &treeNode, Node *newNode)
 {
     if (treeNode == NULL)
       treeNode = newNode;
     else if (newNode->key < treeNode->key)
       InsertNode(treeNode->left, newNode);
     else
       InsertNode(treeNode->right, newNode);
 }

You are now allocating memory to the pointer but you need to attach that point to the tree.

[clanmjc]

In your code here

if(num < data)
{
   struct node* leftCh = NULL; //You declare a local pointer in the scope of the if() block
   leftCh = new node;          //You allocate memory
   data = num;                 //You don't need this data variable, same with your if condition (more on this later)
   leftCh->data = num;         //You set your local pointers data to num
   leftCh->leftCh = NULL;      //...
   leftCh->rightCh = NULL;     //...
} 
//When you leave this block, you not only have a memory leak, leftCh no longer exists.  
//Just because you name your local variable the same name 
//as the member of your node structure does not magically create some kind of relationship. 

If you want to use the local pointer that is fine but before you leave that block make sure to assign your roots pointer e.g.

//Using the code from above...
//....
root->leftCh = leftCh; //Now your 'real' tree points to the memory that you allocated for this temp 

Before you leave main you will need to traverse your tree freeing the memory for each node you allocated.

[monkeybutt]

To avoid confusion, should I change the leftCh in the if statement to something else, like left? I changed the if statement around so that data keeps changing for the recursion but it still only goes through one recursion.

This is what I have,

if(num < data)
{
node* leftCh = new node;
root->leftCh = new node;
leftCh->data = num;
leftCh->leftCh = NULL;
leftCh->rightCh = NULL;
data = leftCh->data;
root->leftCh = leftCh;
}
would it even make a difference if I changed "root->leftCh = leftCh" to "root->leftCh-> data = leftCh->data"? Or should I add that to make it contain the data as well as point to it? Thank you for being patient with me.

[monkeybutt]

I added "root->leftCh->data = leftCh->data" but I don't think it makes a difference. When I am resetting the root pointer in the if statement, I think it is just writing over itself, recursively. It limits how far the tree can go.

[histrungalot]

Using the example from wiki, think about this

      if(num < data)
      {
         struct node* leftCh = new node;
         // Not used in here
         //data = num;
         leftCh->data = num;
         leftCh->left = NULL;
         leftCh->right = NULL;
         // Call a function to recursively add the node
         // where is should be
      }
      else if(num > data)
      {
         struct node* rightCh = new node;
         // Not used 
         //data = num;
         rightCh->data = num;
         rightCh->left = NULL;
         rightCh->right = NULL;
         // Call a function to recursively add the node
         // where is should be
      }
      else
      {
         cout << "Error. You entered a repeat number." << endl;
      }
      cin >> num;

Then in inorderPrint you need to walk down the tree.

void inorderPrint(node *root)
{
   // Check to see if the left is there
   // If there call inorderPrint with the left pointer
   //   remove memory
   //   print current data value
   //   call inorderPrint with the right pointer
   //   remove memory
   // Else if right is there
   //   call inorderPrint with the right pointer
   //   remove memory
   //   print current data value
   // Else print out current node data
}

[monkeybutt]

I got it. Thanks!