Thread: leaves on a binary tree

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

    leaves on a binary tree

    okay the problem is to display only the leaves of the binary tree check the code its running but somehow I don't think the output is quite right.
    Code:
    #include <iostream>
    #include <string>
    using namespace std;
    struct node
    {
        char info[12];
        node *left;
        node *right;
    };
    void leafdisplay(node *p);    
    
    void inorder(node *p);      
    
    void preorder(node *p);
    
    void insert(node *&p, char string[12]);
    
    void insert(node *&p, char string[12]) 
    {
        if(p==NULL)
        {
            p=new(node);
            strcpy(p->info,string);
      
      
      p->left=NULL;
            p->right=NULL;
        }
        else if(strcmp(string,p->info) < 0)
        {
            insert(p->left,  string);
        }
        else   insert(p->right, string);
    }  // You were missing an ending bracket, add this
    void inorder(node *p)
    {
        if(p!=NULL)
        {
            inorder(p->left);
            cout<<p->info<<"  "<<endl;
            inorder(p->right);
        }
    }
    void preorder(node *p)
    {
     
     if(p!=NULL)
     {
      cout<<p->info<<"  "<<endl;
      preorder( p->left);
      preorder(p->right);
     }
    }
    void leafdisplay(node *p)
    {
     if(p->left !=NULL  && p->right !=NULL)
     {
      leafdisplay(p->left);
      leafdisplay(p->right);
     }
     cout<<p->info<<endl;
    }
    int main() // main should always return an int
    {
        node *root=NULL;
     char string[12];
     
     for(int i=0; i<12; ++i)
     {
      cout<<"Enter the value for your node: ";
       cin.getline(string, 11, '\n');
       insert(root, string);
     
       // Your insert function takes two parameters but you only provide one
     }
     inorder(root);
     cout<<endl;
     preorder(root);
     cout<<endl;
     leafdisplay(root);
     
     return 0;
    }
    apr
    aug
    dec
    feb
    january
    jul
    jun
    mar
    may
    nov
    oct
    sep


    feb
    jun
    may
    mar
    january
    Press any key to continue
    so whats up with this leaf function is the logic okay here or did I miss something

  2. #2
    OCD script writer syrel's Avatar
    Join Date
    Sep 2004
    Posts
    12
    Code:
    void leafdisplay(node *p)
    {
     if(p->left !=NULL  && p->right !=NULL)
     {
      leafdisplay(p->left);
      leafdisplay(p->right);
     }
     cout<<p->info<<endl; // this statement will display all nodes regardless, u dont need this
    
    //add an ELSE IF statement to display the value of p->info when it hits a leaf
    
    }
    (3.0 Units of C++ Data Structures) - (Lab Time) = Death

  3. #3
    Registered User
    Join Date
    Apr 2003
    Posts
    78

    where though

    Where should I put an else if statement in this problem to get it working

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > if(p->left !=NULL && p->right !=NULL)
    Yeah, you missed the possibility that one of the branches could be NULL without the other branch being NULL.
    So you only print nodes which have both children present.

  5. #5
    Registered User
    Join Date
    Apr 2003
    Posts
    78

    okay friends how about a small hint

    okay buds I give up can anybody just send me in the right direction at all with this whole leaf thing. I'm lost all of the algorithms I've tried fail miserably. So please be merciful and throw me a bone here.

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Code:
      if ( p->left ) leafdisplay(p->left);
      if ( p->right ) leafdisplay(p->right);
    Did you try this?

  7. #7
    Registered User
    Join Date
    Apr 2003
    Posts
    78

    tried it but not sure in what context though

    I did try that bit of code but I'm not to sure in what context I'm supposed to use it feel free to fill in the blanks where neccessary
    Code:
    #include <iostream>
    #include <string>
    using namespace std;
    struct node
    {
        char info[12];
        node *left;
        node *right;
    };
    void twochildren(node *p);  
    
    void leafdisplay(node *p);  
    
    void inorder(node *p); //inorder recursive function      
    					   //to show months in alphabetical order
    
    void insert(node *&p, char string[12]);//insert function to insert 
    									   //nodes in binary tree
    
    void insert(node *&p, char string[12]) 
    {
        if(p==NULL)
        {
            p=new(node);
            strcpy(p->info,string);
    		p->left=NULL;
            p->right=NULL;
        }
        else if(strcmp(string,p->info) < 0)
        {
            insert(p->left,  string);
        }
        else   insert(p->right, string);
    }  
    
    void inorder(node *p)
    {
        if(p!=NULL)
        {
            inorder(p->left);
            cout<<p->info<<"  "<<endl;
            inorder(p->right);
        }
    }
    
    void twochildren(node *p)
    {
    	if(p->left !=NULL  && p->right !=NULL)
    	{
    	twochildren(p->left);
    	twochildren(p->right);
    
    	cout<<p->info<<endl;
     
    	}
    }
    
    void leafdisplay(node *p)
    {
    	if ( p->left ) leafdisplay(p->left);
        if ( p->right ) leafdisplay(p->right);
    	//what next after these statements
    
    }
    int main() 
    {
        node *root=NULL;
     char string[12];
     
     for(int i=0; i<12; ++i)
     {
      cout<<"Enter the value for your node: ";
    
      cin.getline(string, 11, '\n');
       insert(root, string);
     
       
     }
     inorder(root);
     cout<<endl;
     
     twochildren(root);
     leafdisplay(root);
     
     return 0;
    }

  8. #8
    OCD script writer syrel's Avatar
    Join Date
    Sep 2004
    Posts
    12
    u just need to consider the important options. for leaves, you are concerned ONLY with those nodes that do not have any children. anything else is irrelevant.
    Code:
    void leafdisplay(node *p)
    {
    	if(p->left ==NULL && p->right ==NULL) // if both left and right are NULL, the node is a leaf	
            {
    		cout<<p->info;  //  display the node
    	}
    	else if (p->left==NULL&&p->right!=NULL)
    		leafdisplay(p->right); // if left is NULL, but right is not, then go further down the right
    	else if(p->left!=NULL&&p->right==NULL)
    		leafdisplay(p->left); // if right is NULL, but left is not, then go further down the LEFT	
            else if(p->left!=NULL&&p->right!=NULL)
    		leafdisplay(p->left); // if both are not NULL, then keep moving down the list WIHTOUT displaying the INFO value		
            leafdisplay(p->right);
    }
    notice how each ELSE IF statement covers the possibilities that your BST will encounter, hope that helps...even though it's 2am and u have class at 10....see ya there
    Last edited by syrel; 11-30-2004 at 11:43 AM.
    (3.0 Units of C++ Data Structures) - (Lab Time) = Death

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM