以下代码分为一个头文件和一个.cpp文件,可复制粘贴直接运行,头文件记得命名为BST.h
我的运行环境是vs2017,编译没有出错,插入函数也是照书中代码一点点打的,保证没有抄错。但是无法正常插入,麻烦大佬们花两分钟帮忙看看,是不是代码的错,在下C++才学一年,希望能大家能多指教,非常感谢!
代码出自《数据结构与算法分析 C++语言描述 第2版》Larry Nyhoff著 清华大学出版社 第600页
/*
头文件名字如下:
BST.h
这是一个二叉查找树模板类,我只定义了元素插入二叉树的函数
代码出自《数据结构与算法分析 C++语言描述 第2版》Larry Nyhoff著 第600页
保证没有抄错,大佬们可以直接复制粘贴到编译器中执行
后面有测试的test.cpp文件,也可以直接复制粘贴
*/
#include <iostream>
#include <new>//我不知道该头文件的用处,书上是这么写的
using namespace std;
#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H
template <typename DataType>
class BinarySearchTree {
private:
/*节点类*/
class BinNode {
public:
DataType data;
BinNode * left;
BinNode * right;
BinNode() :left(0),right(0){}
BinNode(DataType item) :data(item), left(0), right(0) {}
};//节点类声明结束
typedef BinNode * BinNodePointer;//用BinNodePointe来代替BinNode *
//类成员
BinNode * myRoot;
public:
BinarySearchTree();//构造
void insert(const DataType & item)const;//插入
private:
void insertAux(BinNodePointer subtreeRoot, const DataType & item)const;//插入辅助函数
};//模板类声明结束
//以下是函数定义
//构造
template <typename DataType>
inline BinarySearchTree<DataType>::BinarySearchTree():myRoot(0){}
//插入
template<typename DataType>
inline void BinarySearchTree<DataType>::insert(const DataType & item) const {
insertAux(myRoot, item);
}
//插入辅助函数定义,用了递归
template<typename DataType>
void BinarySearchTree<DataType>::insertAux(
BinarySearchTree<DataType>::BinNodePointer subtreeRoot,
const DataType & item) const {
if (subtreeRoot == 0){
subtreeRoot = new BinarySearchTree<DataType>::BinNode(item);
cout<<"xxx\n";//之后用for循环测试是否插入成功,如果成功只显示一次,失败显示n次。
}
else if (item < subtreeRoot->data)//左子树
insertAux(subtreeRoot->left, item);
else if (subtreeRoot->data)//右子树
insertAux(subtreeRoot->right, item);
else
cerr << "Item already in the tree\n";
}
#endif
下面是测试用的main函数
#include <iostream>
#include "BST.h"
using namespace std;
int main() {
BinarySearchTree<int> bst;
//测试插入函数
int number;
for (number=0;;) {
number++;
if (number == 999)break;
bst.insert(number);
}//如果一直是空树的话会不断的输出"xxx"
return 0;
}