Programming Forums > Application Development > C++

nnxion · Apr 2nd, 2006, 10:02 AM

When The Dark says you should do:

void insertSpot(int option)
{
	heapNode *newNode = new heapNode(option);
	// Increment counter first as the algorithm needs it
	counter++;

	if (root == NULL)
	{
		root = newNode;
	}
	else
	{

...........................

      int temp = counter;
      for(i = 0; i < 32; i++)
      {
          arrayValue = temp % 2;
          temp = temp / 2;
          ar = arrayValue;
      }

Then you should not do:

(Toggle Plain Text)

void insertSpot(int option)
{
	heapNode *newNode = new heapNode(option);
	int arrayValue;
	bool isOne = false;
	int ar[32];
	int i = 31;
	int temp = counter;
	counter++;

Just following what The Dark says gives me something that almost compiles. You still need to change some things. Please study carefully and do not just try to compile and tell us "my compiler gives errors". Read post #49 to see what to do with parent.

(Toggle Plain Text)

#include <iostream>
using namespace std;

class heapNode
{
private:
	int value;

public:
	heapNode *left;
	heapNode *right;

	heapNode(int newValue)
	{
		value = newValue;
		left = NULL;
		right = NULL;
	}

	int getValue()
	{
		return value;
	}

	heapNode* getRight()
	{
		return right;
	}

	heapNode* getLeft()
	{
		return left;
	}

	void setValue(int newValue)
	{
		value = newValue;
	}

	void setRight(heapNode *newRight)
	{
		right = newRight;
	}

	void setLeft(heapNode *newLeft)
	{
		left = newLeft;
	}
};

class heap
{
	private:
	heapNode *root;
	int counter;

public:
	heap()
	{
		counter = 0;
		root = NULL;
	}

	void realInsert(int ar[], int pos, heapNode *parent, heapNode *newNode)
	{
		if(newNode->left == NULL)
		{
			realInsert(ar, pos-1, parent, newNode);
			if(newNode->left->getValue() < newNode->getValue())
			{
				newNode->setValue(newNode->left->getValue());
				counter++;
			}
		}

		else if(newNode->right == NULL)
		{
			realInsert(ar, pos-1, parent, newNode);
			if(newNode->right->getValue() < newNode->getValue())
			{
				newNode->setValue(newNode->right->getValue());
				counter++;
			}
		}
	}

	void insertSpot(int option)
	{
		heapNode *newNode = new heapNode(option);
		// Increment counter first as the algorithm needs it
		counter++;

		if (root == NULL)
		{
			root = newNode;
		}
		else
		{
			int arrayValue;
			bool isOne = false;
			int ar[32];
			int i = 31;

			int temp = counter;

			for(i = 0; i < 32; i++)
			{
				arrayValue = temp % 2;
				temp = temp / 2;
				ar[i] = arrayValue; // changed from ar to ar[i]
			}

			for(int i = 0; i < 32; i++)
				cout << ar[i] << " ";
			cout << endl;

			while(i >= 0)
			{
				if(ar[i] == 1)
					isOne = true;

				if(isOne = true)
					break;
				i--;
			}
			realInsert(ar, i, parent, newNode); // still needs fixing
		}
	}

	void print()
	{
		printNode(root, 0);
	}

	void printNode(heapNode *node, int level)
	{
		if(node != NULL)
		{
			cout << "Level: " << " Val: " << node->getValue() << "\n";
			printNode(node->getLeft(), level + 1);
			printNode(node->getRight(), level + 1);
		}
	}

	heapNode* getRoot()
	{
		return root;
	}
};

int main()
{
	heap *myHeap;

	myHeap = new heap();

	int option = -1;
	while (option != 0)
	{
		cout << "Please enter a number: ";
		cin >> option;
		myHeap->insertSpot(option);
	}

	myHeap->print();
	return 0;
}

#include <iostream>
using namespace std;

class heapNode
{
private:
	int value;

public:
	heapNode *left;
	heapNode *right;

	heapNode(int newValue)
	{
		value = newValue;
		left = NULL;
		right = NULL;
	}

	int getValue()
	{
		return value;
	}

	heapNode* getRight()
	{
		return right;
	}

	heapNode* getLeft()
	{
		return left;
	}

	void setValue(int newValue)
	{
		value = newValue;
	}

	void setRight(heapNode *newRight)
	{
		right = newRight;
	}

	void setLeft(heapNode *newLeft)
	{
		left = newLeft;
	}
};

class heap
{
	private:
	heapNode *root;
	int counter;

public:
	heap()
	{
		counter = 0;
		root = NULL;
	}

	void realInsert(int ar[], int pos, heapNode *parent, heapNode *newNode)
	{
		if(newNode->left == NULL)
		{
			realInsert(ar, pos-1, parent, newNode);
			if(newNode->left->getValue() < newNode->getValue())
			{
				newNode->setValue(newNode->left->getValue());
				counter++;
			}
		}

		else if(newNode->right == NULL)
		{
			realInsert(ar, pos-1, parent, newNode);
			if(newNode->right->getValue() < newNode->getValue())
			{
				newNode->setValue(newNode->right->getValue());
				counter++;
			}
		}
	}

	void insertSpot(int option)
	{
		heapNode *newNode = new heapNode(option);
		// Increment counter first as the algorithm needs it
		counter++;

		if (root == NULL)
		{
			root = newNode;
		}
		else
		{
			int arrayValue;
			bool isOne = false;
			int ar[32];
			int i = 31;

			int temp = counter;

			for(i = 0; i < 32; i++)
			{
				arrayValue = temp % 2;
				temp = temp / 2;
				ar[i] = arrayValue; // changed from ar to ar[i]
			}

			for(int i = 0; i < 32; i++)
				cout << ar[i] << " ";
			cout << endl;

			while(i >= 0)
			{
				if(ar[i] == 1)
					isOne = true;

				if(isOne = true)
					break;
				i--;
			}
			realInsert(ar, i, parent, newNode); // still needs fixing
		}
	}

	void print()
	{
		printNode(root, 0);
	}

	void printNode(heapNode *node, int level)
	{
		if(node != NULL)
		{
			cout << "Level: " << " Val: " << node->getValue() << "\n";
			printNode(node->getLeft(), level + 1);
			printNode(node->getRight(), level + 1);
		}
	}

	heapNode* getRoot()
	{
		return root;
	}
};

int main()
{
	heap *myHeap;

	myHeap = new heap();

	int option = -1;
	while (option != 0)
	{
		cout << "Please enter a number: ";
		cin >> option;
		myHeap->insertSpot(option);
	}

	myHeap->print();
	return 0;
}

cwl157 · Apr 2nd, 2006, 3:40 PM

ok so i set root to be parent when i call the realInsert method in insertSpot and i get this error

Quote:

program5.cpp: In member function ?void heap::insertSpot(int)?:
program5.cpp:137: error: invalid conversion from ?int? to ?int*?
program5.cpp:137: error: initializing argument 1 of ?void heap::realInsert(int*, int, heapNode*, heapNode*)?

Quote:

parent is the name of the parameter, you should pass in root in the first call to realInsert, as root is the top level parent of the heap.

As to what to pass as parent and newNode. When you first call the realInsert function the parent would be root, from then on when you recurse down, you would use parent->getLeft() or parent->getRight().
Pass in the newNode that was created at the top of insertSpot as the newNode parameter.

Does this mean realInsert should look like this?

(Toggle Plain Text)

void realInsert(int ar[], int pos, heapNode *parent, heapNode *newNode)
  {
    if(newNode->left == NULL)
    {
      realInsert(ar, pos-1, parent->getLeft(), newNode);
      if(newNode->left->getValue() < newNode->getValue())
      {
        newNode->setValue(newNode->left->getValue());
        counter++;
      }  
    }
    else if(newNode->right == NULL)
    {
      realInsert(ar, pos-1, parent->getRight(), newNode);
      if(newNode->right->getValue() < newNode->getValue())
      {
        newNode->setValue(newNode->right->getValue());
        counter++;
      }
    }
  }

Here is the whole program

(Toggle Plain Text)

#include <iostream>
using namespace std;

class heapNode
{
  private:
  int value;

  public:
  heapNode *left;
  heapNode *right;
  //constructor
  heapNode(int newValue)
  {
     value = newValue;
     left = NULL; 
     right = NULL;
  }
 
  //get value
  int getValue()
  {
    return value;
  }
  
  //get right
  heapNode* getRight()
  {
    return right;
  }

  //get left
  heapNode* getLeft()
  {
    return left;
  }

  //set value
  void setValue(int newValue)
  {
    value = newValue;
  }

  // set right
  void setRight(heapNode *newRight)
  {
    right = newRight;
  }

  // set left
  void setLeft(heapNode *newLeft)
  {
    left = newLeft;
  }
  
}; // end of heapNode class

class heap
{
  private:
  heapNode *root;
  int counter;

public:
  //constructor
  heap()
  {
    counter = 0;
    root = NULL;
  }

  void realInsert(int ar[], int pos, heapNode *parent, heapNode *newNode)
  {
    if(newNode->left == NULL)
    {
      realInsert(ar, pos-1, parent, newNode);
      if(newNode->left->getValue() < newNode->getValue())
      {
        newNode->setValue(newNode->left->getValue());
        counter++;
      }  
    }
    else if(newNode->right == NULL)
    {
      realInsert(ar, pos-1, parent, newNode);
      if(newNode->right->getValue() < newNode->getValue())
      {
        newNode->setValue(newNode->right->getValue());
        counter++;
      }
    }
  }

  // find the spot to put new value
  void insertSpot(int option)
  {
    heapNode *newNode = new heapNode(option);
    int arrayValue;
    bool isOne = false;
    int ar[32];
    int i = 31;
    counter++;
    if(root == NULL)
    {
      root = newNode;
    }

    else
    {
      int arrayValue;
      bool isOne = false;
      int ar[32];
      int i = 31;
      int temp = counter;
      for(int i = 0; i < 32; i++)
      {
          arrayValue = temp % 2;
          option = temp / 2;
          ar[i] = arrayValue;
      }
 
      for(int i = 0; i < 32; i++)
        cout << ar[i] << " ";
      cout << endl;

      while(i >= 0)
      {
        if(ar[i] == 1)
          isOne = true;
        if(isOne = true)
          break;
        i--;
      }
      realInsert(*ar, i, root, newNode);
    }
  }
   
  //print
  void print()
  {
    printNode(root, 0);
  }

  void printNode(heapNode *node, int level)
  {
    if(node != NULL)
    {
      cout << "Level: " << " Val: " << node->getValue() << "\n";
      printNode(node->getLeft(), level + 1);
      printNode(node->getRight(), level + 1);
    }
  }

  // get root
  heapNode* getRoot()
  {
    return root;
  }

/*
    int delete(rootValue)
    {
        heapNode *tempNode = new heapNode(value, *left, *right)
        go down the heap to the last one
        make it root
        last nodeValue = null
	while(not at the bottom level of tree)
	{
	  if(newRoot < *left)
	    break;
          elseif(newRoot > *left)
	    swap with left;
        }

        return tempNode;         
     }
*/

  }; // end of heap class

int main()
{
  heap *myHeap;

  myHeap = new heap();


  int option=9;
  while (option != 0) {
    cout << "Please enter a number: ";
    cin >> option;
    myHeap->insertSpot(option);
    }

  myHeap->print();
  return 0;
}

#include <iostream>
using namespace std;

class heapNode
{
  private:
  int value;

  public:
  heapNode *left;
  heapNode *right;
  //constructor
  heapNode(int newValue)
  {
     value = newValue;
     left = NULL; 
     right = NULL;
  }
 
  //get value
  int getValue()
  {
    return value;
  }
  
  //get right
  heapNode* getRight()
  {
    return right;
  }

  //get left
  heapNode* getLeft()
  {
    return left;
  }

  //set value
  void setValue(int newValue)
  {
    value = newValue;
  }

  // set right
  void setRight(heapNode *newRight)
  {
    right = newRight;
  }

  // set left
  void setLeft(heapNode *newLeft)
  {
    left = newLeft;
  }
  
}; // end of heapNode class

class heap
{
  private:
  heapNode *root;
  int counter;

public:
  //constructor
  heap()
  {
    counter = 0;
    root = NULL;
  }

  void realInsert(int ar[], int pos, heapNode *parent, heapNode *newNode)
  {
    if(newNode->left == NULL)
    {
      realInsert(ar, pos-1, parent, newNode);
      if(newNode->left->getValue() < newNode->getValue())
      {
        newNode->setValue(newNode->left->getValue());
        counter++;
      }  
    }
    else if(newNode->right == NULL)
    {
      realInsert(ar, pos-1, parent, newNode);
      if(newNode->right->getValue() < newNode->getValue())
      {
        newNode->setValue(newNode->right->getValue());
        counter++;
      }
    }
  }

  // find the spot to put new value
  void insertSpot(int option)
  {
    heapNode *newNode = new heapNode(option);
    int arrayValue;
    bool isOne = false;
    int ar[32];
    int i = 31;
    counter++;
    if(root == NULL)
    {
      root = newNode;
    }

    else
    {
      int arrayValue;
      bool isOne = false;
      int ar[32];
      int i = 31;
      int temp = counter;
      for(int i = 0; i < 32; i++)
      {
          arrayValue = temp % 2;
          option = temp / 2;
          ar[i] = arrayValue;
      }
 
      for(int i = 0; i < 32; i++)
        cout << ar[i] << " ";
      cout << endl;

      while(i >= 0)
      {
        if(ar[i] == 1)
          isOne = true;
        if(isOne = true)
          break;
        i--;
      }
      realInsert(*ar, i, root, newNode);
    }
  }
   
  //print
  void print()
  {
    printNode(root, 0);
  }

  void printNode(heapNode *node, int level)
  {
    if(node != NULL)
    {
      cout << "Level: " << " Val: " << node->getValue() << "\n";
      printNode(node->getLeft(), level + 1);
      printNode(node->getRight(), level + 1);
    }
  }

  // get root
  heapNode* getRoot()
  {
    return root;
  }

/*
    int delete(rootValue)
    {
        heapNode *tempNode = new heapNode(value, *left, *right)
        go down the heap to the last one
        make it root
        last nodeValue = null
	while(not at the bottom level of tree)
	{
	  if(newRoot < *left)
	    break;
          elseif(newRoot > *left)
	    swap with left;
        }

        return tempNode;         
     }
*/

  }; // end of heap class

int main()
{
  heap *myHeap;

  myHeap = new heap();


  int option=9;
  while (option != 0) {
    cout << "Please enter a number: ";
    cin >> option;
    myHeap->insertSpot(option);
    }

  myHeap->print();
  return 0;
}

nnxion · Apr 2nd, 2006, 4:21 PM

What do you not get from:

Quote:

parent is the name of the parameter, you should pass in root in the first call to realInsert, as root is the top level parent of the heap.

As to what to pass as parent and newNode. When you first call the realInsert function the parent would be root, from then on when you recurse down, you would use parent->getLeft() or parent->getRight().
Pass in the newNode that was created at the top of insertSpot as the newNode parameter.

That means your call.

(Toggle Plain Text)

realInsert(*ar, i, root, newNode);

While I gave already gave you:

(Toggle Plain Text)

realInsert(ar, i, parent, newNode); // still needs fixing

And did you even check to see what you were copying?

(Toggle Plain Text)

void insertSpot(int option)
{
	heapNode *newNode = new heapNode(option);
	int arrayValue;
	bool isOne = false;
	int ar[32];
	int i = 31;
	counter++;
	if(root == NULL)
	{
	  root = newNode;
	}

	else
	{
		int arrayValue;
		bool isOne = false;
		int ar[32];
		int i = 31;
		int temp = counter;

And lastly, you should remove the comments that say: "//get value", when the function is called "getvalue". Only comment when it makes things more clear.

Just a quick question: how much programming experience do you have?

The Dark · Apr 2nd, 2006, 8:32 PM

Also, in your realInsert function, you need to think about what you are trying to do. You are passing the ar and pos parameters for a reason, but your current code is not using them at all.
- You need to be using the value of ar[pos] to decide whether to move left or right.
- You also need a special case for pos == 0 in realInsert, because that mean you have hit the bottom of the heap and actually want to do the insert.
- You never want to check the right or left values of newNode, because you have just allocated newNode so its right or left values will always be NULL.

in your insertSpot, you need to fix this line

(Toggle Plain Text)

        if(isOne = true)

That is an assignment, not a test, so it will always evaluate to true.

If you are under unix and are using gcc (or g++), have a look at gdb. It will let you single step through the code so you can see what the various variable values are.

cwl157 · Apr 4th, 2006, 4:39 PM

ok now i think it will make a lot more sense. I still have 1 problem with the insert and 1 problem with the print. For the insert i need it to swap the values if the new node entered is less than the parents node. For the print method i need it to print spaces to show each level of the tree. I have an attempt at both of these problems but i do not think either of them work right. I did the swapping problem first but thought it would be easier to see if that was working if it printed them in the proper layers so then i tried to do the layers but now neither work right. Here is the code:

(Toggle Plain Text)

#include <iostream>
using namespace std;

class heapNode
{
  private:
  int value;

  public:
  heapNode *left;
  heapNode *right;
  //constructor
  heapNode(int newValue)
  {
     value = newValue;
     left = NULL; 
     right = NULL;
  }
 
  //get value
  int getValue()
  {
    return value;
  }
  
  //get right
  heapNode* getRight()
  {
    return right;
  }

  //get left
  heapNode* getLeft()
  {
    return left;
  }

  //set value
  void setValue(int newValue)
  {
    value = newValue;
  }

  // set right
  void setRight(heapNode *newRight)
  {
    right = newRight;
  }

  // set left
  void setLeft(heapNode *newLeft)
  {
    left = newLeft;
  }
  
}; // end of heapNode class

class heap
{
  private:
  heapNode *root;
  int counter;

public:
  //constructor
  heap()
  {
    counter = 0;
    root = NULL;
  }

  void realInsert(int ar[], int pos, heapNode *parent, heapNode *newNode)
  {
    if(ar[pos] == 0)
    {
      if (parent->getLeft() == NULL)
	parent->setLeft(newNode);
      else
	realInsert(ar, pos-1, parent->left, newNode);
      if(parent->getLeft()->getValue() < parent->getValue())
      {
	heapNode *tempParentLeft = new heapNode(parent->getLeft()->getValue());
        heapNode *tempParent = new heapNode(parent->getValue());
        parent->setValue(tempParent->getValue());
        parent->left->setValue(tempParentLeft->getValue());
      }
    }
    else if(ar[pos] == 1)
    {
	if (parent->getRight() == NULL)
	  parent->setRight(newNode);
	else
	  realInsert(ar, pos-1, parent->right, newNode);
      if(parent->getRight()->getValue() < parent->getValue())
      {
	heapNode *tempParentRight = new heapNode(parent->getRight()->getValue());
        heapNode *tempParent = new heapNode(parent->getValue());
        parent->setValue(tempParent->getValue());
        parent->right->setValue(tempParentRight->getValue());
      }
    }
  }

  // find the spot to put new value
  void insertSpot(int option)
  {
    heapNode *newNode = new heapNode(option);
    counter++;
    if(root == NULL)
    {
      root = newNode;
    }

    else
    {
      int arrayValue;
      bool isOne = false;
      int ar[32];
      int i;
      int temp = counter;
      for(i = 0; i < 32; i++)
      {
          arrayValue = temp % 2;
          temp = temp / 2;
          ar[i] = arrayValue;
      }
 
      for(i = 0; i < 32; i++)
        cout << ar[i] << " ";
      cout << endl;

      i=31;
      while(i >= 0)
      {
        if(ar[i] == 1)
          isOne = true;
        if(isOne == true)
          break;
        i--;
      }
      i--;
      cout << "Broke loop with i = " << i << endl;
      realInsert(ar, i, root, newNode);
    }
  }
   
  //print
  void print()
  {
    cout << "Printing the heap...\n";
    printNode(root, 0);
  }

  void printNode(heapNode *node, int level)
  {
    if(node != NULL)
    {
      for(int i = 0; i <= level; i++)
      {     
        //cout << node->getValue()
          cout   << "\t"
             << "\t"
             << "\t"
	     << node->getValue() 
             << endl;
        printNode(node->getLeft(), level + 1);
        printNode(node->getRight(), level + 1);
      }
    }
  }

  // get root
  heapNode* getRoot()
  {
    return root;
  }

/*
    int delete(rootValue)
    {
        heapNode *tempNode = new heapNode(value, *left, *right)
        go down the heap to the last one
        make it root
        last nodeValue = null
	while(not at the bottom level of tree)
	{
	  if(newRoot < *left)
	    break;
          elseif(newRoot > *left)
	    swap with left;
        }

        return tempNode;         
     }
*/

  }; // end of heap class

int main()
{
  heap *myHeap;

  myHeap = new heap();


  int option=9;
  while (option != 0) {
    cout << "Please enter a number: ";
    cin >> option;
    myHeap->insertSpot(option);
    myHeap->print();

    }

  myHeap->print();
  return 0;
}

#include <iostream>
using namespace std;

class heapNode
{
  private:
  int value;

  public:
  heapNode *left;
  heapNode *right;
  //constructor
  heapNode(int newValue)
  {
     value = newValue;
     left = NULL; 
     right = NULL;
  }
 
  //get value
  int getValue()
  {
    return value;
  }
  
  //get right
  heapNode* getRight()
  {
    return right;
  }

  //get left
  heapNode* getLeft()
  {
    return left;
  }

  //set value
  void setValue(int newValue)
  {
    value = newValue;
  }

  // set right
  void setRight(heapNode *newRight)
  {
    right = newRight;
  }

  // set left
  void setLeft(heapNode *newLeft)
  {
    left = newLeft;
  }
  
}; // end of heapNode class

class heap
{
  private:
  heapNode *root;
  int counter;

public:
  //constructor
  heap()
  {
    counter = 0;
    root = NULL;
  }

  void realInsert(int ar[], int pos, heapNode *parent, heapNode *newNode)
  {
    if(ar[pos] == 0)
    {
      if (parent->getLeft() == NULL)
	parent->setLeft(newNode);
      else
	realInsert(ar, pos-1, parent->left, newNode);
      if(parent->getLeft()->getValue() < parent->getValue())
      {
	heapNode *tempParentLeft = new heapNode(parent->getLeft()->getValue());
        heapNode *tempParent = new heapNode(parent->getValue());
        parent->setValue(tempParent->getValue());
        parent->left->setValue(tempParentLeft->getValue());
      }
    }
    else if(ar[pos] == 1)
    {
	if (parent->getRight() == NULL)
	  parent->setRight(newNode);
	else
	  realInsert(ar, pos-1, parent->right, newNode);
      if(parent->getRight()->getValue() < parent->getValue())
      {
	heapNode *tempParentRight = new heapNode(parent->getRight()->getValue());
        heapNode *tempParent = new heapNode(parent->getValue());
        parent->setValue(tempParent->getValue());
        parent->right->setValue(tempParentRight->getValue());
      }
    }
  }

  // find the spot to put new value
  void insertSpot(int option)
  {
    heapNode *newNode = new heapNode(option);
    counter++;
    if(root == NULL)
    {
      root = newNode;
    }

    else
    {
      int arrayValue;
      bool isOne = false;
      int ar[32];
      int i;
      int temp = counter;
      for(i = 0; i < 32; i++)
      {
          arrayValue = temp % 2;
          temp = temp / 2;
          ar[i] = arrayValue;
      }
 
      for(i = 0; i < 32; i++)
        cout << ar[i] << " ";
      cout << endl;

      i=31;
      while(i >= 0)
      {
        if(ar[i] == 1)
          isOne = true;
        if(isOne == true)
          break;
        i--;
      }
      i--;
      cout << "Broke loop with i = " << i << endl;
      realInsert(ar, i, root, newNode);
    }
  }
   
  //print
  void print()
  {
    cout << "Printing the heap...\n";
    printNode(root, 0);
  }

  void printNode(heapNode *node, int level)
  {
    if(node != NULL)
    {
      for(int i = 0; i <= level; i++)
      {     
        //cout << node->getValue()
          cout   << "\t"
             << "\t"
             << "\t"
	     << node->getValue() 
             << endl;
        printNode(node->getLeft(), level + 1);
        printNode(node->getRight(), level + 1);
      }
    }
  }

  // get root
  heapNode* getRoot()
  {
    return root;
  }

/*
    int delete(rootValue)
    {
        heapNode *tempNode = new heapNode(value, *left, *right)
        go down the heap to the last one
        make it root
        last nodeValue = null
	while(not at the bottom level of tree)
	{
	  if(newRoot < *left)
	    break;
          elseif(newRoot > *left)
	    swap with left;
        }

        return tempNode;         
     }
*/

  }; // end of heap class

int main()
{
  heap *myHeap;

  myHeap = new heap();


  int option=9;
  while (option != 0) {
    cout << "Please enter a number: ";
    cin >> option;
    myHeap->insertSpot(option);
    myHeap->print();

    }

  myHeap->print();
  return 0;
}

cwl157 · Apr 4th, 2006, 5:10 PM

alright stupid mistake on my part. I had the temps going back into their original values. Now the levels are ok and the values go where they are supposed to. However i am still confused on how to make the different levels print. Its something with a for loop and passing in the number of levels and then putting spaces for the number of levels or something like that but i am not really sure how to put it together.

(Toggle Plain Text)

#include <iostream>
using namespace std;

class heapNode
{
  private:
  int value;

  public:
  heapNode *left;
  heapNode *right;
  //constructor
  heapNode(int newValue)
  {
     value = newValue;
     left = NULL; 
     right = NULL;
  }
 
  //get value
  int getValue()
  {
    return value;
  }
  
  //get right
  heapNode* getRight()
  {
    return right;
  }

  //get left
  heapNode* getLeft()
  {
    return left;
  }

  //set value
  void setValue(int newValue)
  {
    value = newValue;
  }

  // set right
  void setRight(heapNode *newRight)
  {
    right = newRight;
  }

  // set left
  void setLeft(heapNode *newLeft)
  {
    left = newLeft;
  }
  
}; // end of heapNode class

class heap
{
  private:
  heapNode *root;
  int counter;

public:
  //constructor
  heap()
  {
    counter = 0;
    root = NULL;
  }

  void realInsert(int ar[], int pos, heapNode *parent, heapNode *newNode)
  {
    if(ar[pos] == 0)
    {
      if (parent->getLeft() == NULL)
	parent->setLeft(newNode);
      else
	realInsert(ar, pos-1, parent->left, newNode);
      if(parent->getLeft()->getValue() < parent->getValue())
      {
	int tempParentLeft = parent->getLeft()->getValue();
        int tempParent = parent->getValue();
	//heapNode *tempParentLeft = new heapNode(parent->getLeft()->getValue());
        //heapNode *tempParent = new heapNode(parent->getValue());
        parent->setValue(tempParentLeft);
        parent->left->setValue(tempParent);
      }
    }
    else if(ar[pos] == 1)
    {
	if (parent->getRight() == NULL)
	  parent->setRight(newNode);
	else
	  realInsert(ar, pos-1, parent->right, newNode);
      if(parent->getRight()->getValue() < parent->getValue())
      {
        int tempParentRight = parent->getRight()->getValue();
        int tempParent = parent->getValue();
	//heapNode *tempParentRight = new heapNode(parent->getRight()->getValue());
        //heapNode *tempParent = new heapNode(parent->getValue());
        parent->setValue(tempParentRight);
        parent->right->setValue(tempParent);
      }
    }
  }

  // find the spot to put new value
  void insertSpot(int option)
  {
    heapNode *newNode = new heapNode(option);
    counter++;
    if(root == NULL)
    {
      root = newNode;
    }

    else
    {
      int arrayValue;
      bool isOne = false;
      int ar[32];
      int i;
      int temp = counter;
      for(i = 0; i < 32; i++)
      {
          arrayValue = temp % 2;
          temp = temp / 2;
          ar[i] = arrayValue;
      }
 
      for(i = 0; i < 32; i++)
        cout << ar[i] << " ";
      cout << endl;

      i=31;
      while(i >= 0)
      {
        if(ar[i] == 1)
          isOne = true;
        if(isOne == true)
          break;
        i--;
      }
      i--;
      cout << "Broke loop with i = " << i << endl;
      realInsert(ar, i, root, newNode);
    }
  }
   
  //print
  void print()
  {
    cout << "Printing the heap...\n";
    printNode(root, 0);
  }

  void printNode(heapNode *node, int level)
  {
    if(node != NULL)
    {
      cout << "Level: " << level << " Val: " << node->getValue() << "\n";
      //for(int i = 0; i <= level; i++)
      //{     
      //cout << node->getValue();
      //  cout   << "\t"
      //     << "\t"
      //     << "\t"
	  //     << node->getValue() 
      //     << endl;
      //  i = level;
        printNode(node->getLeft(), level + 1);
        printNode(node->getRight(), level + 1);
	//     }
    }
  }

  // get root
  heapNode* getRoot()
  {
    return root;
  }

/*
    int delete(rootValue)
    {
        heapNode *tempNode = new heapNode(value, *left, *right)
        go down the heap to the last one
        make it root
        last nodeValue = null
	while(not at the bottom level of tree)
	{
	  if(newRoot < *left)
	    break;
          elseif(newRoot > *left)
	    swap with left;
        }

        return tempNode;         
     }
*/

  }; // end of heap class

int main()
{
  heap *myHeap;

  myHeap = new heap();


  int option=9;
  while (option != 0) {
    cout << "Please enter a number: ";
    cin >> option;
    myHeap->insertSpot(option);
    myHeap->print();

    }

  myHeap->print();
  return 0;
}

#include <iostream>
using namespace std;

class heapNode
{
  private:
  int value;

  public:
  heapNode *left;
  heapNode *right;
  //constructor
  heapNode(int newValue)
  {
     value = newValue;
     left = NULL; 
     right = NULL;
  }
 
  //get value
  int getValue()
  {
    return value;
  }
  
  //get right
  heapNode* getRight()
  {
    return right;
  }

  //get left
  heapNode* getLeft()
  {
    return left;
  }

  //set value
  void setValue(int newValue)
  {
    value = newValue;
  }

  // set right
  void setRight(heapNode *newRight)
  {
    right = newRight;
  }

  // set left
  void setLeft(heapNode *newLeft)
  {
    left = newLeft;
  }
  
}; // end of heapNode class

class heap
{
  private:
  heapNode *root;
  int counter;

public:
  //constructor
  heap()
  {
    counter = 0;
    root = NULL;
  }

  void realInsert(int ar[], int pos, heapNode *parent, heapNode *newNode)
  {
    if(ar[pos] == 0)
    {
      if (parent->getLeft() == NULL)
	parent->setLeft(newNode);
      else
	realInsert(ar, pos-1, parent->left, newNode);
      if(parent->getLeft()->getValue() < parent->getValue())
      {
	int tempParentLeft = parent->getLeft()->getValue();
        int tempParent = parent->getValue();
	//heapNode *tempParentLeft = new heapNode(parent->getLeft()->getValue());
        //heapNode *tempParent = new heapNode(parent->getValue());
        parent->setValue(tempParentLeft);
        parent->left->setValue(tempParent);
      }
    }
    else if(ar[pos] == 1)
    {
	if (parent->getRight() == NULL)
	  parent->setRight(newNode);
	else
	  realInsert(ar, pos-1, parent->right, newNode);
      if(parent->getRight()->getValue() < parent->getValue())
      {
        int tempParentRight = parent->getRight()->getValue();
        int tempParent = parent->getValue();
	//heapNode *tempParentRight = new heapNode(parent->getRight()->getValue());
        //heapNode *tempParent = new heapNode(parent->getValue());
        parent->setValue(tempParentRight);
        parent->right->setValue(tempParent);
      }
    }
  }

  // find the spot to put new value
  void insertSpot(int option)
  {
    heapNode *newNode = new heapNode(option);
    counter++;
    if(root == NULL)
    {
      root = newNode;
    }

    else
    {
      int arrayValue;
      bool isOne = false;
      int ar[32];
      int i;
      int temp = counter;
      for(i = 0; i < 32; i++)
      {
          arrayValue = temp % 2;
          temp = temp / 2;
          ar[i] = arrayValue;
      }
 
      for(i = 0; i < 32; i++)
        cout << ar[i] << " ";
      cout << endl;

      i=31;
      while(i >= 0)
      {
        if(ar[i] == 1)
          isOne = true;
        if(isOne == true)
          break;
        i--;
      }
      i--;
      cout << "Broke loop with i = " << i << endl;
      realInsert(ar, i, root, newNode);
    }
  }
   
  //print
  void print()
  {
    cout << "Printing the heap...\n";
    printNode(root, 0);
  }

  void printNode(heapNode *node, int level)
  {
    if(node != NULL)
    {
      cout << "Level: " << level << " Val: " << node->getValue() << "\n";
      //for(int i = 0; i <= level; i++)
      //{     
      //cout << node->getValue();
      //  cout   << "\t"
      //     << "\t"
      //     << "\t"
	  //     << node->getValue() 
      //     << endl;
      //  i = level;
        printNode(node->getLeft(), level + 1);
        printNode(node->getRight(), level + 1);
	//     }
    }
  }

  // get root
  heapNode* getRoot()
  {
    return root;
  }

/*
    int delete(rootValue)
    {
        heapNode *tempNode = new heapNode(value, *left, *right)
        go down the heap to the last one
        make it root
        last nodeValue = null
	while(not at the bottom level of tree)
	{
	  if(newRoot < *left)
	    break;
          elseif(newRoot > *left)
	    swap with left;
        }

        return tempNode;         
     }
*/

  }; // end of heap class

int main()
{
  heap *myHeap;

  myHeap = new heap();


  int option=9;
  while (option != 0) {
    cout << "Please enter a number: ";
    cin >> option;
    myHeap->insertSpot(option);
    myHeap->print();

    }

  myHeap->print();
  return 0;
}

The Dark · Apr 4th, 2006, 6:28 PM

Well done!

If you just want to indent by the number of levels a simple way would be:

(Toggle Plain Text)

for(int i = 0; i < level; i++)
  cout << "\t"

Just put that before printing the data. (I just copied this from your commented out bits).

cwl157 · Apr 4th, 2006, 9:42 PM

when i do that this is what it prints out

Quote:

Printing the heap...
0 78 55Printing the heap...
0 78 55

I need verticle spaces in there too. So when you turn the paper sideways it looks like a tree. I would show you what i mean but when i type it out in this forum everything is to the left and it ignores the blanks spaces i put in. But in this example it would have the 78 on the first line indented then on the next line it would have the 0 to the left and on the third line the 55 indented so when you turn the paper it looks like a tree with root 0.

The Dark · Apr 4th, 2006, 10:11 PM

In that case, you need to print out the right hand child, then the current node, then the left hand child. The indent should work OK (personally I would use a space or two rather than a tab). Remember to add a "\n" to the end of the output of each node's value to output a new line.

If that doesn't work, show us the printing code you are using now.

cwl157 · Apr 4th, 2006, 10:35 PM

alright heres the updated code. I get a segmentation fault when it prints

(Toggle Plain Text)

// add, print and delete a number from a binary min heap

#include <iostream>
using namespace std;

// node containing int value and left and right pointers
// constructor, get value, get right, get left, set value, set left, set right
class heapNode
{
  private:
  int value;

  public:
  heapNode *left;
  heapNode *right;

  //constructor
  heapNode(int newValue)
  {
     value = newValue;
     left = NULL; 
     right = NULL;
  }
 
  //get value
  int getValue()
  {
    return value;
  }
  
  //get right
  heapNode* getRight()
  {
    return right;
  }

  //get left
  heapNode* getLeft()
  {
    return left;
  }

  //set value
  void setValue(int newValue)
  {
    value = newValue;
  }

  // set right
  void setRight(heapNode *newRight)
  {
    right = newRight;
  }

  // set left
  void setLeft(heapNode *newLeft)
  {
    left = newLeft;
  }
  
}; // end of heapNode class

class heap
{
  private:
  heapNode *root;
  int counter;

public:
  //constructor
  heap()
  {
    counter = 0;
    root = NULL;
  }

  //insert new value, check to see if swap is needed
  void realInsert(int ar[], int pos, heapNode *parent, heapNode *newNode)
  {
    if(ar[pos] == 0)
    {
      if (parent->getLeft() == NULL)
	parent->setLeft(newNode);
      else
	realInsert(ar, pos-1, parent->left, newNode);
      if(parent->getLeft()->getValue() < parent->getValue())
      {
	int tempParentLeft = parent->getLeft()->getValue();
        int tempParent = parent->getValue();
        parent->setValue(tempParentLeft);
        parent->left->setValue(tempParent);
      }
    }
    else if(ar[pos] == 1)
    {
	if (parent->getRight() == NULL)
	  parent->setRight(newNode);
	else
	  realInsert(ar, pos-1, parent->right, newNode);
      if(parent->getRight()->getValue() < parent->getValue())
      {
        int tempParentRight = parent->getRight()->getValue();
        int tempParent = parent->getValue();
        parent->setValue(tempParentRight);
        parent->right->setValue(tempParent);
      }
    }
  }

  // find the spot to put new value
  void insertSpot(int option)
  {
    heapNode *newNode = new heapNode(option);
    counter++;
    if(root == NULL)
    {
      root = newNode;
    }

    else
    {
      int arrayValue;
      bool isOne = false;
      int ar[32];
      int i;
      int temp = counter;
      for(i = 0; i < 32; i++)
      {
          arrayValue = temp % 2;
          temp = temp / 2;
          ar[i] = arrayValue;
      }
 
      for(i = 0; i < 32; i++)
        cout << ar[i] << " ";
      cout << endl;

      i=31;
      while(i >= 0)
      {
        if(ar[i] == 1)
          isOne = true;
        if(isOne == true)
          break;
        i--;
      }
      i--;
      cout << "Broke loop with i = " << i << endl;
      realInsert(ar, i, root, newNode);
    }
  }
   
  //call printNode
  void print()
  {
    cout << "Printing the heap...\n";
    printNode(root, 0);
  }
  
  //print tree with spaces for levels of the tree
  void printNode(heapNode *node, int level)
  {
    if(node != NULL)
    {
      //cout << "Level: " << level << " Val: " << node->getValue() << "\n";
      for(int j = 0; j < level; j++)
      {
	cout << "\t";  
        cout << "\n";   
      }
      cout << node->left->getValue();
      cout << node->getValue();
      cout << node->right->getValue();
      
        printNode(node->getLeft(), level + 1);
        printNode(node->getRight(), level + 1);
     }
    }

  // get root
  heapNode* getRoot()
  {
    return root;
  }

/*
    int delete(rootValue)
    {
        heapNode *tempNode = new heapNode(value, *left, *right)
        go down the heap to the last one
        make it root
        last nodeValue = null
	while(not at the bottom level of tree)
	{
	  if(newRoot < *left)
	    break;
          elseif(newRoot > *left)
	    swap with left;
        }

        return tempNode;         
     }
*/

  }; // end of heap class

// menu with add, print, delete choices  call methods from heap class
int main()
{
  heap *myHeap;

  myHeap = new heap();


  int option=9;
  while (option != 0) {
    cout << "Please enter a number: ";
    cin >> option;
    myHeap->insertSpot(option);
    myHeap->print();

    }

  myHeap->print();
  return 0;
}

// add, print and delete a number from a binary min heap

#include <iostream>
using namespace std;

// node containing int value and left and right pointers
// constructor, get value, get right, get left, set value, set left, set right
class heapNode
{
  private:
  int value;

  public:
  heapNode *left;
  heapNode *right;

  //constructor
  heapNode(int newValue)
  {
     value = newValue;
     left = NULL; 
     right = NULL;
  }
 
  //get value
  int getValue()
  {
    return value;
  }
  
  //get right
  heapNode* getRight()
  {
    return right;
  }

  //get left
  heapNode* getLeft()
  {
    return left;
  }

  //set value
  void setValue(int newValue)
  {
    value = newValue;
  }

  // set right
  void setRight(heapNode *newRight)
  {
    right = newRight;
  }

  // set left
  void setLeft(heapNode *newLeft)
  {
    left = newLeft;
  }
  
}; // end of heapNode class

class heap
{
  private:
  heapNode *root;
  int counter;

public:
  //constructor
  heap()
  {
    counter = 0;
    root = NULL;
  }

  //insert new value, check to see if swap is needed
  void realInsert(int ar[], int pos, heapNode *parent, heapNode *newNode)
  {
    if(ar[pos] == 0)
    {
      if (parent->getLeft() == NULL)
	parent->setLeft(newNode);
      else
	realInsert(ar, pos-1, parent->left, newNode);
      if(parent->getLeft()->getValue() < parent->getValue())
      {
	int tempParentLeft = parent->getLeft()->getValue();
        int tempParent = parent->getValue();
        parent->setValue(tempParentLeft);
        parent->left->setValue(tempParent);
      }
    }
    else if(ar[pos] == 1)
    {
	if (parent->getRight() == NULL)
	  parent->setRight(newNode);
	else
	  realInsert(ar, pos-1, parent->right, newNode);
      if(parent->getRight()->getValue() < parent->getValue())
      {
        int tempParentRight = parent->getRight()->getValue();
        int tempParent = parent->getValue();
        parent->setValue(tempParentRight);
        parent->right->setValue(tempParent);
      }
    }
  }

  // find the spot to put new value
  void insertSpot(int option)
  {
    heapNode *newNode = new heapNode(option);
    counter++;
    if(root == NULL)
    {
      root = newNode;
    }

    else
    {
      int arrayValue;
      bool isOne = false;
      int ar[32];
      int i;
      int temp = counter;
      for(i = 0; i < 32; i++)
      {
          arrayValue = temp % 2;
          temp = temp / 2;
          ar[i] = arrayValue;
      }
 
      for(i = 0; i < 32; i++)
        cout << ar[i] << " ";
      cout << endl;

      i=31;
      while(i >= 0)
      {
        if(ar[i] == 1)
          isOne = true;
        if(isOne == true)
          break;
        i--;
      }
      i--;
      cout << "Broke loop with i = " << i << endl;
      realInsert(ar, i, root, newNode);
    }
  }
   
  //call printNode
  void print()
  {
    cout << "Printing the heap...\n";
    printNode(root, 0);
  }
  
  //print tree with spaces for levels of the tree
  void printNode(heapNode *node, int level)
  {
    if(node != NULL)
    {
      //cout << "Level: " << level << " Val: " << node->getValue() << "\n";
      for(int j = 0; j < level; j++)
      {
	cout << "\t";  
        cout << "\n";   
      }
      cout << node->left->getValue();
      cout << node->getValue();
      cout << node->right->getValue();
      
        printNode(node->getLeft(), level + 1);
        printNode(node->getRight(), level + 1);
     }
    }

  // get root
  heapNode* getRoot()
  {
    return root;
  }

/*
    int delete(rootValue)
    {
        heapNode *tempNode = new heapNode(value, *left, *right)
        go down the heap to the last one
        make it root
        last nodeValue = null
	while(not at the bottom level of tree)
	{
	  if(newRoot < *left)
	    break;
          elseif(newRoot > *left)
	    swap with left;
        }

        return tempNode;         
     }
*/

  }; // end of heap class

// menu with add, print, delete choices  call methods from heap class
int main()
{
  heap *myHeap;

  myHeap = new heap();


  int option=9;
  while (option != 0) {
    cout << "Please enter a number: ";
    cin >> option;
    myHeap->insertSpot(option);
    myHeap->print();

    }

  myHeap->print();
  return 0;
}

Apr 2nd, 2006, 10:02 AM	#51
nnxion Programming Guru Join Date: Jun 2005 Location: elemental plane Posts: 1,429 Rep Power: 5	When The Dark says you should do: (Toggle Plain Text) void insertSpot(int option) { heapNode newNode = new heapNode(option); // Increment counter first as the algorithm needs it counter++;* if (root == NULL) { root = newNode; } else { ........................... int temp = counter; for(i = 0; i < 32; i++) { arrayValue = temp % 2; temp = temp / 2; ar = arrayValue; } void insertSpot(int option) { heapNode newNode = new heapNode(option); // Increment counter first as the algorithm needs it counter++; if (root == NULL) { root = newNode; } else { ........................... int temp = counter; for(i = 0; i < 32; i++) { arrayValue = temp % 2; temp = temp / 2; ar = arrayValue; } Then you should not do: (Toggle Plain Text) void insertSpot(int option) { heapNode newNode = new heapNode(option); int arrayValue; bool isOne = false; int ar[32]; int i = 31; int temp = counter; counter++; void insertSpot(int option) { heapNode newNode = new heapNode(option); int arrayValue; bool isOne = false; int ar[32]; int i = 31; int temp = counter; counter++; Just following what The Dark says gives me something that almost compiles. You still need to change some things. Please study carefully and do not just try to compile and tell us "my compiler gives errors". Read post #49 to see what to do with parent. (Toggle Plain Text) #include <iostream> using namespace std; class heapNode { private: int value; public: heapNode left; heapNode right; heapNode(int newValue) { value = newValue; left = NULL; right = NULL; } int getValue() { return value; } heapNode getRight() { return right; } heapNode* getLeft() { return left; } void setValue(int newValue) { value = newValue; } void setRight(heapNode newRight) { right = newRight; } void setLeft(heapNode newLeft) { left = newLeft; } }; class heap { private: heapNode root; int counter; public: heap() { counter = 0; root = NULL; } void realInsert(int ar[], int pos, heapNode parent, heapNode newNode) { if(newNode->left == NULL) { realInsert(ar, pos-1, parent, newNode); if(newNode->left->getValue() < newNode->getValue()) { newNode->setValue(newNode->left->getValue()); counter++; } } else if(newNode->right == NULL) { realInsert(ar, pos-1, parent, newNode); if(newNode->right->getValue() < newNode->getValue()) { newNode->setValue(newNode->right->getValue()); counter++; } } } void insertSpot(int option) { heapNode newNode = new heapNode(option); // Increment counter first as the algorithm needs it counter++; if (root == NULL) { root = newNode; } else { int arrayValue; bool isOne = false; int ar[32]; int i = 31; int temp = counter; for(i = 0; i < 32; i++) { arrayValue = temp % 2; temp = temp / 2; ar[i] = arrayValue; // changed from ar to ar[i] } for(int i = 0; i < 32; i++) cout << ar[i] << " "; cout << endl; while(i >= 0) { if(ar[i] == 1) isOne = true; if(isOne = true) break; i--; } realInsert(ar, i, parent, newNode); // still needs fixing } } void print() { printNode(root, 0); } void printNode(heapNode node, int level) { if(node != NULL) { cout << "Level: " << " Val: " << node->getValue() << "\n"; printNode(node->getLeft(), level + 1); printNode(node->getRight(), level + 1); } } heapNode getRoot() { return root; } }; int main() { heap myHeap; myHeap = new heap(); int option = -1; while (option != 0) { cout << "Please enter a number: "; cin >> option; myHeap->insertSpot(option); } myHeap->print(); return 0; } #include <iostream> using namespace std; class heapNode { private: int value; public: heapNode left; heapNode right; heapNode(int newValue) { value = newValue; left = NULL; right = NULL; } int getValue() { return value; } heapNode getRight() { return right; } heapNode* getLeft() { return left; } void setValue(int newValue) { value = newValue; } void setRight(heapNode newRight) { right = newRight; } void setLeft(heapNode newLeft) { left = newLeft; } }; class heap { private: heapNode root; int counter; public: heap() { counter = 0; root = NULL; } void realInsert(int ar[], int pos, heapNode parent, heapNode newNode) { if(newNode->left == NULL) { realInsert(ar, pos-1, parent, newNode); if(newNode->left->getValue() < newNode->getValue()) { newNode->setValue(newNode->left->getValue()); counter++; } } else if(newNode->right == NULL) { realInsert(ar, pos-1, parent, newNode); if(newNode->right->getValue() < newNode->getValue()) { newNode->setValue(newNode->right->getValue()); counter++; } } } void insertSpot(int option) { heapNode newNode = new heapNode(option); // Increment counter first as the algorithm needs it counter++; if (root == NULL) { root = newNode; } else { int arrayValue; bool isOne = false; int ar[32]; int i = 31; int temp = counter; for(i = 0; i < 32; i++) { arrayValue = temp % 2; temp = temp / 2; ar[i] = arrayValue; // changed from ar to ar[i] } for(int i = 0; i < 32; i++) cout << ar[i] << " "; cout << endl; while(i >= 0) { if(ar[i] == 1) isOne = true; if(isOne = true) break; i--; } realInsert(ar, i, parent, newNode); // still needs fixing } } void print() { printNode(root, 0); } void printNode(heapNode node, int level) { if(node != NULL) { cout << "Level: " << " Val: " << node->getValue() << "\n"; printNode(node->getLeft(), level + 1); printNode(node->getRight(), level + 1); } } heapNode getRoot() { return root; } }; int main() { heap myHeap; myHeap = new heap(); int option = -1; while (option != 0) { cout << "Please enter a number: "; cin >> option; myHeap->insertSpot(option); } myHeap->print(); return 0; } __________________ "Employ your time in improving yourself by other men's writings, so that you shall gain easily what others have labored hard for." -- Socrates Last edited by nnxion; Apr 2nd, 2006 at 10:18 AM.*

Apr 2nd, 2006, 8:32 PM	#54
The Dark Expert Programmer Join Date: Jun 2005 Posts: 884 Rep Power: 4	Also, in your realInsert function, you need to think about what you are trying to do. You are passing the ar and pos parameters for a reason, but your current code is not using them at all. - You need to be using the value of ar[pos] to decide whether to move left or right. - You also need a special case for pos == 0 in realInsert, because that mean you have hit the bottom of the heap and actually want to do the insert. - You never want to check the right or left values of newNode, because you have just allocated newNode so its right or left values will always be NULL. in your insertSpot, you need to fix this line (Toggle Plain Text) if(isOne = true) if(isOne = true) That is an assignment, not a test, so it will always evaluate to true. If you are under unix and are using gcc (or g++), have a look at gdb. It will let you single step through the code so you can see what the various variable values are.

Apr 4th, 2006, 6:28 PM	#57
The Dark Expert Programmer Join Date: Jun 2005 Posts: 884 Rep Power: 4	Well done! If you just want to indent by the number of levels a simple way would be: (Toggle Plain Text) for(int i = 0; i < level; i++) cout << "\t" for(int i = 0; i < level; i++) cout << "\t" Just put that before printing the data. (I just copied this from your commented out bits).

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Apr 4th, 2006, 4:39 PM	#55
cwl157 Professional Programmer Join Date: Feb 2005 Posts: 346 Rep Power: 4	ok now i think it will make a lot more sense. I still have 1 problem with the insert and 1 problem with the print. For the insert i need it to swap the values if the new node entered is less than the parents node. For the print method i need it to print spaces to show each level of the tree. I have an attempt at both of these problems but i do not think either of them work right. I did the swapping problem first but thought it would be easier to see if that was working if it printed them in the proper layers so then i tried to do the layers but now neither work right. Here is the code: (Toggle Plain Text) #include <iostream> using namespace std; class heapNode { private: int value; public: heapNode left; heapNode right; //constructor heapNode(int newValue) { value = newValue; left = NULL; right = NULL; } //get value int getValue() { return value; } //get right heapNode* getRight() { return right; } //get left heapNode* getLeft() { return left; } //set value void setValue(int newValue) { value = newValue; } // set right void setRight(heapNode newRight) { right = newRight; } // set left void setLeft(heapNode newLeft) { left = newLeft; } }; // end of heapNode class class heap { private: heapNode root; int counter; public: //constructor heap() { counter = 0; root = NULL; } void realInsert(int ar[], int pos, heapNode parent, heapNode newNode) { if(ar[pos] == 0) { if (parent->getLeft() == NULL) parent->setLeft(newNode); else realInsert(ar, pos-1, parent->left, newNode); if(parent->getLeft()->getValue() < parent->getValue()) { heapNode tempParentLeft = new heapNode(parent->getLeft()->getValue()); heapNode tempParent = new heapNode(parent->getValue()); parent->setValue(tempParent->getValue()); parent->left->setValue(tempParentLeft->getValue()); } } else if(ar[pos] == 1) { if (parent->getRight() == NULL) parent->setRight(newNode); else realInsert(ar, pos-1, parent->right, newNode); if(parent->getRight()->getValue() < parent->getValue()) { heapNode tempParentRight = new heapNode(parent->getRight()->getValue()); heapNode tempParent = new heapNode(parent->getValue()); parent->setValue(tempParent->getValue()); parent->right->setValue(tempParentRight->getValue()); } } } // find the spot to put new value void insertSpot(int option) { heapNode newNode = new heapNode(option); counter++; if(root == NULL) { root = newNode; } else { int arrayValue; bool isOne = false; int ar[32]; int i; int temp = counter; for(i = 0; i < 32; i++) { arrayValue = temp % 2; temp = temp / 2; ar[i] = arrayValue; } for(i = 0; i < 32; i++) cout << ar[i] << " "; cout << endl; i=31; while(i >= 0) { if(ar[i] == 1) isOne = true; if(isOne == true) break; i--; } i--; cout << "Broke loop with i = " << i << endl; realInsert(ar, i, root, newNode); } } //print void print() { cout << "Printing the heap...\n"; printNode(root, 0); } void printNode(heapNode node, int level) { if(node != NULL) { for(int i = 0; i <= level; i++) { //cout << node->getValue() cout << "\t" << "\t" << "\t" << node->getValue() << endl; printNode(node->getLeft(), level + 1); printNode(node->getRight(), level + 1); } } } // get root heapNode getRoot() { return root; } /* int delete(rootValue) { heapNode tempNode = new heapNode(value, left, right) go down the heap to the last one make it root last nodeValue = null while(not at the bottom level of tree) { if(newRoot < left) break; elseif(newRoot > left) swap with left; } return tempNode; } / }; // end of heap class int main() { heap myHeap; myHeap = new heap(); int option=9; while (option != 0) { cout << "Please enter a number: "; cin >> option; myHeap->insertSpot(option); myHeap->print(); } myHeap->print(); return 0; } #include <iostream> using namespace std; class heapNode { private: int value; public: heapNode left; heapNode right; //constructor heapNode(int newValue) { value = newValue; left = NULL; right = NULL; } //get value int getValue() { return value; } //get right heapNode getRight() { return right; } //get left heapNode* getLeft() { return left; } //set value void setValue(int newValue) { value = newValue; } // set right void setRight(heapNode newRight) { right = newRight; } // set left void setLeft(heapNode newLeft) { left = newLeft; } }; // end of heapNode class class heap { private: heapNode root; int counter; public: //constructor heap() { counter = 0; root = NULL; } void realInsert(int ar[], int pos, heapNode parent, heapNode newNode) { if(ar[pos] == 0) { if (parent->getLeft() == NULL) parent->setLeft(newNode); else realInsert(ar, pos-1, parent->left, newNode); if(parent->getLeft()->getValue() < parent->getValue()) { heapNode tempParentLeft = new heapNode(parent->getLeft()->getValue()); heapNode tempParent = new heapNode(parent->getValue()); parent->setValue(tempParent->getValue()); parent->left->setValue(tempParentLeft->getValue()); } } else if(ar[pos] == 1) { if (parent->getRight() == NULL) parent->setRight(newNode); else realInsert(ar, pos-1, parent->right, newNode); if(parent->getRight()->getValue() < parent->getValue()) { heapNode tempParentRight = new heapNode(parent->getRight()->getValue()); heapNode tempParent = new heapNode(parent->getValue()); parent->setValue(tempParent->getValue()); parent->right->setValue(tempParentRight->getValue()); } } } // find the spot to put new value void insertSpot(int option) { heapNode newNode = new heapNode(option); counter++; if(root == NULL) { root = newNode; } else { int arrayValue; bool isOne = false; int ar[32]; int i; int temp = counter; for(i = 0; i < 32; i++) { arrayValue = temp % 2; temp = temp / 2; ar[i] = arrayValue; } for(i = 0; i < 32; i++) cout << ar[i] << " "; cout << endl; i=31; while(i >= 0) { if(ar[i] == 1) isOne = true; if(isOne == true) break; i--; } i--; cout << "Broke loop with i = " << i << endl; realInsert(ar, i, root, newNode); } } //print void print() { cout << "Printing the heap...\n"; printNode(root, 0); } void printNode(heapNode node, int level) { if(node != NULL) { for(int i = 0; i <= level; i++) { //cout << node->getValue() cout << "\t" << "\t" << "\t" << node->getValue() << endl; printNode(node->getLeft(), level + 1); printNode(node->getRight(), level + 1); } } } // get root heapNode getRoot() { return root; } /* int delete(rootValue) { heapNode tempNode = new heapNode(value, left, right) go down the heap to the last one make it root last nodeValue = null while(not at the bottom level of tree) { if(newRoot < left) break; elseif(newRoot > left) swap with left; } return tempNode; } / }; // end of heap class int main() { heap *myHeap; myHeap = new heap(); int option=9; while (option != 0) { cout << "Please enter a number: "; cin >> option; myHeap->insertSpot(option); myHeap->print(); } myHeap->print(); return 0; }

Apr 4th, 2006, 5:10 PM	#56
cwl157 Professional Programmer Join Date: Feb 2005 Posts: 346 Rep Power: 4	alright stupid mistake on my part. I had the temps going back into their original values. Now the levels are ok and the values go where they are supposed to. However i am still confused on how to make the different levels print. Its something with a for loop and passing in the number of levels and then putting spaces for the number of levels or something like that but i am not really sure how to put it together. (Toggle Plain Text) #include <iostream> using namespace std; class heapNode { private: int value; public: heapNode left; heapNode right; //constructor heapNode(int newValue) { value = newValue; left = NULL; right = NULL; } //get value int getValue() { return value; } //get right heapNode* getRight() { return right; } //get left heapNode* getLeft() { return left; } //set value void setValue(int newValue) { value = newValue; } // set right void setRight(heapNode newRight) { right = newRight; } // set left void setLeft(heapNode newLeft) { left = newLeft; } }; // end of heapNode class class heap { private: heapNode root; int counter; public: //constructor heap() { counter = 0; root = NULL; } void realInsert(int ar[], int pos, heapNode parent, heapNode newNode) { if(ar[pos] == 0) { if (parent->getLeft() == NULL) parent->setLeft(newNode); else realInsert(ar, pos-1, parent->left, newNode); if(parent->getLeft()->getValue() < parent->getValue()) { int tempParentLeft = parent->getLeft()->getValue(); int tempParent = parent->getValue(); //heapNode tempParentLeft = new heapNode(parent->getLeft()->getValue()); //heapNode tempParent = new heapNode(parent->getValue()); parent->setValue(tempParentLeft); parent->left->setValue(tempParent); } } else if(ar[pos] == 1) { if (parent->getRight() == NULL) parent->setRight(newNode); else realInsert(ar, pos-1, parent->right, newNode); if(parent->getRight()->getValue() < parent->getValue()) { int tempParentRight = parent->getRight()->getValue(); int tempParent = parent->getValue(); //heapNode tempParentRight = new heapNode(parent->getRight()->getValue()); //heapNode tempParent = new heapNode(parent->getValue()); parent->setValue(tempParentRight); parent->right->setValue(tempParent); } } } // find the spot to put new value void insertSpot(int option) { heapNode newNode = new heapNode(option); counter++; if(root == NULL) { root = newNode; } else { int arrayValue; bool isOne = false; int ar[32]; int i; int temp = counter; for(i = 0; i < 32; i++) { arrayValue = temp % 2; temp = temp / 2; ar[i] = arrayValue; } for(i = 0; i < 32; i++) cout << ar[i] << " "; cout << endl; i=31; while(i >= 0) { if(ar[i] == 1) isOne = true; if(isOne == true) break; i--; } i--; cout << "Broke loop with i = " << i << endl; realInsert(ar, i, root, newNode); } } //print void print() { cout << "Printing the heap...\n"; printNode(root, 0); } void printNode(heapNode node, int level) { if(node != NULL) { cout << "Level: " << level << " Val: " << node->getValue() << "\n"; //for(int i = 0; i <= level; i++) //{ //cout << node->getValue(); // cout << "\t" // << "\t" // << "\t" // << node->getValue() // << endl; // i = level; printNode(node->getLeft(), level + 1); printNode(node->getRight(), level + 1); // } } } // get root heapNode getRoot() { return root; } /* int delete(rootValue) { heapNode tempNode = new heapNode(value, left, right) go down the heap to the last one make it root last nodeValue = null while(not at the bottom level of tree) { if(newRoot < left) break; elseif(newRoot > left) swap with left; } return tempNode; } / }; // end of heap class int main() { heap myHeap; myHeap = new heap(); int option=9; while (option != 0) { cout << "Please enter a number: "; cin >> option; myHeap->insertSpot(option); myHeap->print(); } myHeap->print(); return 0; } #include <iostream> using namespace std; class heapNode { private: int value; public: heapNode left; heapNode right; //constructor heapNode(int newValue) { value = newValue; left = NULL; right = NULL; } //get value int getValue() { return value; } //get right heapNode getRight() { return right; } //get left heapNode* getLeft() { return left; } //set value void setValue(int newValue) { value = newValue; } // set right void setRight(heapNode newRight) { right = newRight; } // set left void setLeft(heapNode newLeft) { left = newLeft; } }; // end of heapNode class class heap { private: heapNode root; int counter; public: //constructor heap() { counter = 0; root = NULL; } void realInsert(int ar[], int pos, heapNode parent, heapNode newNode) { if(ar[pos] == 0) { if (parent->getLeft() == NULL) parent->setLeft(newNode); else realInsert(ar, pos-1, parent->left, newNode); if(parent->getLeft()->getValue() < parent->getValue()) { int tempParentLeft = parent->getLeft()->getValue(); int tempParent = parent->getValue(); //heapNode tempParentLeft = new heapNode(parent->getLeft()->getValue()); //heapNode tempParent = new heapNode(parent->getValue()); parent->setValue(tempParentLeft); parent->left->setValue(tempParent); } } else if(ar[pos] == 1) { if (parent->getRight() == NULL) parent->setRight(newNode); else realInsert(ar, pos-1, parent->right, newNode); if(parent->getRight()->getValue() < parent->getValue()) { int tempParentRight = parent->getRight()->getValue(); int tempParent = parent->getValue(); //heapNode tempParentRight = new heapNode(parent->getRight()->getValue()); //heapNode tempParent = new heapNode(parent->getValue()); parent->setValue(tempParentRight); parent->right->setValue(tempParent); } } } // find the spot to put new value void insertSpot(int option) { heapNode newNode = new heapNode(option); counter++; if(root == NULL) { root = newNode; } else { int arrayValue; bool isOne = false; int ar[32]; int i; int temp = counter; for(i = 0; i < 32; i++) { arrayValue = temp % 2; temp = temp / 2; ar[i] = arrayValue; } for(i = 0; i < 32; i++) cout << ar[i] << " "; cout << endl; i=31; while(i >= 0) { if(ar[i] == 1) isOne = true; if(isOne == true) break; i--; } i--; cout << "Broke loop with i = " << i << endl; realInsert(ar, i, root, newNode); } } //print void print() { cout << "Printing the heap...\n"; printNode(root, 0); } void printNode(heapNode node, int level) { if(node != NULL) { cout << "Level: " << level << " Val: " << node->getValue() << "\n"; //for(int i = 0; i <= level; i++) //{ //cout << node->getValue(); // cout << "\t" // << "\t" // << "\t" // << node->getValue() // << endl; // i = level; printNode(node->getLeft(), level + 1); printNode(node->getRight(), level + 1); // } } } // get root heapNode getRoot() { return root; } /* int delete(rootValue) { heapNode tempNode = new heapNode(value, left, right) go down the heap to the last one make it root last nodeValue = null while(not at the bottom level of tree) { if(newRoot < left) break; elseif(newRoot > left) swap with left; } return tempNode; } / }; // end of heap class int main() { heap *myHeap; myHeap = new heap(); int option=9; while (option != 0) { cout << "Please enter a number: "; cin >> option; myHeap->insertSpot(option); myHeap->print(); } myHeap->print(); return 0; }

Apr 4th, 2006, 10:11 PM	#59
The Dark Expert Programmer Join Date: Jun 2005 Posts: 884 Rep Power: 4	In that case, you need to print out the right hand child, then the current node, then the left hand child. The indent should work OK (personally I would use a space or two rather than a tab). Remember to add a "\n" to the end of the output of each node's value to output a new line. If that doesn't work, show us the printing code you are using now.

Apr 4th, 2006, 10:35 PM	#60
cwl157 Professional Programmer Join Date: Feb 2005 Posts: 346 Rep Power: 4	alright heres the updated code. I get a segmentation fault when it prints (Toggle Plain Text) // add, print and delete a number from a binary min heap #include <iostream> using namespace std; // node containing int value and left and right pointers // constructor, get value, get right, get left, set value, set left, set right class heapNode { private: int value; public: heapNode left; heapNode right; //constructor heapNode(int newValue) { value = newValue; left = NULL; right = NULL; } //get value int getValue() { return value; } //get right heapNode* getRight() { return right; } //get left heapNode* getLeft() { return left; } //set value void setValue(int newValue) { value = newValue; } // set right void setRight(heapNode newRight) { right = newRight; } // set left void setLeft(heapNode newLeft) { left = newLeft; } }; // end of heapNode class class heap { private: heapNode root; int counter; public: //constructor heap() { counter = 0; root = NULL; } //insert new value, check to see if swap is needed void realInsert(int ar[], int pos, heapNode parent, heapNode newNode) { if(ar[pos] == 0) { if (parent->getLeft() == NULL) parent->setLeft(newNode); else realInsert(ar, pos-1, parent->left, newNode); if(parent->getLeft()->getValue() < parent->getValue()) { int tempParentLeft = parent->getLeft()->getValue(); int tempParent = parent->getValue(); parent->setValue(tempParentLeft); parent->left->setValue(tempParent); } } else if(ar[pos] == 1) { if (parent->getRight() == NULL) parent->setRight(newNode); else realInsert(ar, pos-1, parent->right, newNode); if(parent->getRight()->getValue() < parent->getValue()) { int tempParentRight = parent->getRight()->getValue(); int tempParent = parent->getValue(); parent->setValue(tempParentRight); parent->right->setValue(tempParent); } } } // find the spot to put new value void insertSpot(int option) { heapNode newNode = new heapNode(option); counter++; if(root == NULL) { root = newNode; } else { int arrayValue; bool isOne = false; int ar[32]; int i; int temp = counter; for(i = 0; i < 32; i++) { arrayValue = temp % 2; temp = temp / 2; ar[i] = arrayValue; } for(i = 0; i < 32; i++) cout << ar[i] << " "; cout << endl; i=31; while(i >= 0) { if(ar[i] == 1) isOne = true; if(isOne == true) break; i--; } i--; cout << "Broke loop with i = " << i << endl; realInsert(ar, i, root, newNode); } } //call printNode void print() { cout << "Printing the heap...\n"; printNode(root, 0); } //print tree with spaces for levels of the tree void printNode(heapNode node, int level) { if(node != NULL) { //cout << "Level: " << level << " Val: " << node->getValue() << "\n"; for(int j = 0; j < level; j++) { cout << "\t"; cout << "\n"; } cout << node->left->getValue(); cout << node->getValue(); cout << node->right->getValue(); printNode(node->getLeft(), level + 1); printNode(node->getRight(), level + 1); } } // get root heapNode getRoot() { return root; } /* int delete(rootValue) { heapNode tempNode = new heapNode(value, left, right) go down the heap to the last one make it root last nodeValue = null while(not at the bottom level of tree) { if(newRoot < left) break; elseif(newRoot > left) swap with left; } return tempNode; } / }; // end of heap class // menu with add, print, delete choices call methods from heap class int main() { heap myHeap; myHeap = new heap(); int option=9; while (option != 0) { cout << "Please enter a number: "; cin >> option; myHeap->insertSpot(option); myHeap->print(); } myHeap->print(); return 0; } // add, print and delete a number from a binary min heap #include <iostream> using namespace std; // node containing int value and left and right pointers // constructor, get value, get right, get left, set value, set left, set right class heapNode { private: int value; public: heapNode left; heapNode right; //constructor heapNode(int newValue) { value = newValue; left = NULL; right = NULL; } //get value int getValue() { return value; } //get right heapNode getRight() { return right; } //get left heapNode* getLeft() { return left; } //set value void setValue(int newValue) { value = newValue; } // set right void setRight(heapNode newRight) { right = newRight; } // set left void setLeft(heapNode newLeft) { left = newLeft; } }; // end of heapNode class class heap { private: heapNode root; int counter; public: //constructor heap() { counter = 0; root = NULL; } //insert new value, check to see if swap is needed void realInsert(int ar[], int pos, heapNode parent, heapNode newNode) { if(ar[pos] == 0) { if (parent->getLeft() == NULL) parent->setLeft(newNode); else realInsert(ar, pos-1, parent->left, newNode); if(parent->getLeft()->getValue() < parent->getValue()) { int tempParentLeft = parent->getLeft()->getValue(); int tempParent = parent->getValue(); parent->setValue(tempParentLeft); parent->left->setValue(tempParent); } } else if(ar[pos] == 1) { if (parent->getRight() == NULL) parent->setRight(newNode); else realInsert(ar, pos-1, parent->right, newNode); if(parent->getRight()->getValue() < parent->getValue()) { int tempParentRight = parent->getRight()->getValue(); int tempParent = parent->getValue(); parent->setValue(tempParentRight); parent->right->setValue(tempParent); } } } // find the spot to put new value void insertSpot(int option) { heapNode newNode = new heapNode(option); counter++; if(root == NULL) { root = newNode; } else { int arrayValue; bool isOne = false; int ar[32]; int i; int temp = counter; for(i = 0; i < 32; i++) { arrayValue = temp % 2; temp = temp / 2; ar[i] = arrayValue; } for(i = 0; i < 32; i++) cout << ar[i] << " "; cout << endl; i=31; while(i >= 0) { if(ar[i] == 1) isOne = true; if(isOne == true) break; i--; } i--; cout << "Broke loop with i = " << i << endl; realInsert(ar, i, root, newNode); } } //call printNode void print() { cout << "Printing the heap...\n"; printNode(root, 0); } //print tree with spaces for levels of the tree void printNode(heapNode node, int level) { if(node != NULL) { //cout << "Level: " << level << " Val: " << node->getValue() << "\n"; for(int j = 0; j < level; j++) { cout << "\t"; cout << "\n"; } cout << node->left->getValue(); cout << node->getValue(); cout << node->right->getValue(); printNode(node->getLeft(), level + 1); printNode(node->getRight(), level + 1); } } // get root heapNode getRoot() { return root; } /* int delete(rootValue) { heapNode tempNode = new heapNode(value, left, right) go down the heap to the last one make it root last nodeValue = null while(not at the bottom level of tree) { if(newRoot < left) break; elseif(newRoot > left) swap with left; } return tempNode; } / }; // end of heap class // menu with add, print, delete choices call methods from heap class int main() { heap *myHeap; myHeap = new heap(); int option=9; while (option != 0) { cout << "Please enter a number: "; cin >> option; myHeap->insertSpot(option); myHeap->print(); } myHeap->print(); return 0; }

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > C++

pointer help