I'm working on a binary space partition tree.
For the time being, the nodes are only inserted into the right. A node that has children will have 0 as data. Here are the insertion rules.
If the insertion node has data and no parent, the current data becames the left child, and the node to insert goes to the right.
1 0
^ ---> / \
1 2
If the node has a parent, is a the left child of the parent and has data, the node is reinserted in the parent's right node, and the inserted node takes its place
0 0
/ \ / \
1 2 ---> 3 0
^ / \
2 1
I'd like to have a feedback on my insert function. I put a goto
statement to not repeat code, but I'd like to avoid it to make the function more clear.
Live on Coliru with verbose output
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
struct node
{
int data;
struct node* parent;
struct node* left;
struct node* right;
};
struct node* create_node(int i)
{
struct node* n = calloc(1, sizeof(struct node));
n->data = i;
n->parent = NULL;
n->left = NULL;
n->right = NULL;
return n;
}
void destroy_node(struct node* n)
{
if (n->left != NULL)
{
destroy_node(n->left);
}
if (n->right != NULL)
{
destroy_node(n->right);
}
free(n);
}
void insert(struct node* i, struct node* n)
{
printf("insert at %d node %d\n", i->data, n->data);
// TODO : insert rightmost or leftmost
if (i->parent != NULL)
{
if (i->parent->left == i)
{
// if insert node is left
struct node* p = i->parent;
i->parent = NULL;
insert(p->right, i);
p->left = n;
n->parent = p;
return;
}
else if (i->parent->right == i)
{
// if insert node is right
if ((i->left == NULL) && (i->right == NULL))
{
// if insert node is rightmost
goto insert;
}
if (i->right != NULL)
{
// if right node is not rightmost
insert(i->right, n);
return;
}
}
}
else if (i->parent == NULL)
{
// if insert node is root
if ((i->left == NULL) && (i->right == NULL))
{
// if insert node has no children
goto insert;
}
else if (i->right != NULL)
{
// if right child is not null
insert(i->right, n);
return;
}
}
insert: ;
int value = i->data;
i->data = 0;
struct node* left = create_node(value);
left->parent = i;
n->parent = i;
i->left = left;
i->right = n;
return;
}
int main()
{
// A
struct node* root = NULL;
// B
root = create_node(1);
assert(root->data == 1);
assert(root->left == NULL);
assert(root->right == NULL);
// C
insert(root, create_node(2));
assert(root->data == 0);
assert(root->left->data == 1);
assert(root->right->data == 2);
// X
insert(root->right, create_node(3));
assert(root->right->data == 0);
assert(root->right->left->data == 2);
assert(root->right->right->data == 3);
// Y
insert(root->right->left, create_node(4));
assert(root->right->left->data == 4);
assert(root->right->right->data == 0);
assert(root->right->right->left->data == 3);
assert(root->right->right->right->data == 2);
// Z
insert(root->right->left, create_node(5));
assert(root->right->left->data == 5);
assert(root->right->right->left->data == 3);
assert(root->right->right->right->left->data == 2);
assert(root->right->right->right->right->data == 4);
destroy_node(root);
return 0;
}