c++ - 搜索二叉搜索树后输出错误

Question

我正在使用二叉搜索树来收集字符串，然后按后序对它们进行排序。我还使用一个列表来显示字符串出现的行号。我可以使 BST 正常工作，但最终我的输出出现错误。我认为当我遇到一个重复的词时就会出现问题。当我向重复的单词添加行号时，我的输出搞砸了。

我的输出应该是这样的

hawaii    3

hello     1

is        3

paradise  2

to        2

welcome   2

wonderful 1 3

world    1

但是我得到这个作为输出

Contents of tree:

hello 1

Contents of tree:

hello 1
wonderful 1
.
.
.

Contents of tree:

hawaii 3
hello 1
is 3
paradise 2
to 2
welcome 2
wonderful 1
world 1

Contents of tree:

is 3
paradise 2
to 2
welcome 2
wonderful 1 3
world 1
Press any key to continue . . .

这里是主要逻辑

struct TreeNode
{
    string data;
    list<int> lineNum;
    TreeNode *left;
    TreeNode *right;


    TreeNode(string str,list<int> num)
    {
        data = str;
        lineNum = num;
        left = NULL;
        right = NULL;
    }
};

void insert(TreeNode *&root, string newNode,list<int> num)
{
    if(root == NULL)
    {
        root = new TreeNode(newNode,num);
    }
    else if(newNode < root -> data)
    {
        insert(root -> left, newNode,num);
    }
    else
    {
        insert(root -> right, newNode,num);
    }
}

bool treeContains( TreeNode *root, string item )
{

    if ( root == NULL )
    {
        return false;
    }
    else if ( item == root->data)
    {
        return true;
    }
    else if ( item < root->data )
    {
        return treeContains( root->left, item );
    }
    else
    {
        return treeContains( root->right, item );
    }
}

void treeInsert(TreeNode *&root, string newItem,int num)
{
    list<int> temp;
    temp.push_back(num);
    if ( root == NULL ) 
    {
        root = new TreeNode(newItem,temp );
        return;
    }
    else if ( newItem < root->data ) 
    {
        treeInsert( root->left, newItem,num );
    }
    else 
    {
        treeInsert( root->right, newItem,num );
    }
}

void printTree(TreeNode *node)
{
    list<int>::iterator i;

    if ( node != NULL )
    {
        printTree(node->left);
        cout <<node->data;
        for( i = node->lineNum.begin(); i != node ->lineNum.end(); ++i)
            cout<<" "<<*i;

        cout << endl;

        printTree(node->right);
    }
}

TreeNode search(TreeNode *root, string item)
{
    while ( root != NULL )
    {
        if(item == root->data)
        {
            break;
        }

        if ( item > root->data )
        {
            root = root-> right;
        }
        else if(item < root->data )
        {
            root = root-> left;
        }

        if(root == NULL)
        {
            cout << "error";
        }

    }
    return *root;
}

int main()
{
    TreeNode *root;
    root = NULL;
    ifstream test("test.txt");
    istringstream strLine;
    string line, word;
    list<int> lineNum;

    int currentLine=0;

    // Go line by line
    while (getline(test,line))
    {
        ++currentLine;

        strLine.clear();
        strLine.str(line);

        lineNum.push_back(currentLine);
        // Now from the line read word by word
        while (strLine >> word)
        {

            // if word is already in tree search tree for node and line number
            if (treeContains(root,word))
            {
                *root = search(root,word);
                root->lineNum.push_back(currentLine);
                cout << "\nContents of tree:\n\n";
                printTree(root);

            }
            // if word is new add to tree insert node
            else
            {
                treeInsert(root,word,currentLine);  
                cout << "\nContents of tree:\n\n";
                printTree(root);
            }
        }
    }
}

输入文本如下所示:

hello wonderful world
welcome to paradise
hawaii is wonderful

先谢谢大家了!

Answer 1

我查看了您的代码并对其进行了简化。我正在粘贴结果。错误消失了:)

你的问题主要是你做了两次同样的事情——你在“搜索”和“插入”函数中都在树中找到了一个节点。这两种实现方式存在细微差别，导致了您的错误。

我还冒昧地将您的函数调用移动到方法调用。

#include <list>
#include <string>
#include <iostream>
#include <fstream>
#include <sstream>
using namespace std;

struct TreeNode {
        string data;
        list<int> lineNum;
        TreeNode *left;
        TreeNode *right;

    public:
        TreeNode(string str, int num) {
            data = str;
            lineNum.push_back(num);
            left = NULL;
            right = NULL;
        }


        void print() const {
            if (this->left != NULL) {
                this->left->print();
            }

            this->printNode();

            if (this->right != NULL) {
                this->right->print();
            }
        }

        static void insert(TreeNode *&root, string newNode, int num) {
            if (root == NULL) {
                root = new TreeNode(newNode, num);
            } else if (newNode < root->data) {
                TreeNode::insert(root->left, newNode, num);
            } else if (newNode > root->data) {
                TreeNode::insert(root->right, newNode, num);
            } else {
                root->lineNum.push_back(num);
            }
        }

    private:
        void printNode() const {
            list<int>::const_iterator i;
            cout<<this->data;

            for (i = this->lineNum.begin(); i != this->lineNum.end(); ++i) {
                cout<<" "<<*i;
            }

            cout << endl;
        }
};


int main()
{
    TreeNode *root;
    root = NULL;
    ifstream test("test.txt");
    istringstream strLine;
    string line, word;
    int currentLine=0;

    // Go line by line
    while (getline(test,line)) {
        ++currentLine;
        strLine.clear();
        strLine.str(line);

        // Now from the line read word by word
        while (strLine >> word) {
            TreeNode::insert(root,word,currentLine);
        }
    }

    cout << "\nContents of tree:\n\n";
    root->print();
}