Link to home
Start Free TrialLog in
Avatar of Atouray
Atouray

asked on

How to code binary tree abstract data type in C

Hello experts,
I just wanted to know if someone has implemented a binary tree abstract data type in C. i am practising stuff on it and wanted to see if i can have a sample code someone has already written. \
Can someone help me with a sample please.
Avatar of phoffric
phoffric

Avatar of Atouray

ASKER

I have seen this tutorial. I am just looking for a sample code that was implemented in C. Do you have any sample code to show me Please?
re: "i am practising stuff on it"
If you would submit what you have, and indicate where you are having trouble, then I sure that we can assist you. As you know, if this is homework, then EE cannot provide you with the fully worked out assignment.

Here is a link with a simple program to insert nodes, and print them out.
http://www.macs.hw.ac.uk/~rjp/Coursewww/Cwww/tree.html
Avatar of Atouray

ASKER

This is not definitely homework. Just practicing C programming. I am new to C programming and i am trying to learn now. I don't know if my approach to learning is good, but i like to look at sample program, understand how it works and then try to program it myslef.
This is why i am seeking for a sample Complete program in C here.
Avatar of Atouray

ASKER

Paricularly one that has been implemented using arrays.
OK, if I find one using arrays without pointers, I'll post the link.
Avatar of Atouray

ASKER

I would like to see the following in the sample code which i am practising:
Pretraversal function that performs the preorder traversal of the binary tree
Intraversal function that performs the inorder traversal of the binary tree
Posttraversal function that performs the postorder traversal of the binary tree
Leveltraversal function that performs the level-order traversal of the binary tree
also
The GenBinTree function should be able to  transfer the 3-tuple list to a binary tree structure as follows

e.g  (-, (/, (*, 4, (+, 15, 10)), 7), 9)

The GenBinTree function should transfer an infix expression to its corresponding binary tree structure
Any sample on this please?


ASKER CERTIFIED SOLUTION
Avatar of phoffric
phoffric

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
lol. Wished you would have asked for this type of arithmetic calculator in your question.
Avatar of Atouray

ASKER

I am trying to following the link you provided, but could not see the functions i nameed in my last post, ie
Pretraversal function that performs the preorder traversal of the binary tree
Intraversal function that performs the inorder traversal of the binary tree
Posttraversal function that performs the postorder traversal of the binary tree
Leveltraversal function that performs the level-order traversal of the binary tree
also
The GenBinTree function should be able to  transfer the 3-tuple list to a binary tree structure as follows

e.g  (-, (/, (*, 4, (+, 15, 10)), 7), 9)

The GenBinTree function should transfer an infix expression to its corresponding binary tree structur
How do i also Add a BinTree_plot function to print out the above binary tree structure
thanks
I posted the link not knowing that you had add a 3rd requirement. My post was for your 2nd requirement to use arrays rather than links. I hope the links have offered you something of value. In my search for links, I did not come across anything that resembled all your requirements. I suggest that you use the basics of the provided links, and then add in all your requirements.
Avatar of Atouray

ASKER

Has anyone dopne any work on this threat. I would love to see the sample code of the implementation.
Thanks
re: original question "has implemented a binary tree abstract data type in C. i am practicing stuff on it"
I think we are getting a little too far off the original question. If we helped you with the original question, you can close it. If not, then please ask for specific assistance and we will be happy to assist further on the original question. Thanks.

I think that if you want to start discussing calculators, you can easily start a different question, preferably after this one has been answered to  your satisfaction. Thanks.
Avatar of Atouray

ASKER

I tried running the link you sent me, but it gives me the error that the originall poster complained. I tried to see why the error, but still could not fix the error. Do you know why it is complaining of the following errors in these lines of codes:
BTREE makeTree(int a[], int i, int SIZE);
BTREE new_node();
BTREE init_node(DATA dat1, BTREE par1, BTREE par2);
BTREE insert(BTREE parent, BTREE root, int item);
Error      1      error C2143: syntax error : missing ')' before 'constant'
Error      2      error C2143: syntax error : missing ';' before 'constant'      
Error      3      error C2059: syntax error : ')'      
Error      4      error C2143: syntax error : missing ')' before 'constant'      
etc...
Any idea please? I need to run it first and then read, understandf it and add in my requirements, but right now it is not compiling
Thanks'
is "BTREE" declared before those lines?
sorry phoffric, didnt see your last post, I totally agree with staying on topic :)
Avatar of Atouray

ASKER

Yes, it is defiined before those lines. It is defined as
typedef node *BTREE;
see the code here:http://www.daniweb.com/forums/thread18627.html
Any idea?
Thanks
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
mmmmh, sorry, it was already posted on the other site
Avatar of Atouray

ASKER

I did what you said, but still have like 15 more errors, i was having 39 errors.
here are the errors:
1>c:\users\visual studio 2008\projects\bin_tree_adt\bin_tree_adt\bin_tree_adt.cpp(78) : error C2084: function 'int *order_array(int [])' already has a body
1>        c:\users\visual studio 2008\projects\bin_tree_adt\bin_tree_adt\bin_tree_adt.cpp(60) : see previous definition of 'order_array'
1>c:\users\visual studio 2008\projects\bin_tree_adt\bin_tree_adt\bin_tree_adt.cpp(117) : error C2057: expected constant expression
1>c:\users\visual studio 2008\projects\bin_tree_adt\bin_tree_adt\bin_tree_adt.cpp(117) : error C2466: cannot allocate an array of constant size 0
1>c:\users\visual studio 2008\projects\bin_tree_adt\bin_tree_adt\bin_tree_adt.cpp(117) : error C2057: expected constant expression
1>c:\users\visual studio 2008\projects\bin_tree_adt\bin_tree_adt\bin_tree_adt.cpp(117) : error C2466: cannot allocate an array of constant size 0
1>c:\users\visual studio 2008\projects\bin_tree_adt\bin_tree_adt\bin_tree_adt.cpp(186) : error C2440: 'return' : cannot convert from 'void *' to 'BTREE'
1>        Conversion from 'void*' to pointer to non-'void' requires an explicit cast
1>c:\users\visual studio 2008\projects\bin_tree_adt\bin_tree_adt\bin_tree_adt.cpp(189) : error C2065: 'dat1' : undeclared identifier
1>c:\users\visual studio 2008\projects\bin_tree_adt\bin_tree_adt\bin_tree_adt.cpp(189) : error C2275: 'BTREE' : illegal use of this type as an expression
1>        c:\users\visual studio 2008\projects\bin_tree_adt\bin_tree_adt\bin_tree_adt.cpp(19) : see declaration of 'BTREE'
1>c:\users\visual studio 2008\projects\bin_tree_adt\bin_tree_adt\bin_tree_adt.cpp(189) : error C2146: syntax error : missing ')' before identifier 'par1'
1>c:\users\visual studio 2008\projects\bin_tree_adt\bin_tree_adt\bin_tree_adt.cpp(189) : error C2365: 'init_node' : redefinition; previous definition was 'function'
1>        c:\users\visual studio 2008\projects\bintreeadt\bintreeadt\bintreeadt.cpp(27) : see declaration of 'init_node'
1>c:\users\visual studio 2008\projects\bintreeadt\bintreeadt\bintreeadt.cpp(189) : error C2078: too many initializers
1>c:\users\visual studio 2008\projects\bin_tree_adt\bintreeadt\bintreeadt.cpp(189) : error C2275: 'BTREE' : illegal use of this type as an expression
1>        c:\users\visual studio 2008\projects\bintreeadt\bintreeadt\bintreeadt.cpp(19) : see declaration of 'BTREE'
1>c:\users\visual studio 2008\projects\bintreeadt\bintreeadt\bintreeadt.cpp(189) : error C2059: syntax error : ')'
1>c:\users\visual studio 2008\projects\bintreeadt\bintreeadt\bintreeadt.cpp(190) : error C2143: syntax error : missing ';' before '{'
1>c:\users\visual studio 2008\projects\bintreeadt\bin_tree_adt\bintreeadt.cpp(190) : error C2447: '{' : missing function header (old-style formal list?)
1>BinTreeADT - 15 error(s), 0 warning(s)
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========
The fgirst one is saying, that order_array was defined twice

1>c:\users\visual studio 2008\projects\bin_tree_adt\bin_tree_adt\bin_tree_adt.cpp(78) : error C2084: function 'int *order_array(int [])' already has a body


Please show the current code here
Just reread the thread and realised, its most likely homework.
Wouldnt it be better to start from the scratch and actually learn something?
Avatar of Atouray

ASKER

It is actaully not a Homework. I have said it earlier, i just wanted to read it and understand how it works, but first i need to have it compile first and then need to do more stuffs in it for practising. It is just for practice because i am very new in C/C++, so i am learning it.
Here is the code i have errors in:

//    declaration of a binary tree with pointers to left and right children// #include <assert.h>#include <stdio.h>#include <stdlib.h> #define SIZE 9 typedef int DATA; struct node{	DATA dat;	struct node *left;	struct node *right;}; typedef struct node bNODE;typedef node *BTREE; void inorder(const BTREE root);void preorder(const BTREE root);void postorder(const BTREE root);BTREE makeTree(int a[], int i, int SIZE);BTREE new_node();BTREE init_node(DATA dat1, BTREE par1, BTREE par2);BTREE insert(BTREE parent, BTREE root, int item);int count_nodes(BTREE root, int cnt);int count_Lnodes(BTREE root, int cnt); int *makeArray(BTREE root, int val[]);int *inorder_traversal(int i, BTREE b_tree, int *valPtr);int *order_array(int a[]);void divide_array(int a[], int b[], int c[], int SIZE);int find_center(int a[], int SIZE); int main(){//	int command; 	BTREE b_tree;	int array_of_ints[] = {5, 10, 2, 5, 7, 12, 3, 9, 8};	int val[9] = {0};	int *valPtr = 0; 	b_tree = makeTree)array_of_ints, 0, SIZE);	printf("Tree printed 'in-order'\n");	preorder (b_tree);	putchar('\n');	printf("Number of nodes = %d\n", count_nodes(b_tree, 0));	printf("Number of Leaf nodes = %d\n", count_Lnodes(b_tree, 0));	printf("Here is the array made from the tree:\n");	valPtr = makeArray(b_tree, val);	return 0; } // put an array in alphabetical orderint *order_array(int a[]){	int j, i, temp;	int *b = a; 	for (i = 0; i < SIZE-1; ++i)	for (j = i+1; j < SIZE; ++j)	if (a[i] > a[j])	{		temp = a[i];		a[i] = a[j];		a[j] = temp;	}return b;} 	// put an array in alphabetical orderint *order_array(int a[]){	int j, i, temp;	int *b = a; 	for (i = 0; i < SIZE-1; ++i)	for (j = i+1; j < SIZE; ++j)	if (a[i] > a[j])	{		temp = a[i];		a[i] = a[j];		a[j] = temp;	}	return b;} // send function a, the array to be divided, and b and c, the 2 array pointersvoid divide_array(int a[], int b[], int c[], int SIZE){	int i, j; 	for (i = 0; i < SIZE/2; ++i) b[i] = a[i];	i++; // removing middle item, the one being added	for (j = 0; i < SIZE; ++i, ++j) c[j] = a[i];} // find center of an arrayint find_center(int a[], int SIZE){	int i = 0, center; 	while (i < SIZE) ++i;	center = i / 2;	printf("%d.. %d .. %d\n", i, center, a[center]);	return a[center];} // create ordered binary tree using recursion, divide array, then insert center intBTREE makeTree(int a[], int i, int SIZE){	int b[SIZE] = {0}, c[SIZE] = {0}; 	if(SIZE == 0) 		return NULL;	if(SIZE == 1)		init_node(a[0], NULL, NULL);	if(i <= SIZE)	{		divide_array(a, b, c, SIZE);		return init_node(find_center(a, SIZE), makeTree(b, 2 * i + 1, SIZE / 2), 		makeTree(c, 2 * i + 2, SIZE - SIZE / 2 - 1));	}}  // create array using inorder binary tree traversal and printint *makeArray(BTREE root, int val[]){	int i = 0, *valPtr; 	valPtr = val;	valPtr = inorder_traversal(i, root, val);	putchar('\n');	return valPtr;} // create array from binary treeint *inorder_traversal(int i, BTREE parent, int val[]){	int *valPtr;	valPtr = val; 	if (parent != NULL)	{		inorder_traversal(i, parent->left, val);		val[i] = parent->dat;		printf("%d ", val[i]);		++i;		inorder_traversal(i, parent->right, val);	}	return valPtr;} // inorder binary tree traversal and printvoid inorder(const BTREE parent){	if (parent != NULL) 	{		inorder(parent->left);		printf("%d ", parent->dat);		inorder(parent->right);	}} // preorder binary tree traversal and printvoid preorder(const BTREE root){	if (root != NULL) 	{		printf("%d ", root->dat);		preorder(root->left);		preorder(root->right);	}} // creating binary treesBTREE new_node(){	return (malloc(sizeof(bNODE)));} BTREE init_node(dat1, BTREE par1, BTREE par2){	BTREE t;	t = new_node();	t->dat = dat1;	t->left = par1;	t->right = par2;	return t;}  // count total number of nodesint count_nodes(BTREE root, int cnt){	if (root != NULL) 	{		cnt = count_nodes(root->left, cnt); /* recur left */		cnt = count_nodes(root->right, ++cnt); /* recur right */	}	return cnt;} // count number of leaf nodesint count_Lnodes(BTREE root, int cnt){	if (root != NULL) 	{		cnt = count_Lnodes(root->left, cnt);		cnt = count_Lnodes(root->right, cnt);		if (root->left == NULL && root->right == NULL) ++cnt;	}	return cnt;}//    declaration of a binary tree with pointers to left and right children//

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

#define SIZE 9

typedef int DATA;

struct node
{
	DATA dat;
	struct node *left;
	struct node *right;
};

typedef struct node bNODE;
typedef node *BTREE;

int siz=9;
void inorder(const BTREE root);
void preorder(const BTREE root);
void postorder(const BTREE root);
BTREE makeTree(int a[], int i, int siz);
BTREE new_node();
BTREE init_node(DATA dat1, BTREE par1, BTREE par2);
BTREE insert(BTREE parent, BTREE root, int item);
int count_nodes(BTREE root, int cnt);
int count_Lnodes(BTREE root, int cnt);

int *makeArray(BTREE root, int val[]);
int *inorder_traversal(int i, BTREE b_tree, int *valPtr);
//int *order_array(int a[]);
void divide_array(int a[], int b[], int c[], int siz);
int find_center(int a[], int siz);

int main()
{
//	int command;

	BTREE b_tree;
	int array_of_ints[] = {5, 10, 2, 5, 7, 12, 3, 9, 8};
	int val[9] = {0};
	int *valPtr = 0;

	b_tree = makeTree(array_of_ints, 0, siz);
	printf("Tree printed 'in-order'\n");
	preorder (b_tree);
	putchar('\n');
	printf("Number of nodes = %d\n", count_nodes(b_tree, 0));
	printf("Number of Leaf nodes = %d\n", count_Lnodes(b_tree, 0));
	printf("Here is the array made from the tree:\n");
	valPtr = makeArray(b_tree, val);
	return 0;

}

// put an array in alphabetical order
int *order_array(int a[])
{
	int j, i, temp;
	int *b = a;

	for (i = 0; i < siz-1; ++i)
	for (j = i+1; j < siz; ++j)
	if (a[i] > a[j])
	{
		temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
return b;
}

	// put an array in alphabetical order
int *order_array(int a[])
{
	int j, i, temp;
	int *b = a;

	for (i = 0; i < siz-1; ++i)
	for (j = i+1; j < siz; ++j)
	if (a[i] > a[j])
	{
		temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	return b;
}

Open in new window

>> It is actaully not a Homework. I have said it earlier, i just wanted to read it
>> and understand how it works, but first i need to have it compile first and then
>> need to do more stuffs in it for practising. It is just for practice because i am very
>> new in C/C++, so i am learning it.

Ok I see, then the link phoffric posted (http://www.macs.hw.ac.uk) is just perfect to start practising, its simple and easier to understand and actually answers your original question.
That you can take as a starting point and accept phoffric's post, since it answers the question.
However, the code you use from that page is very buggy, I wouldnt use it anyway. You wont learn much there.
Avatar of Atouray

ASKER

As i say, maybe my way of learning is not good, but that is how i am learning right noiw, maybe need to change, but my question is not answered as i have not got want i ask for. The code given to me cannot compile, so it is of very litlle significant to me, but anyway i am waiting for someone to help me fix the bug on the code i post. Can someone help me fix the bug for me as i am still tring to debug, but keep getting the same results
Avatar of Atouray

ASKER

Any help please?
ikework:
re: staying on topic
I was referring to changing the question to calculator type questions -  (-, (/, (*, 4, (+, 15, 10)), 7), 9)
So, I don't see a problem with helping to get a program to compile. I'll start taking a look a bit later. Jump in if you have time now.

Atouray:
Just curious.. What are your long-range goals w.r.t. Binary Trees? Why the restriction on dynamic allocation of nodes, and the must-have array approach? In practice, I believe that for trees that are large and have unpredictable size, some form of dynamic allocation is generally the preferred approach.
Ok Atouray, its your call..

About the errors, if you report "there is an error", then please post the error-message(s) plus which line they refer to.
However, here are some obvious errors:

1) You defined the function (the function body) "order_array" twice
2) Missing definitions for at least following functions, you can copy them from the page that you used the code from

  makeTree
  preorder
  makeArray
Btw, the B-Tree in that example does not use arrays to store the B-Tree-Nodes, it uses only an array to pass the data to the B-Tree, but the B-Tree does not store it in an array. The nodes are created in init_node() and new_node(). In new_node() the node is allocated dynamically using malloc, then the node is being put into the tree, there is no array involved.

BTREE init_node(dat1, BTREE par1, BTREE par2)
{
      BTREE t;
      t = new_node();
      t->dat = dat1;
      t->left = par1;
      t->right = par2;
      return t;
}

BTREE new_node()
{
      return (malloc(sizeof(bNODE)));
}


That code is messy! it does not implement, what you want, so why not using the better code posted above?
Avatar of Atouray

ASKER

Oh, yea, you are right. If you could help me on that, i will be very grateful. I really need you people to help me on this.
I would like to have the  functions of the ADT include GenBinTree , Pretraversal , Intraversal , Posttraversal and Leveltraversal. I also would like to be able to input a 3-tuple list as follows

                                      (-, (/, (*, 4, (+, 15, 10)), 7), 9) and it transfer the 3-tuple list to a binary tree structure as shown graphically like thus:

             | - |
            /---\
         | /|     | 9 |
       /---\    
    | * |   | 7 |    
    /  \
 | 4 |  |+|
        /  \
     |15|  |10|

Can someone help me on this please
Thanks





Avatar of Atouray

ASKER

Btw, the B-Tree in that example does not use arrays to store the B-Tree-Nodes, it uses only an array to pass the data to the B-Tree, but the B-Tree does not store it in an array. The nodes are created in init_node() and new_node(). In new_node() the node is allocated dynamically using malloc, then the node is being put into the tree, there is no array involved.

BTREE init_node(dat1, BTREE par1, BTREE par2)
{
      BTREE t;
      t = new_node();
      t->dat = dat1;
      t->left = par1;
      t->right = par2;
      return t;
}

BTREE new_node()
{
      return (malloc(sizeof(bNODE)));
}


That code is messy! it does not implement, what you want, so why not using the better code posted above?

I don't understand what you are saying in the above. When you say"why not using the better code posted above?" which code are you refering to?
I would be happy if you can just fix the errors for me and post it back to me here with no compile error. Can you Please do that for me?
Thanks
Avatar of Atouray

ASKER

you can go ahead a delete this topic. i am sorry if i could not make myself clear to your guys.
I have posted a new topic now.
I hope that will be understood
>> "why not using the better code posted above?" which code are you refering to?

I refered to the link that phoffric posted:

http://www.macs.hw.ac.uk/~rjp/Coursewww/Cwww/tree.html


>> I don't understand what you are saying in the above

I'm saying that the code you copied does not implement the B-Tree using arrays. You said:

  "Paricularly one that has been implemented using arrays."

The code you use does not implement it using arrays, plus its messy, so lets drop it.
Avatar of Atouray

ASKER

Infact, anyone is ok for me. Wether it is implemented using Arrays or pointers, they are all fine for me. Anyone i have is fine. Please check the new post i made.
Thanks.
>> Infact, anyone is ok for me

Great, then use the following code. Its simple, has no errors and works.
Its from the link that phoffric posted:

http://www.macs.hw.ac.uk/~rjp/Coursewww/Cwww/tree.html

However, this will just be a starting point for you. We will assist you implementing the functions that you need.
Start with destroying the tree, it is not properly deallocated. That way you will get used to the tree.
#include<stdlib.h>
#include<stdio.h>

struct tree_el {
   int val;
   struct tree_el * right, * left;
};

typedef struct tree_el node;

void insert(node ** tree, node * item) {
   if(!(*tree)) {
      *tree = item;
      return;
   }
   if(item->val<(*tree)->val)
      insert(&(*tree)->left, item);
   else if(item->val>(*tree)->val)
      insert(&(*tree)->right, item);
}

void printout(node * tree) {
   if(tree->left) printout(tree->left);
   printf("%d\n",tree->val);
   if(tree->right) printout(tree->right);
}

void main() {
   node * curr, * root;
   int i;

   root = NULL;

   for(i=1;i<=10;i++) {
      curr = (node *)malloc(sizeof(node));
      curr->left = curr->right = NULL;
      curr->val = rand();
      insert(&root, curr);
   }

   printout(root);
}

Open in new window

Avatar of Atouray

ASKER

Yea, i have ran it and it has no error, but i have posted a new topic which requires more than just what this is doing. I hope you can follow me on the new post and help me out.
Thanks
The question asked has been worked by ikework and me. Add on questions pertaining to  "I also would like to be able to input a 3-tuple list as follows (-, (/, (*, 4, (+, 15, 10)), 7), 9) and it transfer the 3-tuple list to a binary tree" was out-of-scope, and this is what has been reposted.

For the efforts put into this question, it seems reasonable that the author award or split points to the contributors. The add-on question is much more involved than the original question, and is going to be addressed in the author's new question.