C++

Forum

 
Problem with a binary tree code

master1001 (3)
Hello! I need to compile afunction to search for lineal descendants of
a specific element in a binary tree. But I don't understand why case 3 doesn't work. Please help 

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
 
#include <iostream>
using namespace std;

struct elem {                         
	char key;
	elem* left, * right;
} *root = NULL;     
void add(int n, elem*& t);
void obb(elem* t);  
void print(int n, int h);
void show(elem* t, int h);
int height(elem* t);
elem* search(int k, elem* t);
elem* search_iter(elem* t, int k);
void main()
{
	int num, ch, h, k;
	do {
		cout << "Menu\n";
		cout << "1.Add element\n";
		cout << "2.Preorder\n";
		cout << "3. Search and show\n";
		cout << "4.Show\n";
		cout << "Exit\n";
		cout << "Your choice: ";
		cin >> ch;
		switch (ch)
		{
		case 1: 
			cout << "num="; cin >> num;
			add(num, root); cout << endl;
			break;
		case 2: obb(root);
			h = height(root);
			show(root, h);
			 cout << endl;
			break;
		case 3:
			cout << "Cin element, whose descendants you're looking for\n";
			cin >> k;
			if (k != p->key) cout << "Wrong number";
			else elem *&p = search_iter(k); show(root, height(root));
			break;
		case 4: h = height(root);
			show(root, h); 
			cout << "\n"; break;
		}
	} while (ch != 0);
	system("pause");
}
void add(int n, elem*& t) {
	if (t == NULL) {
		t = new elem;
		t->key = n;
		t->left = t->right = NULL;
	}
	else
	{
		if (t->key < n)
			add(n, t->right);
		else
			add(n, t->left);
	}
}
void obb(elem* t) {
	if (t) {
		cout << t->key << " ";
		obb(t->left);
		obb(t->right);
	}
}
void print(int n, int h) {
	for (int i = 0; i < h; i++)
		cout << "\t";
	cout << n << "\n";
}
void show(elem* t, int h) {
	if (t) {
		show(t->right, h + 1);
		print(t->key, h);
		show(t->left, h + 1);
	}
}
int height(elem* t) {
	int u, v;
	if (!t) return -1;
	u = height(t->left);
	v = height(t->right);
	if (u > v) return u + 1;
	else return v + 1;
}
elem* search(int k, elem* t) 
{
	if (t)
	{
		while (t->key != k);
		{
			if (t->key < k)
				t = t->right;
			else
				t = t->left;
		}
	}
	return t;

}
elem* search_iter(elem* t, int k)
{
	while (t && t->key != k)
		if (t->key < k)
			t = t->right;
		else
			t = t->left;
	return t;
}
jonnin (11333)
only time for a quick drive by:
did you MEAN for the case 3 else to NOT contain both statements on its line (lack of braces)?
kbw (9488)
I don't understand what this statement does:
 
 
if (k != p->key) cout << "Wrong number";


Also, I can't see where p is declared, and don't understand its purpose.

Why can you read the number, then just search for it, starting at root?
master1001 (3)
okay, that's a good idea, but how it should be done ?
seeplus (6457)
[Very similar to this thread http://www.cplusplus.com/forum/general/283690/ - same course?]
Last edited on
dhayden (5795)
Why does case 2 show both a pre-order and an in-order copy?

Your in-order shows from largest to smallest. Is that what you intended, or did you mean smallest to largest?

search() will dereference a NULL pointer if the key isn't in the tree.

obb() prints t->key, which is a character. You should convert it to an int:
cout << (int)t->key << " ";

Why do you have search() and search_iter()? You probably need just one.

The semicolon at line 97 is wrong. The compiler interprets it like this:
1
2
3
4
5
6
7
8
 
while (t->key != k)
	;  // do nothing
{
	if (t->key < k)
		t = t->right;
	else
		t = t->left;
}


Did you mean to have an option 5 to exit? The menu just contains "exit"
seeplus (6457)
Possibly:

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
 
#include <iostream>

struct elem {
	int key {};
	elem* left {}, * right {};

	elem(int k) : key(k) {}
};

elem* root {};

void add(int n, elem*& t);
void inorder(const elem* t);
void print(int n, int h);
void show(const elem* t, int h);
int height(const elem* t);
const elem* search(int k, const elem* t);

int main() {
	int ch {};

	do {
		std::cout << "\nMenu\n" <<
			"1. Add element\n" <<
			"2. Display inorder\n" <<
			"3. Search and show tree\n" <<
			"4. Show tree\n" <<
			"0. Exit\n" <<
			"\nYour choice: ";

		std::cin >> ch;

		switch (ch) {
		case 1:
		{
			int num {};

			std::cout << "num= ";
			std::cin >> num;

			auto t { root };

			add(num, t);

			if (!root)
				root = t;

			std::cout << '\n';
		}
			break;

		case 2:
			inorder(root);
			std::cout << '\n';
			break;

		case 3: {
			int num {};

			std::cout << "Cin element, whose descendants you're looking for: ";
			std::cin >> num;

			const auto p { search(num, root) };

			if (!p)
				std::cout << "Wrong number";
			else {
				inorder(p);
				std::cout << '\n';
				show(p, height(p));
			}
		}

			break;

		case 4:
			show(root, height(root));
			std::cout << '\n';
			break;

		case 0:
			break;

		default:
			std::cout << "Invalid option\n";
			break;
		}
	} while (ch);
}

void add(int n, elem*& t) {
	if (!t)
		t = new elem(n);
	else
		add(n, n < t->key ? t->left : t->right);
}

void inorder(const elem* t) {
	if (t) {
		inorder(t->left);
		std::cout << t->key << ' ';
		inorder(t->right);
	}
}

void print(int n, int h) {
	for (int i {}; i < h; ++i)
		std::cout << '\t';

	std::cout << n << '\n';
}

void show(const elem* t, int h) {
	if (t) {
		print(t->key, h);
		show(t->left, h + 1);
		show(t->right, h + 1);
	}
}

int height(const elem* t) {
	if (!t)
		return -1;

	const auto u { height(t->left) };
	const auto v { height(t->right) };

	return 1 + (u > v ? u : v);
}

const elem* search(int k, const elem* t) {
	while (t && t->key != k)
		t = k < t->key ? t->left : t->right;

	return t;
}

master1001 (3)
Thank you very much, but can you give me an alternative for ,,auto'' ? I haven't used it
jonnin (11333)
use the explicit type. Auto uses the best fit type for an initialized variable creation, but you can put in the type yourself.

Not having used something is not a good reason to change it. Instead, embrace it and learn the new thing that you have encountered rather than avoid it. Auto can be over-used to the point that you can't tell what ANYTHING is easily, but it can also save typing weird, complicated types (like smart pointers of templates or iterators) by hand.
George P (5600)
an alternative for ,,auto'' ? I haven't used it

No time like the now to start learning about the benefits with using auto, and possible drawbacks of misusing/overusing it.

https://www.learncpp.com/cpp-tutorial/type-deduction-for-objects-using-the-auto-keyword/

https://www.educba.com/c-plus-plus-auto/

Using auto can save keystrokes, and possible headaches later if the data type(s) "up the chain" get changed/modified.
seeplus (6457)
an alternative for ,,auto


Work out manually what the type should be and replace auto with that type.

So for L125/126, height() returns a type int and so replace auto with int.

Similar logic for replacing auto on the other lines.
Last edited on
Topic archived. No new replies allowed.