• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1339
  • Last Modified:

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.
0
Atouray
Asked:
Atouray
  • 17
  • 12
  • 10
2 Solutions
 
phoffricCommented:
0
 
phoffricCommented:
0
 
AtourayAuthor Commented:
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?
0
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 
phoffricCommented:
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
0
 
AtourayAuthor Commented:
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.
0
 
AtourayAuthor Commented:
Paricularly one that has been implemented using arrays.
0
 
phoffricCommented:
OK, if I find one using arrays without pointers, I'll post the link.
0
 
AtourayAuthor Commented:
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?


0
 
phoffricCommented:
Although the following says C++, I don't see classes; and it looks like C. So give it a try.
http://www.daniweb.com/forums/thread18627.html
0
 
phoffricCommented:
lol. Wished you would have asked for this type of arithmetic calculator in your question.
0
 
AtourayAuthor Commented:
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
0
 
phoffricCommented:
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.
0
 
AtourayAuthor Commented:
Has anyone dopne any work on this threat. I would love to see the sample code of the implementation.
Thanks
0
 
phoffricCommented:
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.
0
 
AtourayAuthor Commented:
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'
0
 
ikeworkCommented:
is "BTREE" declared before those lines?
0
 
ikeworkCommented:
sorry phoffric, didnt see your last post, I totally agree with staying on topic :)
0
 
AtourayAuthor Commented:
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
0
 
ikeworkCommented:
The problem is the variable name "SIZE" here:

  BTREE makeTree(int a[], int i, int SIZE);

"SIZE" is already used here here:

  #define SIZE 9

just the variable name "SIZE" to something else:

  BTREE makeTree(int a[], int i, int any_name);


the other errors most likely will go away too, if not post back please
0
 
ikeworkCommented:
mmmmh, sorry, it was already posted on the other site
0
 
AtourayAuthor Commented:
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 ==========
0
 
ikeworkCommented:
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
0
 
ikeworkCommented:
Just reread the thread and realised, its most likely homework.
Wouldnt it be better to start from the scratch and actually learn something?
0
 
AtourayAuthor Commented:
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

0
 
ikeworkCommented:
>> 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.
0
 
ikeworkCommented:
However, the code you use from that page is very buggy, I wouldnt use it anyway. You wont learn much there.
0
 
AtourayAuthor Commented:
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
0
 
AtourayAuthor Commented:
Any help please?
0
 
phoffricCommented:
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.
0
 
ikeworkCommented:
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
0
 
ikeworkCommented:
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?
0
 
AtourayAuthor Commented:
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





0
 
AtourayAuthor Commented:
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
0
 
AtourayAuthor Commented:
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
0
 
ikeworkCommented:
>> "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.
0
 
AtourayAuthor Commented:
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.
0
 
ikeworkCommented:
>> 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

0
 
AtourayAuthor Commented:
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
0
 
phoffricCommented:
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.
0

Featured Post

Hire Technology Freelancers with Gigs

Work with freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely, and get projects done right.

  • 17
  • 12
  • 10
Tackle projects and never again get stuck behind a technical roadblock.
Join Now