Thread: Building B-Tree from Arrays

Hmm I need to build a binary tree from arrays, specifically the two arrays have a pre-order and an in-order sequence of the binary tree that it needs to build. I've done most of it and it works for a completely filled binary tree i.e. all nodes have left and right children except for the leafs. It also works for partially or unbalanced trees but the thing is that they have a value of "0" when I print them out when they are supposed to be NULL. The arrays can be assumed to have a global storage class for the problem and you can "assume" the sequence of keys are already put in.

Heres the whole code listing:

Code:

#include <stdio.h>
#include <stdlib.h>

#define MAX_LEVELS 8

typedef struct node {
	int key;
	struct node* left;
	struct node* right;
} NODE;

int pre_array[] = {6,4,2,7,10};
int in_array[] = {2,4,7,6,10};

NODE* buildTree(int i1, int i2, int p1, int p2);
void printTree(NODE* head);
int sSearch(int* array, int key, int size);
void show_tree(NODE* tree);
void show_tree_recurse(NODE* tree, int level);
void print_node(NODE* tree, int level);

int main(void)
{
	NODE* tree_initial = NULL;

	tree_initial = buildTree(0,(sizeof(in_array))/(sizeof(int))-1,0,
			(sizeof(pre_array))/(sizeof(int))-1);
	/* Print the tree and also print another
	with the layout of the tree */
	printf("\n\n");
	printTree(tree_initial);
	printf("\n\n");
	show_tree(tree_initial);

	return 0;
}

void printTree(NODE* head)
{
	if (head == NULL)
		return;

	printTree(head->left);
	printf("%d ",head->key);
	printTree(head->right);
}

NODE* buildTree(int i1, int i2, int p1, int p2)
{
	NODE* tree;

	/* Nodes have VALUE, i1/i2/p1/p2 have INDEX */

	int pre_index = p1;
	int pre_node = pre_array[p1];
	int find_node = pre_node;
	int in_index = sSearch(in_array,find_node,7);
	int in_node = in_array[in_index-1];
	int pre_left = sSearch(pre_array,in_node,7);

	/* For Debugging Purposes */
	printf("%d %d %d %d\n",i1,i2,p1,p2);
	
	/* Base Case */
	if (p1 >= p2 || i2 <= 0)
	{
		tree = malloc(sizeof(NODE));
		if (tree == NULL)
		{
			fprintf(stderr,"Could not allocate mem!\n");
			exit(1);
		}
		tree->key = pre_node;
		tree->left = NULL;
		tree->right = NULL;
		return tree;
	}

	if ((pre_array[p1] == in_array[p1]) && (pre_array[p1] == in_array[p2]))
		return NULL;

	tree = malloc(sizeof(NODE));
	if (tree == NULL)
	{
		fprintf(stderr,"Could not allocate mem!\n");
		exit(1);
	}

	tree->key = pre_node;

	tree->left = buildTree(i1, in_index-1, pre_index+1, pre_left);
	tree->right = buildTree(in_index+1, i2, pre_left+1, p2);  

	return tree;
}

int sSearch(int* array, int key, int size)
{
	/* Sequential Search Algorithm */
	int i = 0;
	for (i = 0; i < size; i++)
	{
		/* Return index if found */
		if (array[i] == key)
			return i;
	}

	/* Not found */
	return -1;
} 

void show_tree(NODE* tree)
{
	/* Print tree on a 90 degree angle */
	show_tree_recurse(tree,0);
}

void show_tree_recurse(NODE* tree, int level)
{
	if (tree == NULL || level == MAX_LEVELS)
		return;

	show_tree_recurse(tree->right, level+1);
	print_node(tree,level);
	show_tree_recurse(tree->left, level+1);
}

void print_node(NODE* tree, int level)
{
	int i;
	for (i = 0; i <= level; i++)
		printf("\t");
	printf("%d\n",tree->key);
}

The output for that tree is:

Code:

bash-3.00# ./q499
0 6 0 6
0 2 1 3
0 0 2 2
2 2 3 3
4 6 4 6
4 4 5 5
6 6 6 6


6 10 15 8 22 7 17 

                        17
                7
                        22
        8
                        15
                10
                        6

The arguments to the function are pretty confusing but the question requires that you must do it with those parameters so kinda stuck with those ugly values. Basically what you have to do is divide the two arrays into a "left" section and a "right" section and recursively insert them whilst dividing them by their index. Hard to explain but it's easier if you draw it on paper or something.

If I change the arrays to:

Code:

int pre_array[] = {6,4,2,7,10,11};
int in_array[] = {2,4,7,6,11,10};

I get some buggy output:

Code:

bash-3.00# ./q499
0 5 0 5
0 2 1 3
0 0 2 2
2 2 3 3
4 5 4 5
4 4 5 5
6 5 6 5


2 4 7 6 11 10 2 

                        2
                10
                        11
        6
                        7
                4
                        2

The furthest right child (2) shouldn't be there. You have to tilt your head anti-clockwise 90 degrees to see the tree structure.

I can't seem to figure out why it seems to happen - no compiler errors nor warnings as well. So it's most likely a logic problem I can't seem to get - any help would be great!
Sorry the post is a bit long as well..

Never mind I solved it