C++二进制查找树比较节点数据并去重

Question

我已经在c++中创建了一个二进制搜索树，并在其中加载了两种类型的数据:字符串和整数。我正在读取一个文本文件，并按字母顺序加载树，其中包含我正在提取的单词，以及该单词所在的行号。我可以很好地打印出单词和数字。我现在要做的是检查一个单词是否已经打印，如果已经打印，我将只打印出找到该单词的行号。我考虑这样做的方法是在遍历和打印树时比较以前的数据。这是我的打印函数。

void inOrderPrint(Node *rootPtr ) {
    if ( rootPtr != NULL ) {
        for (int i =0; rootPtr->data[i]; i++){
            while(ispunct(rootPtr->data[i]))
                rootPtr->data.erase(i,1);
                }
        rootPtr->data = rootPtr->data.substr(0,10);
        inOrderPrint( rootPtr->left );
        cout << (rootPtr->data)<<rootPtr->lineNum <<endl;
        inOrderPrint( rootPtr->right );
    }
}

我是这么想的：

if (rootPtr->data == previous rootPtr->data)
    cout<<setw(10)<<theCurrentNode lineNum;
else
    do normal printing

我认为，如果此函数在第一个节点上运行，并将其与不存在的前一个节点进行比较，它将自动尝试将其与NULL进行比较，if语句将返回false，然后它将转移到else。

对于如何使用实际的c++语法来实现这一点，有什么建议吗？或者有人看到我逻辑上的缺陷了吗？

提前感谢！

Answer 1

这个答案将描述如何让程序打印唯一的条目和文件中第一次出现的行号。如果有重复的出现，它将只打印每个重复出现的第一个出现的行号。方法是确保树中没有重复的节点，并计算冗余出现的次数。

为此，我们可能会修改节点结构，如下所示：

struct Node{
    string data;
    int lineNum;
    int count =1;
    Node* left;
    Node* right;
};

可以对函数Insert进行编辑，以计算重复项，如下所示：

Node* Insert(Node* rootPtr,string data,int lineNum){
if(rootPtr == NULL){
    rootPtr = GetNewNode(data,lineNum);
    for (int i =0; rootPtr->data[i]; i++){
        while(ispunct(rootPtr->data[i]))
            rootPtr->data.erase(i,1);
            }
    rootPtr->data = rootPtr->data.substr(0,10);

    return rootPtr;
}
else if(data< rootPtr->data){
    rootPtr->left = Insert(rootPtr->left,data,lineNum);
    for (int i =0; rootPtr->data[i]; i++){
        while(ispunct(rootPtr->data[i]))
            rootPtr->data.erase(i,1);
            }
    rootPtr->data = rootPtr->data.substr(0,10);
}
else if(data > rootPtr->data) {
    rootPtr->right = Insert(rootPtr->right,data,lineNum);
    for (int i =0; rootPtr->data[i]; i++){
        while(ispunct(rootPtr->data[i]))
            rootPtr->data.erase(i,1);
            }
    rootPtr->data = rootPtr->data.substr(0,10);

}
else if(data == rootPtr->data)
    ++rootPtr->count;

return rootPtr;
}

最后，可以修改打印函数：

void inOrderPrint(Node *rootPtr ) {
//ofstream outputFile;
//outputFile.open("Output.txt");

if ( rootPtr != NULL ) {
    inOrderPrint( rootPtr->left );
    cout << (rootPtr->data)<<" " << rootPtr->lineNum <<endl;
    int j =rootPtr->count;
    while( --j )
    cout << rootPtr->lineNum <<endl;

    //outputFile << (rootPtr->data)<<rootPtr->lineNum <<endl;
    inOrderPrint( rootPtr->right );
}
}

现在这应该更接近你想要的了。将文本处理与节点处理分开也是一个好主意。(此答案在某种程度上假设您会处理这些问题。)否则，如果预处理后的文本与处理后的文本不匹配，则会创建重复的节点。

祝好运!