C++

Forum

 
Find word in binary tree

Bram van Velzen (7)
I've got the following code.

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
 
branch* branch::find(string word)
{
	if (word.compare(_word) == 0)
		return this;


	else
	{
		if (_left != 0 && _right != 0)
		{

			if (word.compare(_word) < 0)
			{
				if (_left != 0)
				{
					_left->find(word);
				}
			}

			if (_right != 0)
			{
				if (word.compare(_word) > 0)
				{
					if (_right != 0)
					{
						_right->find(word);
					}
				}
			}



			if (word.compare(_word) == 0)
				return this;
			else
				return 0;
		}


		else if (_right == 0 && _left != 0)
		{
			_left->find(word);
		}



		else if (_left == 0 && _right != 0)
		{
			_right->find(word);
		}


		else
			if (word.compare(_word) == 0)
				return this;
			else
				return 0;
	}
}


My goal for this function is to return "this" (and only "this") if the word which the user searches for is being found and to return 0 if the word which the user searches for is not being found.
_word is the root of the binary tree, _left en _right are pointers from the root.
I attempt to search the tree by comparing the strings (the word the user searches for and the word that is being referred to by one of the three pointers) compare. That way you know how to travel through the tree.


My problem: once the word has been found and "this" has been returned the program finishes the other instances that are on the stack (hopefully I phrase this correctly) and it ends with returning 0 unless it happens to be that the first word in the tree (_word) happens to be the word that is being searched (becausee in that case noting else is on the stack thus "this" is the last value which is being returned).

Question: how do I make sure that once I return "this" there will not be returned a 0 and that if the last string-comparison never equals 0 a 0 will be returned?
I want to do this whith returning a pointer to another class of the program, not whithin a single file (I know how to do that).

There is also still some flawed logic in it. Loading a new instance of this function with the first _right -> find(word); doesn't seem to work.
Last edited on
helios (17574)
When you recurse into a child's find() you should simply return that call's return value.
Bram van Velzen (7)
It didn't cross my mind that you can return that way.

Good news for me: I seem to have functioning code. I tested out all the positions in the tree (on top, on the bottom, only a left child and only a right child) and I tested out non existing words, in all cases I get the correct outcome.

Bad news: my gutfeeling tells me that I could write this down in a more elegant (shorter number of lines) way. I appreciate constructive criticism in that regard. ;)
This is my current code:
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
 
branch* branch::find(string word)
{
	if (word.compare(_word) == 0)
		return this;

	else
		if (_left != 0 && _right != 0)
		{
			if (word.compare(_word) < 0)
			{
				return _left->find(word);
			}
			else if (word.compare(_word) > 0)
			{
				return _right->find(word);
			}
			else
			{
				if (word.compare(_word) == 0)
					return this;
			}
		}

	if (_left && !_right)
		return _left->find(word);

	if (!_left && _right)
		return _right->find(word);

	if (!_left && !_right)
		return NULL;

}


Last edited on
helios (17574)
You don't need to have an else if the true branch of the if returns along all code paths. In other words,
1
2
3
4
5
 
if (x)
     return bob_loblaw;
else{
    // Lobs law bomb
}
is equivalent to
1
2
3
 
if (x)
     return bob_loblaw;
// Lobs law bomb


Your code may be incorrect. Suppose you have the subtree null <- "A" -> "B". If the search arrives at the "A" node searching for string "A", the search will report that the subtree does not contain that string.
Bram van Velzen (7)
All right, I changed the code to this:
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
 
branch* branch::find(string word)
{
	if (word.compare(_word) == 0)
		return this;

	if (_left != 0 && _right != 0)
	{
		if (word.compare(_word) < 0)
		{
			return _left->find(word);
		}
		else if (word.compare(_word) > 0)
		{
			return _right->find(word);
		}
		else
		{
			if (word.compare(_word) == 0)
				return this;
		}
	}

	if (_left && !_right)
		return _left->find(word);

	if (!_left && _right)
		return _right->find(word);

	if (!_left && !_right)
		return NULL;

}

helios (17574)
You can still make it much shorter. Try to figure it out.
Bram van Velzen (7)
I've got one more question regarding the same project, it is however about filestoring. Can I ask this question in the same thread or should I use a different thread for it? For now I'll post it here. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
void tree::write_into_file(string fname) const
{
	ofstream fp;
	fp.open(fname);
	if (!fp.is_open()) {
	   cerr << "Cannot open file \"" << fname << "\"" << endl;
	   return;
	}

	_root -> write_pre_order(&fp);
	fp.close();

}

void branch::write_pre_order(ofstream* file) const
{
    *file << _word << endl;

    if (_left)
        _left->write_pre_order(file);

    if (_right)
        _right->write_pre_order(file);
}


It works but I am not quite comfortable yet whith such a recursive algorithm in combination with a stack, probably mostly because of the stack. Do I understand it correctly that if a new instance of the function is being loaded from a certain line in that specific instance of the function (let's call it X) that once it finished the last line of code of the new instance of the function it continues in instance X of the function as from one line lower until the very end?

A visual schematic for something like this would be very helpful.
Last edited on
helios (17574)
Do I understand it correctly that if a new instance of the function is being loaded from a certain point in that specific instance of the function (let's call it X) that once it finished the later instance of the new instance of the function it continues in instance C of the function untill the very end?
I'm not sure I understand the question. You can recurse twice in a row, and what will happen is, once the first call returns, the program will continue with the second call.
It's not correct to talk about "instances of functions". Functions are not instanced in C++. In this particular context, it's also incorrect to say that write_pre_order() will be "loaded" when it's called. When a recursive function is called, what will happen is that the program will record in the call stack a pointer to the code that must be executed when the callee returns. It's always the same code being executed, all that changes is the contents of the stack and the values of the parameters; in fact, you could rewrite the function as a loop if you wanted (the same is true of all recursive functions).
Bram van Velzen (7)
I think I understand it.

Is this a correct way to handle an error in opening the file if you want to store that data in that file? 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
void tree::write_into_file(string fname) const
{
	ofstream fp;
	fp.open(fname);
	if (fp.is_open())
	{
		
		_root->write_pre_order(&fp);
		fp.close();
	}

	else
		{
			cerr << "Cannot open file \"" << fname << "\"" << endl;
			return;
		}


}
helios (17574)
This new code is functionally equivalent to the one you had before.
Topic archived. No new replies allowed.