2

文字列を収集してポスト順に並べるバイナリ検索ツリーを使用しています。文字列が表示される行番号を示すリストも使用します。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

よろしくお願いします！

4

2 に答える 2

1

わかった。私はしばらく見つめました。これの私自身のバージョンも書きましたが、最終的にはこれがあなたがすべきことだと思います：

まず、次のように変更treeInsert()します。

void treeInsert(TreeNode *&root, const string& newItem,int num)
{
    if (root == NULL )
    {
        root = new TreeNode(newItem, list<int>(1, num));
        return;
    }

    if (newItem < root->data )
    {
        treeInsert( root->left, newItem, num );
    }
    else if (root->data < newItem)
    {
        treeInsert( root->right, newItem, num );
    }

    else
    {   // found the item. just add it to the node's list
        //  if it isn't already there.
        if (find(root->lineNum.begin(), root->lineNum.end(), num) == root->lineNum.end())
            root->lineNum.push_back(num);
    }
}

なんで？: これは事実上、最初にノードが NULL かどうかを確認します。そうである場合は、新しいノードを作成する必要があります。これは、現在の行番号という 1 つの項目の新しいリストです。ルートがNULL でない場合、3 つのオプションがあります。

  1. 単語がルート単語よりも「少ない」場合は、左のツリーを下に移動します。
  2. それ以外の場合、単語がルート単語よりも「大きい」場合は、右のツリーを下に移動します
  3. それ以外の場合は、それより小さくも大きくもないため、等しい必要があるため、現在の行番号を行リストで検索し、存在しない場合は追加します。

これだけで多くの問題が解決します。1つは、メイン関数に対する他の変更を減らします（そして、はるかに簡単になります）：

int main(int argc, char *argv[])
{
    TreeNode *root = NULL;

    ifstream test("test.txt");
    string line;
    int currentLine=0;

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

        istringstream strLine(line);
        string word;
        while (strLine >> word)
        {
            treeInsert(root, word, currentLine);
            cout << "\nContents of tree:\n";
            printTree(root);
        }
    }
    return 0;
}

最後に、これにより、必要のない次の関数を捨てることができます。

void insert(TreeNode *&root, string newNode,list<int> num);
bool treeContains( TreeNode *root, string item );
TreeNode search(TreeNode *root, string item);

私が指摘した変更により、あなたが期待していると思う出力は次のとおりです。

Contents of tree:
hello 1

Contents of tree:
hello 1
wonderful 1

Contents of tree:
hello 1
wonderful 1
world 1

Contents of tree:
hello 1
welcome 2
wonderful 1
world 1

Contents of tree:
hello 1
to 2
welcome 2
wonderful 1
world 1

Contents of tree:
hello 1
paradise 2
to 2
welcome 2
wonderful 1
world 1

Contents of tree:
hawaii 3
hello 1
paradise 2
to 2
welcome 2
wonderful 1
world 1

Contents of tree:
hawaii 3
hello 1
is 3
paradise 2
to 2
welcome 2
wonderful 1
world 1

Contents of tree:
hawaii 3
hello 1
is 3
paradise 2
to 2
welcome 2
wonderful 1 3
world 1

これが役立つことを願っています。

于 2013-03-11T10:06:33.407 に答える
1

私はあなたのコードを見て、それを単純化しました。結果を貼ります。バグが消えました:)

あなたの問題は、ほとんどの場合、同じことを 2 回行っていたことです。「検索」機能と「挿入」機能の両方で、ツリー内のノードを見つけていました。2 つの実装には、バグにつながる微妙な違いがありました。

また、自由に関数呼び出しをメソッド呼び出しに移動しました。

#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();
}
于 2013-03-11T10:01:09.637 に答える