本文介绍了C ++ BinarySearchTree与插入错误的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
您好，我在c ++中实现了BinarySearchTree，但是我发现它不能很好地插入元素，有人可以解决此问题吗?谢谢！以下是我的代码.
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.
/*
* 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_ */
/*
* 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;
}推荐答案
/*
* 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>
//<span class="code-preprocessor">#include "BinaryTree.h"</span>
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.
这篇关于C ++ BinarySearchTree与插入错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！