Stuck on BST. Adding multiple elements into nodes

Hello Evereyone,

I was wondering if someone could explain me how to add multiple elements into one node. I got the idea but it doesn't work.

Here's what I'm trying to accomplish. Let's say I got some text in couple lines. I have to create a searchable index so the user can type a word and program will find in which text line that word exist. I got no problem breaking text into word and assigning it into BST tree. Please see the code below, I know it's long and it could be simpler but I'm totally newbie. Please be gentle with me :)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#include <iostream>
#include <cstdlib>
#include <string>
#include <string.h>
#include <stdio.h>
#include <fstream>
#include <sstream>


using namespace std;

struct Index {
    string word;
    Index *left;
    Index *right;
    int *line; //will refer to dynamic array. not sure if it's correct
    };

void AddNode (Index *&node, string temp_word)
{
    if (node == NULL)
    {
        node=new Index;
        node->word = temp_word;
        node->left = NULL;
        node->right = NULL;
    }
    else if (temp_word < node->word)
    {
        AddNode(node->left,temp_word);
    }
    else if (temp_word > node->word)
    {
        AddNode(node->right,temp_word);
    }
};

void Print(Index *node)
{
    if(node!=NULL)
    {
        Print(node->left);
        cout << node->word << endl;
        Print(node->right);
    }
};

Index* Search(Index* node, string search_word)
{
    if(!node)
    {
        cout << endl << "Word not found" << endl;
        return 0;
    }

    if(search_word == node->word)
    {
        cout << endl << "Word found.. ";
        return node;
    }

    if(search_word < node->word)
    {
        //cout << "Lewy" << endl;
        return Search(node->left, search_word);
    }
    else
    {
        //cout << "Prawy" << endl;
        return Search(node->right, search_word);
    }
};

void Delete(Index *node)
{
    Index *temp;
    if (node!=NULL)
    {
        Delete(node->left);
        Delete(node->right);
        temp=node;
        node=NULL;
        delete temp;
    }
}


int main(int argc, char* argv[])
{
    int n = 0;
    int position = 1;
    string line;
    ifstream text;
    text.open("tekst.txt");

//counting number of lines in text. n used later to create
//dynamic array
    if(text)
    {
        stringstream word;
        while (getline(text,line))
        {
            n++;
        }
    }

    int *Position;
    Position = new int[n];

    Index *root;
    root=NULL;

    text.close();
    text.open("tekst.txt");

//testing if file exist
    if(!text)
    {
        cout << "File not found" << endl;
        return 1;
    }

//converting text to word and entering them into tree
    if(text)
    {
        stringstream word;
        while (getline(text,line))
        {
            word << line;
            while (getline(word,line,' '))
            {
                cout << "Found in " << position << " - ";
                cout << line << endl;
                AddNode(root,line);
            }
            Position[position-1]=position;
            position++;
            word.clear();
        }
    }

//assigning line numbers to array table
    for (int i=0 ; i<n ; i++)
    {
        cout << Position[i];
    };

//how to add Position[i] to node, for example word "ANYTHING" exists in lines 3,4,7,8


    string search_word;
    string temp1;
    string temp2;
    cout << endl << "Enter word: " << endl;
    cin >> search_word;



    Search(root,search_word);


//deleting tree
    Delete(root);

    text.close();

    system("PAUSE");
    return 0;
}


I started that code already couple of time. Not sure if I'm thinking logically anymore :)
Last edited on
this code is a little over my head but why is line 100 stringstream word declared but never used. are you missing a line in that loop
Actually no, BST is being built properly, same words are being omitted and the array Position[n] have all the lines.

My problem is that I want to add multiple positions to a tree nodes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
struct Index {
    string word;
    Index *left;
    Index *right;
    int *line; //will refer to dynamic array. not sure if it's correct
    };

void AddNode (Index *&node, string temp_word)
{
    if (node == NULL)
    {
        node=new Index;
        node->word = temp_word;
        node->line = *position //not sure if I can do that. Anyway it doens't work
        node->left = NULL;
        node->right = NULL;
    }
    else if (temp_word < node->word)
    {
        AddNode(node->left,temp_word);
        AddNode(node->line,*position); //does this line even make sense :(
    }
    else if (temp_word > node->word)
    {
        AddNode(node->right,temp_word);
        AddNode(node->line,*position); //same thing over here
    }
};


I'm not sure if this is the correct way to assing element to node.
AddNode needs to take the current line number, and create/update the Index.lines array. I don't understand what your Position array is for, but it doesn't look necessary.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
struct Index {
    string word;
    Index *left;
    Index *right;
    int line; //so I should just create regular int to hold the number??
    };

void AddNode (Index *&node, string temp_word,int line=0)
{
    if (node == NULL)
    {
        node=new Index;
        node->word = temp_word;
        Index.line = position; //or it should be node.line = position??
        node->left = NULL;
        node->right = NULL;
    }
    else if (temp_word < node->word)
    {
        AddNode(node->left,temp_word);
        Index.line = position; //is that correct?
    }
    else if (temp_word > node->word)
    {
        AddNode(node->right,temp_word);
        Index.line = position; //same thing over here
    }
};


For some stupid reason I decided to create that array to hold all the lines but I don't reallt need it. Is the syntax correct on assigning current line to Index.line?

BTW Thank you for your help, I really appreciate it.

Interesting how I can find million websites about simple trees, but a not single one with related to my problem. :)
By Index.line I meant the member of Index called line. This is not correct syntax in your function though.

Each word can appear on multiple lines, so each node needs its own array (or vector if you're familiar with them), a single integer won't work.

Where has your variable position come from?
I'm going thru a text again in here.

1
2
3
4
5
6
7
int main(int argc, char* argv[])
{
    int n = 0;
    int position = 1;//first line assigned to position
    string line;
    ifstream text;
    text.open("tekst.txt");


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//converting text to word and entering them into tree
    if(text)
    {
        stringstream word;
        while (getline(text,line))
        {
            word << line;
            while (getline(word,line,' '))
            {
                //cout << "Found in " << position << " - ";
                //cout << line << endl;
                AddNode(root,line);
            }
            Position[position-1]=position; //Position is increased with each line being read
            position++;//and here
            word.clear();
        }
    }

//assigning line numbers to array table
    for (int i=0 ; i<n ; i++)
    {
        cout << Position[i];
    };
Where has your variable position come from?


Do you understand scope? variables declared in main() can not be seen in AddNode().
Yes. I just changed functions. So I took your advice and made a following changes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
struct Index {
    string word;
    Index *left;
    Index *right;
    int line;  //here
    };

void AddNode (Index *&node, string temp_word, int position=0) /here
{
    if (node == NULL)
    {
        node=new Index;
        node->word = temp_word;
        node->line = position;  //here
        node->left = NULL;
        node->right = NULL;
    }
    else if (temp_word < node->word)
    {
        AddNode(node->left,temp_word,position); //here
    }
    else if (temp_word > node->word)
    {
        AddNode(node->right,temp_word,position); //here
    }
};

void Print(Index *node)
{
    if(node!=NULL)
    {
        Print(node->left);
        cout << node->word << " ";
        cout << node->line << endl; //here
        Print(node->right);
    }
};


So now I'm getting word with the first line, that word appeared. Now I have to modify code to store mulitple numbers, mostlikely using vectors, 'cause I'm not really strong in linked lists. OMG I sat on that code for a whole week. Finally see light in the tunnel :)

One more questions when I make change

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct Index {
    string word;
    Index *left;
    Index *right;
    vector<int> line; //does it look ok.
    };

void AddNode (Index *&node, string temp_word, vector<int> position=0) /I'm getting error in here : "no match for 'operator<<' in 'std::cout << node->Index::line'
{
    if (node == NULL)
    {
        node=new Index;
        node->word = temp_word;
        node->line = position;
        node->left = NULL;
        node->right = NULL;
    }
    else if (temp_word < node->word)
    {
        AddNode(node->left,temp_word,position);
    }
    else if (temp_word > node->word)
    {
        AddNode(node->right,temp_word,position);
    }
}; 


So is it because I have to use loop for to insert lines in vector.

Thank you so much for you help.
Last edited on
Topic archived. No new replies allowed.