Thread: Preorder Traversal

  1. #1
    Registered User
    Join Date
    Apr 2003
    Posts
    88

    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

  2. #2
    Registered User
    Join Date
    Apr 2003
    Posts
    88
    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 *'

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,682
    > Traverse(Tree_Header *psTree, int ilevel)
    Traverse(BST *psTree, int ilevel)
    seems much better to me - Tree_Header is just something to hold the tree and a bit of additional information.

    Start by calling it with
    Traverse(psTree->pRoot, 0);
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    Registered User
    Join Date
    Apr 2003
    Posts
    88
    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

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,682
    Once you're into the BST part, you do this...

    Traverse(psTree->left, ilevel+1);
    Traverse(psTree->right, ilevel+1);
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #6
    Registered User
    Join Date
    Apr 2003
    Posts
    88
    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)

  7. #7
    Registered User
    Join Date
    Apr 2003
    Posts
    88
    line 103 is the top one
    and line 662 is the bottom one

  8. #8
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,980
    Looks like it doesn't know what "BST" is.
    Try "struct BST" or use the typedef "Tree_node".

    gg

  9. #9
    Registered User
    Join Date
    Apr 2003
    Posts
    88
    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

  10. #10
    Registered User
    Join Date
    Apr 2003
    Posts
    88

    Angry

    anyone have any ideas?

  11. #11
    Registered User
    Join Date
    Apr 2003
    Posts
    88
    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.

  12. #12
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,682
    Well the introduction of local variables for your arrays is probably not what you want, because all your results will be lost.

    So I think it should be like this - note the extra param
    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;
    
    
    Traverse( Tree_Header *info, struct BST *psTree, int ilevel)
    {
    	//visit
    	if(psTree->left == NULL && psTree->right == NULL)
    	{
    		//increment leaves
    		info->leaves[ilevel]++;
    
    	}
    	else
    	{
    		//increment non_leaves
    		info->non_leaves[ilevel]++;
    	}
    	
    	Traverse(info, psTree->left, ilevel+1);
    	Traverse(info, psTree->right, ilevel+1);
    	printf("we made it");
    	return 0;
    }
    Which you call with something like
    Traverse(psTree,psTree->pRoot, 0);
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  13. #13
    Registered User
    Join Date
    Apr 2003
    Posts
    88
    I appreciate your help but it is still crashing

  14. #14
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,682
    Perhaps the way you construct your tree in the first place is at fault.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  15. #15
    Registered User
    Join Date
    Apr 2003
    Posts
    88
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. depth-first traversal of directories
    By geekoftheweek in forum C Programming
    Replies: 0
    Last Post: 03-31-2009, 01:22 AM
  2. Replies: 5
    Last Post: 11-21-2004, 04:39 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. using traversal pairs to build a tree
    By Unregistered in forum C++ Programming
    Replies: 0
    Last Post: 05-06-2002, 11:51 PM
  5. graph traversal
    By Unregistered in forum C Programming
    Replies: 2
    Last Post: 04-10-2002, 11:47 AM