Building B-Tree from Arrays

This is a discussion on Building B-Tree from Arrays within the C Programming forums, part of the General Programming Boards category; Hmm I need to build a binary tree from arrays, specifically the two arrays have a pre-order and an in-order ...

  1. #1
    Registered User
    Join Date
    Apr 2004
    Posts
    173

    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..
    Last edited by 0rion; 04-09-2005 at 02:24 AM.

  2. #2
    Registered User
    Join Date
    Apr 2004
    Posts
    173
    Never mind I solved it
    Last edited by 0rion; 04-09-2005 at 05:27 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. Binary Tree, couple questions
    By scoobasean in forum C Programming
    Replies: 3
    Last Post: 03-12-2005, 08:09 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21