Click here to Skip to main content
15,895,557 members
Search within:


C++ BinarySearchTree with insert wrong
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
C++
hello,I implement a BinarySearchTree in c++,but I found it can't insert elements well,can anybody fix this? Thank you! The following is my code.
C++
/*
 * BinaryTree.h
 *
 *  Created on: 2011-8-23
 *      Author: boge
 */

#ifndef BINARYTREE_H_
#define BINARYTREE_H_

enum ORDER_MODEL{
	ORDER_MODEL_PREV = 0,
	ORDER_MODEL_IN,
	ORDER_MODEL_POST
};

template<typename t>
struct treeNode{
        T date;
        treeNode<t> *parent,*left,*right;

        treeNode(T& d):date(d){}
        treeNode(T& d,treeNode<t>* p):date(d),parent(p){}
        treeNode(T& d,treeNode<t>* p,treeNode<t>* l,treeNode<t>* r):
        	date(d),parent(p),left(l),right(r){}
    	bool operator<(treeNode<t> &node){
    		return date < node.date;
    	}
    	bool operator>(treeNode<t> &node){
    		return date > node.date;
    	}
    	bool operator==(treeNode<t> &node){
    		return date == node.date;
    	}
	};

template<typename t>
class BinaryTree{
private:
	treeNode<t> *root;
	int theSize;
	treeNode<t>* tree_search(treeNode<t>* node,const T& key) const;
	treeNode<t>* tree_minim(const treeNode<t>* node) const;
	treeNode<t>* tree_maxm(const treeNode<t>* node) const;
//	void tree_insert(treeNode<t>* node,const T& key);
	void tree_remove(treeNode<t>* node,T& key);
    void destroy(treeNode<t>* node);
    void print_tree_prev(treeNode<t>*)const;
    void print_tree_in(treeNode<t>*)const;
    void print_tree_post(treeNode<t>*)const;

public:
	BinaryTree();
	~BinaryTree();
	int size();
    treeNode<t>* tree_search(T key){
    	return tree_search(root,key);
    }

    T& tree_minimum(){
    	return tree_minim(root).date;
    }

    T& tree_maxmum(){
    	return tree_maxm(root).date;
    }
    treeNode<t>* tree_sucessor(const treeNode<t>* node)const;
    treeNode<t>* tree_precessor(const treeNode<t>* node)const;
    void insert(const T& key);
    void remove(T& key);
    void makeEmpty();
    void print_tree(ORDER_MODEL model)const;
};

#endif /* BINARYTREE_H_ */


C++
/*
 * BinaryTree.cpp
 */
#include <iostream>
#include <string>
#include "BinaryTree.h"

using namespace std;

template<typename t>
BinaryTree<t>::BinaryTree():root(NULL),theSize(0){}

template<typename t>
BinaryTree<t>::~BinaryTree(){
	destroy(root);
}

template<typename t>
void BinaryTree<t>::destroy(treeNode<t>* node){
	if(node != NULL){
		destroy(node->left);
		destroy(node->right);
		delete node;
	}
	node = NULL;
}

template<typename t>
int BinaryTree<t>::size(){
	return theSize;
}

template<typename t>
treeNode<t>* BinaryTree<t>::tree_search(treeNode<t>* node,const T& key)const{
    while(node!=NULL && key != node->date){
    	if(key < node->date){
    		node = node->left;
    	node = node->right;
    	}
    }
    return node;
}

template<typename t>
treeNode<t>* BinaryTree<t>::tree_maxm(const treeNode<t>* node)const{
    while(node->right!=NULL){
    	node = node->right;
    }
    return node;
}

template<typename t>
treeNode<t>* BinaryTree<t>::tree_minim(const treeNode<t>* node) const{
	while(node->left!=NULL){
		node = node->left;
	}
	return node;
}

template<typename t>
treeNode<t>* BinaryTree<t>::tree_sucessor(const treeNode<t>* node)const{
    if(node==NULL){
    	return NULL;
    }
    else if(node.right!=NULL){
    	return tree_minim(node->right);
    }
    treeNode<t>* p = node.parent;
    while(p!=NULL && p->right = node){
    	node = p;
    	p = p.parent;
    }
    return p;
}

template<typename t>
treeNode<t>* BinaryTree<t>::tree_precessor(const treeNode<t>* node)const{
    if(node==NULL){
    	return NULL;
    }
    else if(node->left != NULL){
    	return tree_maxm(node->left);
    }
    treeNode<t>* p = node->parent;
    while(p!=NULL && p->left = node){
    	node = p;
    	p = p->parent;
    }
    return p;
}

template<typename t>
void BinaryTree<t>::makeEmpty(){
    destroy(root);
}

template<typename t>
void BinaryTree<t>::insert(const T& key){
    treeNode<t>* y = NULL;
    treeNode<t>* z = NULL;
    treeNode<t>* node = root;
    z->date = key;
    while(node!=NULL){
        y = node;
        if(z->date < node->date){
        	node = node->left;
        }else{
        	node = node->right;
        }
    }
    z->parent = y;
    if(y == NULL){
    	root = z;
    }else if(z->date < y->date){
        y->left = z;
    }else{
    	y->right = z;
    }
    theSize++;
}

template<typename t>
void BinaryTree<t>::remove(T& key){
    tree_remove(root,key);
}

template<typename t>
void BinaryTree<t>::tree_remove(treeNode<t>* node,T& key){
	treeNode<t>* z = tree_search(key);
	if(z==NULL)
		return;
    treeNode<t>* y = NULL;
    treeNode<t>* x = NULL;
    if(z->left == NULL || z->right == NULL){
    	y = z;
    }else{
    	y = tree_sucessor(z);
    }
    if(y->left!=NULL){
    	x = y->left;
    }else{
    	x = y->right;
    }
    if(x!=NULL){
    	x->parent = y->parent;
    }
    if(y->parent == NULL){
    	root = x;
    }else if(y == y->parent->left){
    	y->parent->left = x;
    }else{
    	y->parent->right = x;
    }
    if(y!=z){
    	z->date = y->date;
    }
    theSize--;
}

template<typename t>
void BinaryTree<t>::print_tree(ORDER_MODEL model)const{
	if(model == ORDER_MODEL_PREV){
		print_tree_prev(root);
	}else if(model == ORDER_MODEL_IN){
		print_tree_in(root);
	}else{
		print_tree_post(root);
	}
}

template<typename t>
void BinaryTree<t>::print_tree_in(treeNode<t>* node)const{
	cout << "[";
	while(node!=NULL){
		print_tree_in(node->left);
		cout << node->date << ",";
		print_tree_in(node->right);
	}
	cout << "]";
}

template<typename t>
void BinaryTree<t>::print_tree_prev(treeNode<t>* node)const{
	cout << "[";
	while(node!=NULL){
		cout << node->date << ",";
		print_tree_in(node->left);
		print_tree_in(node->right);
	}
	cout << "]";
}

template<typename t>
void BinaryTree<t>::print_tree_post(treeNode<t>* node)const{
	cout << "[";
	while(node!=NULL){
		print_tree_in(node->left);
		print_tree_in(node->right);
		cout << node->date << ",";
	}
	cout << "]";
}

int main(){
	cout << "ok~" << endl;
	BinaryTree<int> bt;
	cout << "1" << endl;
	bt.insert(5);
	bt.insert(7);
	cout << "2" << endl;
	bt.insert(9);
	cout << "ok?" << endl;
	bt.print_tree(ORDER_MODEL_PREV);
	return 0;
}
Posted
Updated 23-Aug-11 14:10pm
v4
Add a Solution
Comments
Philippe Mori 23-Aug-11 20:22pm    
I have fixed < with &lt; and > with &gt;.

I hope Code Project would eventually fix that problem and not interpret < and > int <pre> </pre> blocks and same for code blocks.

Maybe find an alternate way to specify things like bold inside a code block. A sequence of some uncommon characters like <{ ... }> could be required in those block to apply formatting if necessary.

3 solutions

Cant see any problems (except initialisation):
C++
/*
 * BinaryTree.h
 *
 *  Created on: 2011-8-23
 *      Author: boge
 */
 
#ifndef BINARYTREE_H_
#define BINARYTREE_H_
 
enum ORDER_MODEL{
  ORDER_MODEL_PREV = 0,
  ORDER_MODEL_IN,
  ORDER_MODEL_POST
};
 
template<typename T>
struct treeNode
{
  T              date;
  treeNode<T>*  parent,
              *  left,
              *  right;

  treeNode(T& d):date(d){ parent=left=right=0; }
  treeNode(T& d,treeNode<T>* p):date(d),parent(p){ parent=left=right=0; }
  treeNode(T& d,treeNode<T>* p,treeNode<T>* l,treeNode<T>* r):
  date(d),parent(p),left(l),right(r){ parent=left=right=0; }

  bool operator<(treeNode<T> &node)
  {
    return date < node.date;
  }
  bool operator>(treeNode<T> &node)
  {
    return date > node.date;
  }
  bool operator==(treeNode<T> &node)
  {
    return date == node.date;
  }
};
 
template<typename T>
class BinaryTree
{
private:
  treeNode<T>*  root;
  int            theSize;
  treeNode<T>*  tree_search(treeNode<T>* node,const T& key) const;
  treeNode<T>*  tree_minim(const treeNode<T>* node) const;
  treeNode<T>*  tree_maxm(const treeNode<T>* node) const;
//  void tree_insert(treeNode<T>* node,const T& key);
  void          tree_remove(treeNode<T>* node,T& key);
  void          destroy(treeNode<T>* node);
  void          print_tree_prev(treeNode<T>*)const;
  void          print_tree_in(treeNode<T>*)const;
  void          print_tree_post(treeNode<T>*)const;

public:
  BinaryTree();
  ~BinaryTree();

  int            size();
  treeNode<T>*  tree_search(T key)
  {
    return tree_search(root,key);
  }

  T& tree_minimum()
  {
    return tree_minim(root).date;
  }

  T& tree_maxmum()
  {
    return tree_maxm(root).date;
  }
  treeNode<T>* tree_sucessor(const treeNode<T>* node)const;
  treeNode<T>* tree_precessor(const treeNode<T>* node)const;
  void insert(const T& key);
  void remove(T& key);
  void makeEmpty();
  void print_tree(ORDER_MODEL model)const;
};
 
#endif /* BINARYTREE_H_ */

/*
 * BinaryTree.cpp
 */
#include <iostream>
#include <string>
//#include "BinaryTree.h"
 
using namespace std;
 
template<typename T>
BinaryTree<T>::BinaryTree():root(NULL),theSize(0){}
 
template<typename T>
BinaryTree<T>::~BinaryTree()
{
  destroy(root);
}
 
template<typename T>
void BinaryTree<T>::destroy(treeNode<T>* node)
{
  if(node != NULL)
  {
    destroy(node->left);
    destroy(node->right);
    delete node;
  }
  node = NULL;
}
 
template<typename T>
int BinaryTree<T>::size()
{
  return theSize;
}
 
template<typename T>
treeNode<T>* BinaryTree<T>::tree_search(treeNode<T>* node,const T& key)const
{
  while(node!=NULL && key != node->date)
  {
    if(key < node->date)
    {
      node = node->left;
      node = node->right;
    }
  }
  return node;
}
 
template<typename T>
treeNode<T>* BinaryTree<T>::tree_maxm(const treeNode<T>* node)const
{
  while(node->right!=NULL)
  {
    node = node->right;
  }
  return node;
}
 
template<typename T>
treeNode<T>* BinaryTree<T>::tree_minim(const treeNode<T>* node) const
{
  while(node->left!=NULL)
  {
    node = node->left;
  }
  return node;
}
 
template<typename T>
treeNode<T>* BinaryTree<T>::tree_sucessor(const treeNode<T>* node)const
{
  if(node==NULL)
  {
    return NULL;
  }
  else if(node.right!=NULL)
  {
    return tree_minim(node->right);
  }
  treeNode<T>* p = node.parent;
  while(p!=NULL && p->right = node)
  {
    node = p;
    p = p.parent;
  }
  return p;
}
 
template<typename T>
treeNode<T>* BinaryTree<T>::tree_precessor(const treeNode<T>* node)const
{
    if(node==NULL)
    {
      return NULL;
    }
    else if(node->left != NULL)
    {
      return tree_maxm(node->left);
    }
    treeNode<T>* p = node->parent;
    while(p!=NULL && p->left = node)
    {
      node = p;
      p = p->parent;
    }
    return p;
}
 
template<typename T>
void BinaryTree<T>::makeEmpty(){
    destroy(root);
}
 
template<typename T>
void BinaryTree<T>::insert(const T& key)
{
  treeNode<T>* y = NULL;
  treeNode<T>* z = new treeNode<T>((T&)key);
  treeNode<T>* node = root;
  // z->date = key;
  while(node!=NULL)
  {
    y = node;
    if(z->date < node->date)
    {
      node = node->left;
    }
    else
    {
      node = node->right;
    }
  }
  z->parent = y;
  if(y == NULL)
  {
    root = z;
  }
  else if(z->date < y->date)
  {
    y->left = z;
  }
  else
  {
    y->right = z;
  }
  theSize++;
}
 
template<typename T>
void BinaryTree<T>::remove(T& key)
{
  tree_remove(root,key);
}
 
template<typename T>
void BinaryTree<T>::tree_remove(treeNode<T>* node,T& key)
{
  treeNode<T>* z = tree_search(key);
  if(z==NULL)
    return;
  treeNode<T>* y = NULL;
  treeNode<T>* x = NULL;
  if(z->left == NULL || z->right == NULL)
  {
    y = z;
  }
  else
  {
    y = tree_sucessor(z);
  }
  if(y->left!=NULL)
  {
    x = y->left;
  }
  else
  {
    x = y->right;
  }
  if(x!=NULL)
  {
    x->parent = y->parent;
  }
  if(y->parent == NULL)
  {
    root = x;
  }
  else if(y == y->parent->left)
  {
    y->parent->left = x;
  }
  else
  {
    y->parent->right = x;
  }
  if(y!=z)
  {
    z->date = y->date;
  }
  theSize--;
}
 
template<typename T>
void BinaryTree<T>::print_tree(ORDER_MODEL model)const
{
  if(model == ORDER_MODEL_PREV)
  {
    print_tree_prev(root);
  }
  else if(model == ORDER_MODEL_IN)
  {
    print_tree_in(root);
  }
  else
  {
    print_tree_post(root);
  }
}
 
template<typename T>
void BinaryTree<T>::print_tree_in(treeNode<T>* node)const
{
  if(node!=NULL)
  {
    cout << "[";
    print_tree_in(node->left);
    cout << node->date << ",";
    print_tree_in(node->right);
    cout << "]";
  }
}
 
template<typename T>
void BinaryTree<T>::print_tree_prev(treeNode<T>* node)const
{
  if(node!=NULL)
  {
    cout << "[";
    cout << node->date << ",";
    print_tree_in(node->left);
    print_tree_in(node->right);
    cout << "]";
  }
}
 
template<typename T>
void BinaryTree<T>::print_tree_post(treeNode<T>* node)const
{
  if(node!=NULL)
  {
    cout << "[";
    print_tree_in(node->left);
    print_tree_in(node->right);
    cout << node->date << ",";
    cout << "]";
  }
}
 
int main()
{
  BinaryTree<int> bt;
  #if(0)
  cout << "ok~" << endl;
  cout << "1" << endl;
  bt.insert(5);
  bt.insert(7);
  cout << "2" << endl;
  bt.insert(9);
  cout << "ok?" << endl;
  #else
  srand(42);
  for(int i=0;i<100;i++)
    bt.insert(rand());
  #endif
  bt.print_tree(ORDER_MODEL_PREV);
  _gettch();
  return 0;
}

Good luck.
 
Share this answer
 
Posted
Comments
tiancehngbo 24-Aug-11 3:28am    
Thank you very much,it can work now,your change is "treeNode<t>* z = new treeNode<t>((T&)key);"? That's to say each time when to initialise should use "(T&)"？
mbue 24-Aug-11 7:06am    
Compiler cannot cast implicit from (const T&)key to (T&)key. Otherwise you can change the constructor parameter to const T&.
Regards.
tiancehngbo 26-Aug-11 0:46am    
I'm really appreciated your help,now I can understand why!
You are alternately using 't' and 'T'. How could this even compile? C/C++ is fully case sensitive, so always use the same case for your symbols!
 
Share this answer
 
Posted
Comments
enhzflep 23-Aug-11 12:43pm    
exactly!
tiancehngbo 24-Aug-11 3:03am    
I use the "T",but it show on the web as "t",I'm sorry,and thank you!
Stefan_Lang 24-Aug-11 4:06am    
Sounds highly unlikely to me since there are lots of occurences of either case, and sometimes even right within the same function. Looks more like sloppy typing or sloppy copy-pasting to me.

I suggest you fix it and try again.
I've just copied your code and it won't even compile!

And yes, I did remove all of the junk tags I could identify.

I suggest you make the code valid before asking for help with the functionality.
I'd also suggest that you first make the code function before trying to extend it into a template.


After you've learned how to walk, somebody can teach you to run. But certainly not the other way around.
 
Share this answer
 
Posted
Comments
tiancehngbo 24-Aug-11 3:07am    
I can compile on my computer,however,there are some mistake when I copy to web,I'm sorry,and thank you for your suggestion.
enhzflep 24-Aug-11 3:23am    
You mean to say that the case of 'T' was changed to 't' during copy to web?

Look at struct treeNode, where you appear to use T and t interchangeably. See the problem I and the poster of Answer 2 have with your assertion?
Seriously? You're trying to convince us that your computer has mysteriously changed the case of some of the occurances of the letter T?

If that is indeed the case, remove the virus and try again.

What about "but I found it can't insert elements well" - what is that even supposed to mean? It seems to my small, simple little brain that this is a long-winded version "but it's not working. Please help!"

If you would follow the convention and mention what the expected and actual result is, along with anything you've tried, you'll be far more likely to get answers conducive to solving your problem.

It's just a thought..
Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
Top Experts
Last 24hrsThis month
Related Questions
The calculation wrong
Alert for wrongly inserting password
What is wrong in this INSERTION code can someone help me to solve this problem.
argument of type "Node *" is incompatible with parameter of type "BinarySearchTree *"
What is wrong with this code
Something is wrong with my Python code
Data inserted in MYSQL even if it is in wrong format
Insert query not inserting records via javascript procedure in snowflake
what is wrong in this
Clearing of inserted data after submit the form

Advertise
Privacy
Cookies
Terms of Use
Last Updated 24 Aug 2011
Layout: fixed | fluid
Copyright © CodeProject, 1999-2024
All Rights Reserved.

Web03 2.8:2024-04-02:1

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900