<分区>
我发布了 a similar question昨天，当我的双参数二叉搜索树不断崩溃时。
我已经设法让它接受整数作为参数，但是，我真正需要做的是使用字符串作为参数，但每次这样做时我仍然会崩溃。
我将包含插入函数的代码以及我的节点类。
void insert (K k, V v) {
TreeNode<K,V> * treeNode = new TreeNode<K,V> (k,v);
TreeNode<K,V> *temp=NULL;
TreeNode<K,V> *prev=NULL;
temp = root;
while(temp) { // crashes in this loop, even if I remove loop and have it only activate once
prev = temp;
if (temp->key < treeNode->key) //MARKER
temp = temp->right; //MARKER
else
temp = temp->left;
}
if (prev==NULL)
root = treeNode;
else {
if (prev->key<treeNode->key)
prev->right = treeNode;
else
prev->left = treeNode;
}
}
和节点类:
template <class K, class V> class TreeNode {
public:
TreeNode(K k, V v): key(k), value(v), left(0), right(0) {}
K key;
V value;
TreeNode<K,V> *left;
TreeNode<K,V> *right;
template <class X, class Y> friend std::ostream & operator
<< (std::ostream &s,const TreeNode<X,Y> &t);
};
谁能看出我这里做错了什么？
作为建议:完整代码的缩减版本。
/* bst.h */
#ifndef __CSC116__BST_H__
#define __CSC116__BST_H__
#include <list>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
using namespace std;
unsigned int heightCount;
template <class K, class V> class TreeNode
{
public:
TreeNode(K k, V v): key(k), value(v), left(0), right(0) {}
K key;
V value;
TreeNode<K,V> *left;
TreeNode<K,V> *right;
template <class X, class Y> friend std::ostream & operator<< (std::ostream &s,
const TreeNode<X,Y> &t);
};
// TreeNodes can output themselves to streams
template <class K, class V> std::ostream & operator << (std::ostream &s, const TreeNode<K,V> &n)
{
s << "\"" << n.key << ":" << n.value << "\"";
return s;
}
class key_not_found_exception { //Currently inactive
};
template <class K, class V> class BinarySearchTree {
public:
//
// Constructor
//
BinarySearchTree ()
{
sizeCount = 0;
}
~BinarySearchTree()
{
}
void insert (K k, V v) {
TreeNode<K,V> * treeNode = new TreeNode<K,V> (k,v);
TreeNode<K,V> *temp=NULL;
TreeNode<K,V> *prev=NULL;
temp = root;
while(temp) { // crashes in this loop, even if I remove loop and have it only activate once
prev = temp;
if (temp->key < treeNode->key)
temp = temp->right;
else
temp = temp->left;
}
if (prev==NULL)
root = treeNode;
else {
if (prev->key<treeNode->key)
prev->right = treeNode;
else
prev->left = treeNode;
}
}
bool isEmpty() const
{
return root == NULL;
}
unsigned int size()
{
cout << sizeCount; //Currently inactive
return 0;
}
private:
unsigned int doHeight (TreeNode<K,V> *t) //Currently inactive
{
return -1;
}
void doDelete (TreeNode<K,V> * n )
{
}
TreeNode<K,V> *root;
unsigned int count;
unsigned int sizeCount;
template <class X, class Y> friend class tree_view;
template <class X, class Y> friend std::ostream & operator << (std::ostream &s, const
BinarySearchTree<X,Y> &t);
};
template <class K,class V> void do_inorder (std::ostream &s, const TreeNode<K,V> *n)
{
if (!n)
return;
do_inorder(s,n->left);
s << n->key << ":" << n->value << " ";
do_inorder(s,n->right);
}
// Output the tree to a stream by doing an in-order traversal
template <class K, class V> std::ostream & operator << (std::ostream &s, const
BinarySearchTree<K,V> &t)
{
s << "{ ";
do_inorder(s,t.root);
s << "}";
return s;
}
#endif
/bst_tester.cpp/
// bst_tester.cpp
#include <iostream>
#include <string>
#include <sstream>
#include "bst.h"
#include "tree_view.h"
using namespace std;
class bst_tester_exception
{
public:
bst_tester_exception (const string & msg, unsigned int line) : _msg(msg), _line(line) {}
string what() const
{
ostringstream s;
s << _line;
return _msg + " line number: " + s.str();
}
private:
bst_tester_exception();
string _msg;
unsigned int _line;
};
void test_insert_size_height()
{
BinarySearchTree<string,string> t;
if (t.height() != 0)
throw bst_tester_exception(__func__,__LINE__);
if (t.size() != 0 )
throw bst_tester_exception(__func__,__LINE__);
t.insert("bob", "bobdata");
t.insert("abe", "abedata");
t.insert("jane", "janedata");
if (t.height() != 2)
throw bst_tester_exception(__func__,__LINE__);
if (t.size() != 3 )
throw bst_tester_exception(__func__,__LINE__);
}
int main ()
{
unsigned int tests_passed = 0;
try
{
test_insert_size_height();
tests_passed++;
}
catch (bst_tester_exception &e)
{
cout << "Failed test case: " << e.what() << std::endl;
}
catch (...)
{
cout << "Caught unhandled exception." << std::endl;
}
cout << "Passed: " << tests_passed << endl;
return tests_passed;
}