determine if tree is strictly binary bst

This is a discussion on determine if tree is strictly binary bst within the C++ Programming forums, part of the General Programming Boards category; Hi, need a little help on this one. I need to write a member function to determine if my BST ...

  1. #1
    Registered User
    Join Date
    May 2009
    Posts
    5

    determine if tree is strictly binary bst

    Hi, need a little help on this one.
    I need to write a member function to determine if my BST is
    strictly binary or not. The function should do this through a
    series of if statements, and simply printing out a message.
    The complication is, it needs recursive calls, and I'm not too good
    with those.
    I've written the function, and it works, but it's printing a tree ahead of
    time, so there are several printouts when there supposed to be only one.

    Here is the function:



    void BST::strict() //this function is public to be called by main()
    {
    strict(theroot);
    }
    //


    //private functon, gets a pointer to tree node.
    //called by public strict().
    //Will determine if a tree is strictly binary
    //or not, and then rint a message.
    void BST::strict(Tnode *p)
    {

    bool ans;
    ans =false;

    if(p == NULL)

    ans = true;
    else if((p->right == NULL && p->left == NULL) || (p->right != NULL && p->left != NULL)){
    strict(p->left);
    strict(p->right);

    ans =true;
    }
    else if((p->right == NULL && p->left != NULL) || (p->right != NULL && p- >left == NULL)){
    ans =false;
    }

    //else
    // //cout<<"The tree is NOT strictly binary!!!"<<endl;
    // ans =2;


    if(ans ==true){
    cout<<"The tree is strictly binary!!!"<<endl;
    }
    else if(ans ==false){
    cout<<"The tree is NOT strictly binary!!!"<<endl;
    }


    }





    here is the output:



    Here is the 1st Tree traversal:
    INORDER:
    -3 1 10 54 97

    PREORDER:
    10 -3 1 97 54

    POSTORDER:
    1 -3 54 97 10

    Smalest item in the tree: -3
    Largest item in the tree: 97
    Largest item in left subtree: 1
    Smallest item in right subtree: 54

    The tree is NOT strictly binary!!!
    The tree is NOT strictly binary!!!
    The tree is strictly binary!!!




    Here is the 2nd Tree traversal:
    INORDER:
    7 10 20

    PREORDER:
    10 7 20

    POSTORDER:
    7 20 10

    Smalest item in the tree: 7
    Largest item in the tree: 20
    Largest item in left subtree: 7
    Smallest item in right subtree: 20

    The tree is strictly binary!!!
    The tree is strictly binary!!!
    The tree is strictly binary!!!
    The tree is strictly binary!!!
    The tree is strictly binary!!!
    The tree is strictly binary!!!
    The tree is strictly binary!!!




    Here is the 3rd Tree traversal:
    INORDER:
    0 1 15 19 20 20 30 81

    PREORDER:
    0 20 15 1 19 30 20 81

    POSTORDER:
    1 19 15 20 81 30 20 0

    Smalest item in the tree: 0
    Largest item in the tree: 81
    Largest item in left subtree: 0
    Smallest item in right subtree: 1

    The tree is NOT strictly binary!!!




    Here is the 4th Tree traversal:
    INORDER:
    1 3 4 5 6 8 10 11 13 15

    PREORDER:
    10 5 4 1 3 6 8 15 11 13

    POSTORDER:
    3 1 4 8 6 5 13 11 15 10

    Smalest item in the tree: 1
    Largest item in the tree: 15
    Largest item in left subtree: 8
    Smallest item in right subtree: 11

    The tree is NOT strictly binary!!!
    The tree is NOT strictly binary!!!
    The tree is strictly binary!!!
    The tree is NOT strictly binary!!!
    The tree is strictly binary!!!




    Here is the 5th Tree traversal:
    INORDER:


    PREORDER:


    POSTORDER:


    Smalest item in the tree:
    Largest item in the tree:
    Largest item in left subtree:
    Smallest item in right subtree:

    The tree is strictly binary!!!


    Press any key to continue . . .

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Huh? Is this true:
    a BST is strict if it's empty.
    a BST is strict if both left and right are strict.

    Assuming this is the definition, then writing a recursive function to solve the problem shouldn't be hard. However, whilst you have indeed written a recursive function, you are not using the return value from the left/right checks. The second else-if only needs to be an else, since the if-statement is always true if the other if's failed.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    Feb 2010
    Posts
    1
    This is a standalone function.... can easily be converted to member function
    Code:
    bool IsStrictlyBinary(Node* root) {
    
    	if(root->left == NULL && root->right == NULL)
    		return true;
    	else if ((root->left == NULL && root->right != NULL)  ||
    		(root->right == NULL && root->left != NULL)	)
    		return false;	
    	else
    		return ((IsStrictlyBinary(root->left))?IsStrictlyBinary(root->right):false);
    }

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,394
    Quote Originally Posted by learningToCode
    This is a standalone function.... can easily be converted to member function
    Thanks for your contribution, but this thread became dormant the day it began, in the first half of last year. If ashir30000 had responded with say, a problematic solution that was never corrected then perhaps you would be justified in resurrecting this thread, but as it stands I will just close it.

    By the way, this:
    Code:
    return ((IsStrictlyBinary(root->left))?IsStrictlyBinary(root->right):false);
    can be simplified to:
    Code:
    return IsStrictlyBinary(root->left) && IsStrictlyBinary(root->right);
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 10: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, 08:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

Tags for this Thread


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