Thread: Preorder Traversal

Alright I have seen a bunch of algorithms now, that I don't fully understand. I am trying to count leafs and non-leafs of a binary tree

I have this header struct for a binary tree where pRoot is the root

Code:

typedef struct BST
{
	char city[50];
	char zipcode[8];
	char state[2];
	double latitude;
	double longitude;
	long population;
	struct BST *left;
	struct BST *right;
	struct BST *parent;
}Tree_node;

typedef struct
{
	struct BST *pRoot;
	int itree_node_count;
	int idepth;
	int leaves[500];
	int non_leaves[500];
}Tree_Header;

I am declaring my fiunction like this

Code:

	int Traverse(Tree_Header *psTree, int);

calling it like this
CODE]Traverse(psTree, 0);[/CODE]

and then the function looks like this

Code:

Traverse(Tree_Header *psTree, int ilevel)
{
	
	//visit
	if(psTree->pRoot->left == NULL && psTree->pRoot->right == NULL)
	{
		//increment leaves
		psTree->leaves[ilevel]++;

	}
	else
	{
		//increment non_leaves
		psTree->non_leaves[ilevel]++;
	}
	Traverse(psTree->pRoot->left, ilevel+1);
	Traverse(psTree->pRoot->right, ilevel+1);

	return 0;
}

I wish I understood recursion better but I don't . If there is anyone that can help me with this, I would be very thankful because I am tired of beating my head on this keyboard

BTW

here are the warnings I am getting, I would assume they have something to do with it

\\COMP.UARK.EDU\HOMES\wog41.c(677) : warning C4133: 'function' : incompatible types - from 'struct BST *' to 'struct Tree_Header *'
\\COMP.UARK.EDU\HOMES\wog41.c(678) : warning C4133: 'function' : incompatible types - from 'struct BST *' to 'struct Tree_Header *'

does it matter if I don't change it to BST?
It gives me a whole bunch of crazy errors when I do

changed this though
Traverse(psTree->pRoot, 0);
but still doesn't clear anything up

changing my declarations to BST
like this

Code:

int Traverse(BST *psTree, int);

Code:

Traverse(BST *psTree, int ilevel)
{
	
	
	//visit
	if(psTree->left == NULL && psTree->right == NULL)
	{
		//increment leaves
		psTree->leaves[ilevel]++;

	}
	else
	{
		//increment non_leaves
		psTree->non_leaves[ilevel]++;
	}
	
	Traverse(psTree->left, ilevel+1);
	Traverse(psTree->right, ilevel+1);
	printf("we made it");
	return 0;
}

this gives me these errors
\COMP.UARK.EDU\HOMES\wog41.c(103) : error C2059: syntax error : ','
\\COMP.UARK.EDU\HOMES\wog41.c(103) : error C2143: syntax error : missing ')' before '*'
\\COMP.UARK.EDU\HOMES\wog41.c(103) : error C2143: syntax error : missing ';' before '*'
\\COMP.UARK.EDU\HOMES\wog41.c(103) : error C2059: syntax error : 'type'
\\COMP.UARK.EDU\HOMES\wog41.c(103) : error C2059: syntax error : ')'
\\COMP.UARK.EDU\HOMES\wog41.c(662) : error C2143: syntax error : missing ')' before '*'
\\COMP.UARK.EDU\HOMES\wog41.c(662) : error C2143: syntax error : missing '{' before '*'
\\COMP.UARK.EDU\HOMES\wog41.c(662) : error C2059: syntax error : 'type'
\\COMP.UARK.EDU\HOMES\wog41.c(662) : error C2059: syntax error : ')'
Error executing cl.exe.

wog41.obj - 9 error(s), 0 warning(s)

line 103 is the top one
and line 662 is the bottom one

Looks like it doesn't know what "BST" is.
Try "struct BST" or use the typedef "Tree_node".

gg

i used struct BST for both

Code:

int Traverse(struct BST *psTree, int);

Code:

Traverse(struct BST *psTree, int ilevel)
{
	int leaves[500], non_leaves[500];
	
	//visit
	if(psTree->left == NULL && psTree->right == NULL)
	{
		//increment leaves
		leaves[ilevel]++;

	}
	else
	{
		//increment non_leaves
		non_leaves[ilevel]++;
	}
	
	Traverse(psTree->left, ilevel+1);
	Traverse(psTree->right, ilevel+1);
	printf("we made it");
	return 0;
}

no errors, but it crashes

anyone have any ideas?

can someone seriously help?
I will even post the algorithm on here that everybody gives me.
I have been working on this one function for 8-9 hours now. I just want to understand it.

I appreciate your help but it is still crashing

i have looked through the tree and it looks fine.
I am able to search it and delete nodes fine. I don't think the actual tree is the problem.