BST - Binary Search Tree (Iterative Function to Insert)
Hi, i was studying BST and tried to make a iterative function to insert, the original recursive function is the following:
1
2
3
4
5
6
7
8
9
10
11
|
void insert(node *&tree, int value) {
if (!tree) {
tree = new node;
tree->num = value;
tree->left = tree->right = NULL;
}
else if (value < tree->num)
insert(tree->left, value);
else if (value > tree->num)
insertar(tree->right, value);
}
|
And the code that i did is (but doesn't work):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
void insert(node *&tree, int value) {
if (!tree) {
tree = new node;
tree->num = value;
tree->left = tree->right = NULL;
}
else {
node *aux = tree;
while (aux)
if (value < aux->num)
aux = aux->left;
else if (value > aux->num)
aux = aux->right;
aux = new node;
aux->dato = value;
aux->left = aux->right = NULL;
}
}
|
So i ask if someone can help me with this, i don't see where the error is or why it doesn't work.
Last edited on
What exactly doesn't work? Can you show example input/output?
aux stops existing when your function ends, so any changes made to it are lost when the function ends. I assume that's a typo on line 17.
Untested:
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
|
void insert(node *&tree, int value)
{
if (!tree) {
tree = new node;
tree->num = value;
tree->left = tree->right = NULL;
}
else {
node * cur = tree ;
for ( ; ; )
{
while ( value < cur->num )
{
if ( cur->left )
cur = cur->left ;
else
{
cur->left = new node ;
cur->left->num = value ;
cur->left->left = cur->left->right = nullptr ;
return ;
}
}
while ( value > cur->num )
{
if ( cur->right )
cur = cur->right ;
else
{
cur->right = new node ;
cur->right->num = value ;
cur->right->left = cur->right->right = nullptr ;
return ;
}
}
}
}
}
|
[edit: If the value inserted is already in the tree, this will cause an infinite loop. Might want to fix that!]
Last edited on
Only suggestion I can come up with is to not do this:
tree->left = tree->right = NULL;
instead do:
1
2
|
tree->left = NULL;
tree->right = NULL;
|
Given it's C++, there should be no need for the line:
tree->left = tree->right = NULL;
as the node struct/class should be looking after itself, e.g.
1
2
3
4
5
6
7
8
|
struct node {
node() : left(NULL), right(NULL), num(0) {
}
node *left;
node *right;
int num; // or dato
};
|
or even handle the data via a construtor, etc.
Simplifying cire's code
1
2
3
4
5
6
7
8
9
10
11
12
13
|
node *aux = tree, *parent;
while (aux){
parent = aux;
if (value < aux->num)
aux = aux->left;
else if (value > aux->num)
aux = aux->right;
}
if( parent->num < value )
parent->right = new node(value);
else
parent->left = new node(value);
|
there is still the infinite loop if the value is already in, ;P
Thanks people, i used cire's code simplified by ne555 adding a break in case that you find a node with same value.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
void insert(node *&tree, int value) {
if (!tree)
tree = new node(value);
else {
node *aux = tree;
node *aux_2 = aux;
while (aux) {
aux_2 = aux;
if (value < aux->num)
aux = aux->izq;
else if (value > aux->num)
aux = aux->der;
else if (value == aux->num)
break;
}
if (value < aux_2->num)
aux_2->left = new node(value);
else if (value > aux_2->num)
aux_2->right = new node(value);
}
}
|
Topic archived. No new replies allowed.