counting nodes BST

This is a discussion on counting nodes BST within the C Programming forums, part of the General Programming Boards category; How do I count the nodes? i have got so far : Code: #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef ...

  1. #1
    Temporal Apparition qubit67's Avatar
    Join Date
    Jan 2007
    Posts
    85

    counting nodes BST

    How do I count the nodes? i have got so far :
    Code:
    #include <stdio.h>
    
    #include <stdlib.h>
    
    #include <assert.h>
    
    
    
    typedef int data_t;		/* For a tree of ints */
    
    #include "treeops.c"
    
    
    
    int
    
    main ()
    
    {
    
    	int value, size=0;
    
    	tree_t *tree;
    
    	node_t *result;
    
    	tree = make_empty_tree ();
    
    
    
    
    
    /** your experimentatation code goes here **/
    
    	printf("Enter some value onto a tree for testing: ");
    
    	while (scanf("%d", &value)!=EOF)
    
    	{
    
    		tree = insert_in_order (tree, value);	
    
    	}
    
    	size = tree_size(tree);
    
    	
    
    	printf("The size of the tree is: ");
    
    	printf("%d", size);
    
    	
    
        /** Clean up the mess **/
    
    	free_tree (tree);
    
    	tree = NULL;
    
    
    
        /** Exit gracefully **/
    
    	return (EXIT_SUCCESS);
    
    }
    
    
    int 
    
    tree_size(tree_t *tree) {
    
    	node_t *ptr;
    
    	ptr = tree->root;
    
    	return num_nodes(ptr);
    
    }
    
    
    
    int
    
    num_nodes(node_t *root) {
    
    	if (root==NULL)
    
    	{
    
    		return 0;
    
    	}
    
    	else 
    
    	{
    
    		return (1 + num_nodes(root->left) + num_nodes(root->right));		
    
    	}
    
    }
    
    
    
    
    tree_t
    
    *insert_in_order (tree_t *tree, data_t value)
    
    {
    
    	/* make new node */
    
    	node_t *new;
    
    	new = malloc (sizeof (node_t));
    
    	assert (tree!=NULL && new!=NULL);
    
    	new->data = value;
    
    	new->left = NULL;
    
    	new->right = NULL;
    
    	/* insert node in tree */
    
    	tree->root = recursive_insert (tree->root, new);
    
    	return tree;
    
    }
    Is there a better way to write tree_size to not include num_nodes. I find tree_size hard to deal with because it is passed a tree_t pointer, not a node_t and so cant recurse

  2. #2
    Temporal Apparition qubit67's Avatar
    Join Date
    Jan 2007
    Posts
    85
    my bad, it does work, but i was inserting the same number into the tree.... is there an iterative method to count the nodes? I understand that recursion is specifiically for BST's, but there must be a method to do it iterativly...

  3. #3
    Fear the Reaper...
    Join Date
    Aug 2005
    Location
    Toronto, Ontario, Canada
    Posts
    625
    Everything that's recursive can be done iteratively. But I can guarantee you it's not nearly as elegant.
    Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Double Linked List Sorting
    By algatt in forum C Programming
    Replies: 5
    Last Post: 09-15-2007, 01:41 PM
  2. BST Counting
    By m0ntana in forum C Programming
    Replies: 6
    Last Post: 05-11-2007, 06:37 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  4. Finding Nodes on a BST
    By s0ul2squeeze in forum C++ Programming
    Replies: 0
    Last Post: 05-05-2002, 02:25 PM
  5. counting nodes
    By sballew in forum C Programming
    Replies: 8
    Last Post: 10-27-2001, 09:03 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21