实验五，要交OJ，OJ上题目略有不同。
输入有以下四种情况：
当输入大写英文字母'T'时，表示下一行是文本内容，包含若干英文单词、标点符号以及阿拉伯数字，用于构建二叉查找树。文本内容以字符‘@’结束，文本中的每个英文单词的长度不超过30个字母。
当输入大写英文字母'S'时，表示后面跟着的若干行都是停用词，每个停用词占一行，当某行是字符‘#’时，表示停用词输入完毕。对每个停用词，都需要删除二叉查找树中的相应结点，即：每输入一个停用词，执行一次删除结点的操作。
当输入大写英文字母'V'时，表示中序遍历二叉查找树。遍历结果中的每个单词占一行，先输出该单词，然后输出一个空格，再输出该单词出现的次数。
当输入大写英文字母'Q'时，表示后面跟着的若干行都是查询词，每个查询词占一行，当某行是字符‘#’时，表示查询词输入完毕。对每个查询词，都需要在二叉查找树中的搜索相应结点，如果找到，则输出该单词及其出现次数，如果未找到，则输出-1。每个查询词的查询结果占一行，先输出该单词，然后输出一个空格，再输出该单词出现的次数。
当输入大写英文字母'X'时，表示输入结束。
runtime error
找了一上午了找不到错误...
代码如下
#include<iostream>
#include<string>
using namespace std;
class Node{
string key;
int count;
Node *leftChild;
Node *rightChild;
public:
Node(string str){
key = str;
count = 1;
leftChild = NULL;
rightChild = NULL;
}
friend class BinarySearchTree;
};
class BinarySearchTree{
Node *root;
public:
BinarySearchTree(){ root = NULL; };
~BinarySearchTree(){};
Node *Search(string str,Node *&,int);//查找
void InOrder( Node*);//中序遍历
void Insert(string &, Node *&,BinarySearchTree &);//插入一个元素
void Delete(string &, Node*&);//删除一个元素
Node *GetRoot();//获得根节点
};
void BinarySearchTree::Insert(string &str, Node *&r,BinarySearchTree &BSTree){
if (!root){
root = new Node(str);
}
else{
Node *p,*parent;
p = BSTree.Search(str, r, 1);
if (p)
p->count++;
else{
p = new Node(str);
parent = BSTree.Search(str,r,2);
if (str<parent->key)
parent->leftChild = p;
else
parent->rightChild = p;
}
}
}
Node *BinarySearchTree::Search(string str, Node*&r,int tag){
if (!root){
if (tag == 0)
cout << -1 << endl;
return root;
}
else{
Node *p = r,*parent=NULL;
while (p){
if (str == p->key){
if (tag == 0){
cout << p->key << " " << p->count << endl;
return p;
}
else if (tag == 1)
return p;
else
return parent;
}
else{
if (str < p->key){
parent = p;
p = p->leftChild;
}
else{
parent = p;
p = p->rightChild;
}
}
}
if (tag == 0){
cout << -1 << endl;
return p;
}
else if (tag == 1)
return p;
else
return parent;
}
}
void BinarySearchTree::InOrder(Node *r){
if (r){
InOrder(r->leftChild);
cout << r->key << " " << r->count << endl;
InOrder(r->rightChild);
}
}
void BinarySearchTree::Delete(string &str, Node*&r){
if (r){
Node *p = Search(str, r, 1),*parent=Search(str,r,2),*del;
if (p){
if (!p->leftChild){
if (!parent){
r = p->rightChild;
del = p;
delete del;
}
else if (parent->leftChild == p){
parent->leftChild = p->rightChild;
del = p;
delete del;
}
else if(parent->rightChild==p){
parent->rightChild = p->rightChild;
del = p;
delete del;
}
}
else if (!p->rightChild){
if (!parent){
r = p->leftChild;
del = p;
delete del;
}
else if (parent->leftChild == p){
parent->leftChild = p->leftChild;
del = p;
delete del;
}
else if (parent->rightChild == p){
parent->rightChild = p->leftChild;
del = p;
delete del;
}
}
else{
Node *rr = p, *r = p->leftChild;
while (r->rightChild){
rr = r;
r = r->rightChild;
}
p->key = r->key;
rr->rightChild = r->leftChild;
del = r;
delete del;
}
}
}
}
Node *BinarySearchTree::GetRoot(){
return root;
}
int main(){
char ch;
string str1, str2;
BinarySearchTree BSTree;
while (cin >> ch&&ch != 'X'){
if (ch == 'T'){
Node *r1;
while (cin >> str1&&str1 != "@"){
//判断选择str
str2 = str1;
int j;
unsigned int i;
for (i = j = 0; i< str1.size(); i++){
if (str1[i] >= 'a'&&str1[i] <= 'z'){
str2[j] = str1[i];
j++;
}
else if (str1[i] >= 'A'&&str1[i] <= 'Z'){
str2[j] = str1[i] + 32;
j++;
}
}
str2 = str2.substr(0,j);
r1 = BSTree.GetRoot();
if (str2.size())
BSTree.Insert(str2, r1,BSTree);
}
}
else if (ch == 'S'){
Node *r2;
while (cin >> str1&&str1 != "#"){
r2 = BSTree.GetRoot();
BSTree.Delete(str1, r2);
}
}
else if (ch == 'V'){
BSTree.InOrder(BSTree.GetRoot());
}
else if (ch == 'Q'){
Node *p, *r3;
while (cin >> str1&&str1 != "#"){
p = NULL, r3 = BSTree.GetRoot();
BSTree.Search(str1, r3, 0);
}
}
}
}
