HELP IN C

AKIRA

AKIRA

Tank
Joined
Feb 6, 2006
Messages
3,000
Reaction score
2
How do I go about getting the size of a tree?

So far:
Code: 
void PrintPostOrder(BinaryTreeNode* root)
{
	if (root != NULL) {
		PrintPostOrder(root->left);
		PrintPostOrder(root->right);
		printf("%d ", root->item);
	}
}

Function I need to create:
Code: 
int GetSize(BinaryTreeNode* root)
{
	if (root == NULL)
	
		return 0;

	else {
		int 
	}
	return -1;
}

I did the base case, which is obviously if the tree is NULL, but I can't figure out how to get the size of the tree. I know that to get the size of a non-empty tree means that it's 1 plus the sizes of its left and right subtrees, but I don't know how to actually implement that..any help is greatly appreciated, thanks! :cheers:
 
Exactly as you said. If your tree is non-empty, you get the size of the left tree, the size of the right tree, add them together, add one, and return.

I'm somewhat sceptical about writing the code for you, because I don't know how much C you've done, or if it's an assignment you should be doing yourself :p

I'm pretty sure you can do it in a single line. You shouldn't even need your 'int' there.
 
Well one hint is that it'll be a recursive function. You already have the leaf base case and a model that traverses the tree.

You're almost there, dude!

EDIT: okay Druckles put it one step further than I did
EDIT EDIT: what's the -1 for?
 
Druckles said:
Exactly as you said. If your tree is non-empty, you get the size of the left tree, the size of the right tree, add them together, add one, and return.

I'm somewhat sceptical about writing the code for you, because I don't know how much C you've done, or if it's an assignment you should be doing yourself :p

I'm pretty sure you can do it in a single line. You shouldn't even need your 'int' there.
Click to expand...

I tried this:
Code: 
int GetSize(BinaryTreeNode* root)
{
	if (root == NULL)
	
		return 0;

	else {

		return GetSize(1+((root->left) + GetSize(root->right)));
	}
	
}

Except when I run it, nothing prints out.

I'm very new to C and this is part of a lab that I'm trying to figure out on my own but having trouble.
 
MuToiD_MaN said:
EDIT EDIT: what's the -1 for?
Click to expand...

I assume in case something terrible goes wrong.

Or it was written by a lecturer/teacher/someone who does it out of habit.

Code: 
return GetSize(1+((root->left) + GetSize(root->right)));

You're almost there with this line, but thinking about it, you may want to split it up into several lines. We'll go back to the 'int'. Here's a good starting point:

Code: 
else {
   int size;
   [...]
   return size;
}

If you do each step line by line, it should become much clearer. Have you done any programming before C?
 
AKIRA said:
I tried this:
Code: 
		return GetSize(1+((root->left) + GetSize(root->right)));
Click to expand...

I'm surprised that compiled, but I think what you're actually doing is unintentionally very complicated.

Anyways, the hint I'll give you is that each call of GetSize should have just one expression as a parameter, either root->left or root->right
 
Druckles said:
Exactly as you said. If your tree is non-empty, you get the size of the left tree, the size of the right tree, add them together, add one, and return.

I'm somewhat sceptical about writing the code for you, because I don't know how much C you've done, or if it's an assignment you should be doing yourself :p

I'm pretty sure you can do it in a single line. You shouldn't even need your 'int' there.
Click to expand...

the height of the tree is the max of the heights of the left and the right. This is assuming that you're talking about binary trees. so what you need to do is apply this case to each node. It will probably look something like this if done recursively.

NOTE : This is not C , but you get the gist of it.

Code: 
function height(node n) {
if(n==null)
return 0;
return 1+max(height(n.left),height(n.right));
}
 
mindless_moder said:
the height of the tree is the max of the heights of the left and the right. This is assuming that you're talking about binary trees. so what you need to do is apply this case to each node. It will probably look something like this if done recursively.
Click to expand...

The height of the tree is not the same as the size of the tree.
 
Ah, I'm slow lol did this and it worked:

Code: 
int GetSize(BinaryTreeNode* root)
{
	if (root == NULL)
	
		return 0;

	else {
			int leftVal = GetSize(root->left);
			int rightVal = GetSize(root->right);

			return 1+( leftVal+ rightVal);
	}
	
}

Thanks for all the replies!:cheers:
 
AKIRA said:
Ah, I'm slow lol did this and it worked:

Code: 
int GetSize(BinaryTreeNode* root)
{
	if (root == NULL)
	
		return 0;

	else {
			int leftVal = GetSize(root->left);
			int rightVal = GetSize(root->right);

			return 1+( leftVal+ rightVal);
	}
	
}

Thanks for all the replies!:cheers:
Click to expand...

I'm assuming the "1 +" part is for the root node itself.

You can now simplify your code to this:

Code: 
int GetSize(BinaryTreeNode* root)
{
	if (root == NULL)
	
		return 0;

	else {

		return 1 + GetSize(root->left) + GetSize(root->right);
	}
	
}
 
Hazar said:
I'm assuming the "1 +" part is for the root node itself.

You can now simplify your code to this:

Code: 
int GetSize(BinaryTreeNode* root)
{
	if (root == NULL)
	
		return 0;

	else {

		return 1 + GetSize(root->left) + GetSize(root->right);
	}
	
}
Click to expand...

which you can further simplify to

Code: 
int GetSize(BinaryTreeNode* root)
{
	return (root==null)?0:1 + (root->left==null)? 0:GetSize(root->left) + (root->right==null)? 0:GetSize(root->right);
}
.

yeah i'm being silly.
 
actually that's wrong, it returns 1 for an empty tree.
 
I honestly don't even know what trees are for. I didn't in my programming classes either and never asked... what is it some kind of self indexing search matrix kinda thing? I've never used one or anything close to one.
 
problems like this are a LOT more interesting than the stuff i have to code on a day to day basis.

@starBob : A binary tree is a data structure in which data is ordered according to its size, so it optimizes certain tasks like finding the highest or lowest piece of data (keep things generic) in a set of data. The first element in the tree is called the root all elements bigger than the root go to the right and all elements smaller go to the left, this rule is then applied recursively to each element until it finds the right position.

Theres no real concept of indexing , everything is linked by pointers sort of like a linked list.

Btree1.jpg
 
AKIRA said:
I am confuse.
Click to expand...

Confused about what? Need a hand?

StarBob said:
I honestly don't even know what trees are for. I didn't in my programming classes either and never asked... what is it some kind of self indexing search matrix kinda thing? I've never used one or anything close to one.
Click to expand...

They're a data structure, like arrays. But the way they're structured makes them much more efficient, on average.

An array you'd have to go through one at a time to find something, but a (balanced) tree will always be ln n. Quicker, basically, because at worst, it needs to get to the bottom of the tree, and the height is much shorter than the length of an array.

Sorry, I'm becoming a bit incoherent.
 
StarBob said:
I honestly don't even know what trees are for. I didn't in my programming classes either and never asked... what is it some kind of self indexing search matrix kinda thing? I've never used one or anything close to one.
Click to expand...

As a concrete example look at how your files are ordered. Starting with the root directory and then sub directories and so on.
 
@starBob : In a balanced tree every time you choose the left or right sub tree you are effectively dividing the search space by 2 , thus giving you the nice logarithmic run time. For example if i'm searching for a value which is bigger than the root element i can completely ignore the left sub tree. But since an array isn't structured we would have to look through all n elements. Doing a binary search on a sorted array would yield similar results.
 
I get it, but what I wanted was a real world example. I sucked in all of my programming classes because we'd get these abstract assignments to make an application that did nothing but demonstrate a procedure (like binary tree functionality). Once I got out into the workforce and saw what things were actually used for, I began to better understand different aspects of coding. What's an actual application of binary trees? Someone mentioned file directories and such, but that seems to be just a basic tree. Is it just a an efficient way to search a group of objects?
 
I'm not sure if this is the same thing, I never did much C programming. It reminds me of a recursive tree traversal:

http://articles.sitepoint.com/article/hierarchical-data-database

I use this all the time.

Say you have a website that sells products, those products are arranged in to categories.

Cat A
- Sub Cat 1
- Sub Sub Cat 1
- Sub Cat 2
Cat B

Not lets say you want all the products from sub cat 1, sub cat 2, and Sub sub cat 1 to show up when you click on Cat A. Normally you would have to have a field in your database for top_cat and for each subcategory you would need to run a query. This would work but could lead to many queries (hundreds in some cases) that would slow your entire program down.

With a recursive tree using left/right values for each category you can do all this with one simple query. The site point article on this is a great read.

I have no idea if binary trees are the same thing but that's what it seems like to me.
 
Well I tried that fizzbuzz thing and it took me forever because I couldn't for the life of me remember how to output to the console in VB... which makes the whole thing like 5 lines or whatever... I also madeit in an asp.net page wasn't wasn't too bad either... just some stupid string dancing. I like little programming challenges so I can remember important things I rarely use when doing what I do.
 
I really hope I'm not the only one who read the first line and thought "Well, you could get a piece of string and tie it around the tree trunk, and cut the string off and measure it."
 
Well came to another cross road this time with getting the maximum and minimum values of a tree.

I have this so far (just filled in the base case for max will do it for min too) but from there I am lost.
Code: 
int GetMax(BinaryTreeNode* root)
{
	if (root == NULL)
	
		return INT_MIN;

	else {
			int leftValMax = GetMax(root->left);
			int rightValMax = GetMax(root->right);
	}
	
}
/*
 * Function that returns the smallest element in a binary tree.
 * - The smallest element in an empty tree is INT_MAX (biggest possible integer).
 * - The smallest element in a nonempty tree is the smaller of the root's value 
 *   and the minimums in the left and right subtrees.
 *   
 */
int GetMin(BinaryTreeNode* root)
{
	/* implement me! */
	return INT_MAX;
}

Entire code for reference if it helps:
Code: 
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef int TreeEntry;

typedef struct binary_tree_node {
	TreeEntry item;
	struct binary_tree_node * left;
	struct binary_tree_node * right;
} BinaryTreeNode;


BinaryTreeNode* CreateNode(TreeEntry entry);
void            DestroyTree(BinaryTreeNode* root);
void            PrintInOrder(BinaryTreeNode* root);
void            PrintPreOrder(BinaryTreeNode* root);
void            PrintPostOrder(BinaryTreeNode* root);
int             GetHeight(BinaryTreeNode* root);

void            PrintReverseOrder(BinaryTreeNode* root);     /* exercise! */
int             GetSize(BinaryTreeNode* root);               /* exercise! */
int             GetSum(BinaryTreeNode* root);                /* exercise! */
int             GetMax(BinaryTreeNode* root);                /* exercise! */
int             GetMin(BinaryTreeNode* root);                /* exercise! */

BinaryTreeNode* CreateSampleTree();

void            Error(const char* msg);


int main(void)
{
	BinaryTreeNode* tree = CreateSampleTree();

	printf("In Order:      ");  PrintInOrder(tree); printf("\n");
	printf("Reverse Order: ");  PrintReverseOrder(tree); printf("\n");

	printf("Height: %d\n", GetHeight(tree));
	printf("Size:   %d\n", GetSize(tree));
	printf("Sum:    %d\n", GetSum(tree));
	printf("Max:    %d\n", GetMax(tree));
	printf("Min:    %d\n", GetMin(tree));

	DestroyTree(tree);

	return 0;
}


void Error(const char* msg)
{
	printf("ERROR: %s\n", msg);
	exit(EXIT_FAILURE);
}


BinaryTreeNode* CreateNode(TreeEntry entry)
{
	BinaryTreeNode* node = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
	if (node == NULL)
		Error("Out of memory");
	node->item = entry;
	node->left = NULL;
	node->right = NULL;
	return node;
}


BinaryTreeNode* CreateSampleTree()
{
	BinaryTreeNode* root = NULL;
	BinaryTreeNode* parent = NULL;

	/* create root node and its children */

	root = CreateNode(2);
	root->left = CreateNode(7);
	root->right = CreateNode(5);

	/* construct the left subtree */

	parent = root->left;
	parent->left = CreateNode(3);
	parent->right = CreateNode(6);

	parent = parent->right;
	parent->left = CreateNode(5);
	parent->right = CreateNode(11);

	parent = parent->left;
	parent->left = CreateNode(1);

	/* construct the right subtree */

	parent = root->right;
	parent->right = CreateNode(9);

	parent = parent->right;
	parent->left = CreateNode(4);

	return root;
}


void PrintInOrder(BinaryTreeNode* root)
{
	if (root != NULL) {
		PrintInOrder(root->left);
		printf("%d ", root->item);
		PrintInOrder(root->right);
	}
}


void PrintPreOrder(BinaryTreeNode* root)
{
	if (root != NULL) {
		printf("%d ", root->item);
		PrintPreOrder(root->left);
		PrintPreOrder(root->right);
	}
}


void PrintPostOrder(BinaryTreeNode* root)
{
	if (root != NULL) {
		PrintPostOrder(root->left);
		PrintPostOrder(root->right);
		printf("%d ", root->item);
	}
}


void DestroyTree(BinaryTreeNode* root)
{
	if (root != NULL) {
		DestroyTree(root->left);
		DestroyTree(root->right);
		free(root);
	}
}


int GetHeight(BinaryTreeNode* root)
{
	if (root == NULL)
		return 0;
	else {
		int leftHeight = GetHeight(root->left);
		int rightHeight = GetHeight(root->right);

		if (leftHeight > rightHeight)
			return 1 + leftHeight;
		else
			return 1 + rightHeight;
	}
}



/*
 *
 *    EXERCISES
 *
 */


void PrintReverseOrder(BinaryTreeNode* root)
{
	if (root != NULL) {
		PrintInOrder(root->right);
		printf("%d ", root->item);
		PrintInOrder(root->left);
	}
}


/*
 * Function that computes the number of elements in a binary tree.
 * - The size of an empty tree is 0.
 * - The size of a nonempty tree is one plus the sizes of its left and right subtrees.
 */
int GetSize(BinaryTreeNode* root)
{
	if (root == NULL)
	
		return 0;

	else {
			int leftVal = GetSize(root->left);
			int rightVal = GetSize(root->right);

			return 1+( leftVal+ rightVal);
	}
	
}
/*
 * Function that computes the sum of all elements in a binary tree.
 * - The sum of an empty tree is 0.
 * - The sum of a nonempty tree is the root's value plus the sums of the left and right subtrees.
 */
int GetSum(BinaryTreeNode* root)
{
	if (root == NULL)
	
		return 0;

	else {
			int leftSide = GetSum(root->left);
			int rightSide = GetSum(root->right);

			return (leftSide + rightSide + root->item);
	}		
}
/*
 * Function that returns the biggest element in a binary tree.
 * - The biggest element in an empty tree is INT_MIN (smallest possible integer).
 * - The biggest element in a nonempty tree is the bigger of the root's value 
 *   and the maximums in the left and right subtrees.
 *   
 */
int GetMax(BinaryTreeNode* root)
{
	if (root == NULL)
	
		return INT_MIN;

	else {
			int leftValMax = GetMax(root->left);
			int rightValMax = GetMax(root->right);
	}
	
}
/*
 * Function that returns the smallest element in a binary tree.
 * - The smallest element in an empty tree is INT_MAX (biggest possible integer).
 * - The smallest element in a nonempty tree is the smaller of the root's value 
 *   and the minimums in the left and right subtrees.
 *   
 */
int GetMin(BinaryTreeNode* root)
{
	/* implement me! */
	return INT_MAX;
}
 
If its a binary tree then the biggest number is the right most node and the smallest number is the left most node, so just keep going right or left respectively. Theres a trick to stopping it though.


AKIRA said:
Code: 
int GetMax(BinaryTreeNode* root)
{
	if (root == NULL)
	
		return INT_MIN;

	else {
			int leftValMax = GetMax(root->left);
			int rightValMax = GetMax(root->right);
	}
	
}
Click to expand...


you dont need to check the left sub tree if you're looking for the biggest number .... everything in the left tree is smaller than the root. I hope i didn't read this wrong again.
 
Ok, I got the GetMax and GetMin functions to work by doing this:
Code: 
int GetMax(BinaryTreeNode* root)
{
	int maxVal = 0;
	if (root == NULL)
	
		return INT_MIN;

	else {
			
			int Item = root->item;
			int leftValMax = GetMax(root->left);
			int rightValMax = GetMax(root->right);
			
			if(leftValMax>rightValMax)
				maxVal = leftValMax;
			else
				maxVal = rightValMax;
			if(Item>maxVal)
				maxVal = Item;
	}
	
	return maxVal;
}
/*
 * Function that returns the smallest element in a binary tree.
 * - The smallest element in an empty tree is INT_MAX (biggest possible integer).
 * - The smallest element in a nonempty tree is the smaller of the root's value 
 *   and the minimums in the left and right subtrees.
 *   
 */
int GetMin(BinaryTreeNode* root)
{
	int minVal = 0;
	if (root == NULL)
	
		return INT_MAX;

	else {
			
			int Item = root->item;
			int leftValMin = GetMin(root->left);
			int rightValMin = GetMin(root->right);
			
			if(leftValMin<rightValMin)
				minVal = leftValMin;
			else
				minVal = rightValMin;
			if(Item<minVal)
				minVal = Item;
	}
	
	return minVal;
}

My question is though..is there another way of doing this? An easier/less messy way?
 
why are you traversing the left subtree for getMax?.

why are you traversing the right subtree for getMin?.

What is the difference between initializing maxVal to 0 and initializing it to item ?.

Will this work if there are negative numbers in the tree ?.

What if you want to find the highest negative number ?.
 
Is your tree ordered? I.e. when you put items in, do you put them on the right if they're bigger and on the left if they're smaller than root? Or vice versa.

If they are balanced, then it would make the 'else' statement much simpler.

As a side note, the fact you 'return' at the end of your if means you don't need the 'else{' around the main body of the code. If the if is satisfied, then the else will never be executed, because the function returns. It just neatens up your code a bit.
 
He included the code that had the initialization of the tree. It's unordered and unbalanced. Hence traversing the entire tree.

I could have made a mistake here but ...
Code: 
         2
      7     5
    3   6     9
  5  11     4
1
 
not entirely sure what he's doing with the INT_MIN and INT_MAX . But a better solution would be to use one of the tree values (the root ?) as a starting point and then compare the remaining elements to that value . That way you don't have to worry about negative numbers.
 
INT_MIN is the most negative number and INT_MAX is the most positive. It's guaranteed that any number you compare it to, regardless of sign, will be greater (or lesser, respectively). I think what Akira wrote is everything a student's implementation should be. Methodical, accurate, readable, and handles all possible inputs.

By the way, this is handy:
Code: 
#define MIN(x, y) ((x) < (y) ? (x) : (y))

So your GetMin() function would look like this (and this is how I would have written it):
Code: 
[I]*snip*[/I]
else {
			int leftValMin = GetMin(root->left);
			int rightValMin = GetMin(root->right);
			
			minVal = MIN(leftValMin, rightValMin);
			minVal = MIN(minVal, root->item);
	}
or even:
Code: 
[I]*snip*[/I]
else {
			int leftValMin = GetMin(root->left);
			int rightValMin = GetMin(root->right);
			
			minVal = MIN(MIN(leftValMin, rightValMin), root->item);
	}
But you see what I mean about readability.

You gotta be careful with macros by the way. You wouldn't want to write

Code: 
minVal = MIN(GetMin(root->left), rightValMin);
because that would expand to
Code: 
minVal = (GetMin(root->left)) < (rightValMin) ? (GetMin(root->left)) : (rightValMin);
and you wouldn't want that GetMin() recursive function to get called more than once. Ignore all of this if you're not ready start messing with macros :P
 
are those constants in the c library ?. that's pretty cool. I had no idea it was an unordered binary tree , how boring.
 
Even if it's not in the library (or in my case, there is no library) you can always go #define it yourself.
 
Hey guys...I got good on that assignment and would like to thank you all for helping!!

Another question though...i'm doing my final assignment where we have to deal with sets..i'm using arrays and have a few questions.

this function:

Boolean Set_Insert(Set* set, SetEntry value);
This function adds a new value to a set. The function must ensure that duplicate values are not inserted.
If the value already exists in the set, do not insert it again. The parameter set is a pointer
to an initialized set. The parameter value is the value to be added to the set. The function should
return TRUE if the value was inserted or FALSE if the value already existed in the set.

I have this so far:
Code: 
Boolean Set_Insert(Set* set, SetEntry value)
{
	if(set != NULL){
		for(int i=0; i<set->arrValue[count];i++){
			if(set->arrValue[count] == set->arrValue[count])
				
		}
		set->count++;
		set->arrValue[set->count-1]= value;
		
		return TRUE;
	}
    return FALSE;
}

I'm stuck..I figured out how to add an element in the array but I don't know how to check to see if there are any duplicate values?? I know that my if statement inside the for loop is so wrong but thats the only idea i've come up with lol. Been at this for an hour now and no luck..as you can tell I suck at C but I need to do well on this assignment.

Thanks in advance!! :cheers:
 
You must log in or register to reply here.

Similar threads

MuToiD_MaN
Seems we'll have new Half-Life game. What's some life events you've had since Orange Box in 2007?
Replies
24
Views
4K
Shem
Shem
bbson john
Hi everyone. I am new to this forum!
Replies
11
Views
7K
Tollbooth Willie
Tollbooth Willie
MFL
Fascinating look at the ongoing psychological evolution of flat hieirarchies.
Replies
2
Views
3K
Tollbooth Willie
Tollbooth Willie
B
From Warren Spector to Arkane Studios: Half-Life 2's cancelled Ravenholm episode
Replies
2
Views
11K
Clan Wolf 2
Clan Wolf 2
B
Marc Laidlaw releases Half-Life 2: Episode Three's plot
Replies
32
Views
40K
BabyHeadCrab
BabyHeadCrab
Back
Top