binary tree

How to create binary tree.

Page 1 of 1

1 Replies - 2899 Views - Last Post: 20 September 2008 - 10:29 PM Rate Topic: -----

#1 sandip_ray  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 20-September 08

binary tree

Posted 20 September 2008 - 10:04 PM

#include <stdio.h>
#include <conio.h>
#include <alloc.h>

struct node
{
	struct node *left ;
	char data ;
	struct node *right ;
} ;

struct node * buildtree ( int ) ;

char arr[ ] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', '\0', '\0', 'H' } ;
int   lc[ ] = {  1,   3,   5,   -1,   9,  -1,  -1,   -1,   -1,  -1 } ;
int   rc[ ] = {  2,   4,   6,   -1,  -1,  -1,  -1,   -1,   -1,  -1 } ;

void main( )
{
	struct node *root ;

	clrscr( ) ;

	root = buildtree ( 0 ) ;
	printf ("\nIn-order Traversal:\n\n\n\n" ) ;
	inorder ( root ) ;

	getch( ) ;
}

struct node * buildtree ( int index )
{
	struct node *temp = NULL ;
	if ( index != -1 )
	{
		temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
		temp -> left = buildtree ( lc[index] ) ;
		temp -> data = arr[index] ;
		temp -> right = buildtree ( rc[index] ) ;
	}
	return temp ;
}


*edit: Please use code tags in the future, thanks! :code:


now my problem is on passing 0 in funct buildtree(0) the first node 'A' is created but then immediately the control goes back to the func builtree() where the index becomes 3 & so on.So when the data is getting inserted??How is it working?

This post has been edited by Martyr2: 20 September 2008 - 10:13 PM


Is This A Good Question/Topic? 0
  • +

Replies To: binary tree

#2 Martyr2  Icon User is offline

  • Programming Theoretician
  • member icon

Reputation: 4399
  • View blog
  • Posts: 12,255
  • Joined: 18-April 07

Re: binary tree

Posted 20 September 2008 - 10:29 PM

Well if you are looking for an explanation of what this code is doing it is taking a 0 to start as a root node, then it goes into an if statement where it calls the buildTree recursively. This means that the function calls itself before it finishes. Each time it calls itself it is adding a node to the left. When there is no more items to add (because it hits -1) it returns to the previous instance that called it.

So here is the call order, first function is called with 0, it goes into the if statement where it calls itself with the next value in the lc array. That call again calls the next lc[] array value and so on until it hits -1.

Once it hits -1 it returns to the previous calling function where it sets the node data value and goes into a recursive call with rc[] values.

So if you can think of a tree it is starting at the root and going into the left branch which goes into a left branch, returns, sets the branch variable, goes into the right branch, returns and finishes back into the original function.

If you want to see how a binary tree works you can also check out my blog where I show you binary tree code as well as a graphic of how binary trees work...

Martyr2's Programming Underground - Nodes in a Linked List and Binary Tree

Enjoy! :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1