C++

Forum

 
Combining two binary trees into one

Heiru (7)
Hello again. I need to write a function that combines two binary trees that entered by the user into a new binary tree.
I have the general program down but i have literally no idea how to write the function that i need. Can somebody help with that? 

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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
 
#include <iostream>

using namespace std;

struct tree
{
	char key;
	tree* left;
	tree* right;
}*root=NULL;

void add(int n, tree* t);
void preorder(tree* t);
int del(int k);
tree*& search(int k);
tree* search_iter(tree* t, int k);
int height(tree* t);
void print_node(int n, int h);
void show(tree* t, int h);

int main()
{
	int num, choice = 0, h;

	do
	{
		cout << "\t\tMenu" << endl;
		cout << "1. Add element to binary tree" << endl;
		cout << "2. Print" << endl;
		cout << "3. Search element in binary tree" << endl;
		cout << "4. Delete element" << endl;
		cout << "5. Show" << endl;
		cout << "6. Exit" << endl;
		cout << "Enter your choice: " << endl;
		cin >> choice;

		switch (choice)
		{
		case 1:
			cout << "num=";
			cin >> num;
			add(num, root);
			break;
		case 2:
			cout << "All elements" << endl;
			preorder(root);
			break;
		case 3:
			cout << "Search: ";
			cin >> num;
			tree*& p = search(num);
			if (p == NULL)
				cout << "The element is NOT in the tree\n";
			else
				cout << "The element is in the tree\n";
			break;
		case 4:
			cout << "Enter element to delete: ";
			cin >> num;
			if (del(num) == 0)
				cout << "The element is NOT in the tree\n";
			break;
		case 5:
			h = height(root);
			show(root, h);
			cout << "\n";
			break;
		case 6:
			exit(0);
			break;
		}
	}while (choice != 6);
	system("pause");

	return 0;
}

void add(int n, tree* t)
{
	if (t == NULL)
	{
		t = new tree;
		t->key = n;
		t->left = t->right = NULL;
	}
	else
	{
		if (t->key < n)
			add(n, t->right);
		else
			add(n, t->left);
	}
}

void preorder(tree* t)
{
	if (t)
	{
		cout << t->key << " ";
		preorder(t->left);
		preorder(t->right);
	}
}

int del(int k)
{
	tree*& p = search(k), * p0 = p, ** qq, * q;
	if (p == NULL)
		return 0;

	if (p->right == NULL)
	{
		p = p->left;
		delete p0;
	}
	else
		if (p->left == NULL)
		{
			p = p->right;
			delete p0;
		}
		else
		{
			qq = &p->left;
			while ((*qq)->right)
				qq = &(*qq)->right;
			p->key = (*qq)->key;
			q = *qq;
			*qq = q->left;
			delete q;
		}
	return 1;
}

tree*& search(int k)
{
	tree** p = &root;

	for (;;)
	{
		if (*p == NULL)
			return *p;
		if (k < (*p)->key)
			p = &(*p)->left;
		else
			if (k > (*p)->key)
				p = &(*p)->right;
			else
				return *p;
	}
}

tree* search_iter(tree* t, int k)
{
	while (t && t->key != k)
		if (t->key < k)
			t = t->right;
		else
			t = t->left;

	return t;
}

int height(tree* 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;
}

void print_node(int n, int h)
{
	for (int i = 0; i < h; i++)
		cout << "\t";
	cout << n << "\n";
}

void show(tree* t, int h)
{
	if (t)
	{
		show(t->right, h + 1);
		print_node(t->key, h);
		show(t->left, h + 1);
	}
}
AbstractionAnon (6954)
Line 83: You have a type mismatch. You're passing in an int, but trying to store it in a char.

As to your question, show() shows you can walk the tree. To merge two trees, simply walk one tree and add each element to to the other tree.
jonnin (11437)
If you have a binary SEARCH tree (it appears that you DO), you have to insert each node (I don't know of any shortcuts). If it is just a binary tree, you can stuff the root of one tree in as a child on any open (null) pointer leaf node, intact, a single pointer assignment and its done.
Last edited on
seeplus (6591)
Small point. But in C++ it's nullptr instead of NULL (which is c) for null pointers.

seeplus (6591)
Also there is a problem with add. It doesn't update root if first add. Perhaps:

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
170
171
172
173
174
175
176
177
178
179
180
181
182
 
#include <iostream>

struct tree {
	int key {};
	tree* left {};
	tree* right {};

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

tree *root {};

void add(int n, tree*& t);
void preorder(tree* t);
bool del(int k);
tree*& search(int k);
tree* search_iter(tree* t, int k);
int height(tree* t);
void print_node(int n, int h);
void show(tree* t, int h);

int main() {
	int num {}, choice {};

	do {
		std::cout << "\t\tMenu\n" <<
			"1. Add element to binary tree\n" <<
			"2. Print\n"  <<
			"3. Search element in binary tree\n" <<
			"4. Delete element\n" <<
			"5. Show\n" <<
			"6. Exit\n" <<
			"\nEnter your choice: ";

		std::cin >> choice;

		switch (choice) {
		case 1: {
			auto temp { root };

			std::cout << "num= ";
			std::cin >> num;
			add(num, temp);

			if (!root)
				root = temp;
		}
			break;

		case 2:
			std::cout << "All elements\n";
			preorder(root);
			std::cout << '\n';
			break;

		case 3: {
			std::cout << "Search: ";
			std::cin >> num;
			tree*& p = search(num);
			if (!p)
				std::cout << "The element is NOT in the tree\n";
			else
				std::cout << "The element is in the tree\n";
		}
			break;

		case 4:
			std::cout << "Enter element to delete: ";
			std::cin >> num;
			if (!del(num))
				std::cout << "The element is NOT in the tree\n";

			break;

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

		case 6:
			//exit(0);
			break;

		default:
			std::cout << "Invalid option\n";
			break;
		}
	} while (choice != 6);
}

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

void preorder(tree* t) {
	if (t) {
		std::cout << t->key << ' ';
		preorder(t->left);
		preorder(t->right);
	}
}

bool del(int k) {
	tree* &p { search(k) }, *p0 { p };

	if (!p)
		return false;

	if (!p->right) {
		p = p->left;
		delete p0;
	} else if (!p->left) {
			p = p->right;
			delete p0;
		} else {
		    auto qq { &p->left };

			while ((*qq)->right)
				qq = &(*qq)->right;

			p->key = (*qq)->key;

			auto q { *qq };

			*qq = q->left;
			delete q;
		}

	return true;
}

tree*& search(int k) {
	tree** p { &root };

	for (;;) {
		if (*p == nullptr)
			return *p;

		if (k < (*p)->key)
			p = &(*p)->left;
		else
			if (k > (*p)->key)
				p = &(*p)->right;
			else
				return *p;
	}
}

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

	return t;
}

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

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

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

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

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

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

Topic archived. No new replies allowed.