问题描述

指针或数组越界实在找不到问题了

http://wenku.baidu.com/link?url=e_SMeDv5empBQO07OE4vnfFpYDsc_nZ61H-j6OoSTbwN8J24IgKdxnTHnHk51sKnRx0IbujnnQepn-Ml5_l6n3XJGomwgwt6zxoIdF2E32i

实验五，要交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);
            }
        }
    }
}