binary tree complete check

This is a discussion on binary tree complete check within the C++ Programming forums, part of the General Programming Boards category; Ok, I'm working on a binary tree class that needs to have a member function that determines if the tree ...

  1. #1
    GA ichijoji's Avatar
    Join Date
    Nov 2002
    Posts
    179

    binary tree complete check

    Ok, I'm working on a binary tree class that needs to have a member function that determines if the tree is complete. The tree is complete if it's balanced and all the nodes on the bottom level are on the left. The tree is balanced if the bottom nodes are no more than one level away from each other. I made this to check if the tree is balanced:
    Code:
    bool tree_t::isbalanced() {
      if (root == NULL)
        return true;
      else
        return onisbalanced(root,1,getnumlevels());
    }
     
    bool tree_t::onisbalanced(node_t* node, int level, int numlevels) {
      return (node->left != NULL &&
             onisbalanced(node->left,level+1,numlevels)) &&
             (node->right != NULL &&
             onisbalanced(node->right,level+1,numlevels)) &&
             !(node->left == NULL &&
             node->right == NULL && level < numlevels - 1);
    }
    This runs through all the nodes recursively and checks that only nodes at the bottom two levels can have no children. This seems like it should work fine to me, but it always says that the tree is unbalanced. I get the feeling there's a really simple way to do this that I'm missing, or maybe I just have some basic logic flaw.
    Last edited by ichijoji; 11-09-2004 at 11:34 AM.
    Illusion and reality become impartiality and confidence.

  2. #2
    #include<xErath.h> xErath's Avatar
    Join Date
    Jun 2004
    Posts
    722
    Well this isn't a trivial task so 1st think well on the problem. i've already been assigned once to write a function to verify if a tree is complete but i did do it then. But after thinking about the problem is easy.
    You only need to go through the node that go the botom most where the diference in heigth occurs.
    Consider these trees
    Code:
           o                o        
         /   \            /   \      
       o       o        o       o    
      / \     / \      / \     / \   
     o   o   o   o    o   o   o   o  
    / \ / \ /        / \ /  
    o o o o o        o o o
    You start by looking at the root node. What you do in a node is the same for all. In a node you look to the left one and then to the right, and check both height for those nodes.
    1# If the height from the left one isn't the same or only one unit larger than the height from the right side, then the tree isn't complete.
    2.1# If the height matches (case 1) the left node should contain a sub tree with all nodes*, and the control passes to the right node to check if that one is complete
    2.2# If the height is diferent (case2) then the right sub tree must contain all nodes, and the control passes to the left node
    3# the testing ends when both children are null ( to simplify )

    *-> I mean a tree with all nodes when it has 2^(height+1)-1 nodes, or if all levels are all fill.

    Now using this logic where a example of iterations on the 2nd tree:
    Code:
           o                                            
         /   \                                          
       o       o     control goes     o    control goes 
      / \     / \    left node       / \   to right node
     o   o   o   o                  o   o               
    / \ /                          / \ /                
    o o o                          o o o                
    
    
    
                                                         
                                                        
                     control goes      
                     left node         
         o                         
        /                          
        o                          o
    So now in pesudo-code
    Code:
    iscomplete
    	check nulls for left and rght
    	get heights
    	compare heights: is they're valid
    
    	get sizes
    	if left.height == right.height
    		check size for left subtree
    		return right.iscomplete
    	else if left.height == right.height-1
    		check size for left subtree
    		return right.iscomplete
    	//the end
    And finally in C++
    Code:
    bool Node::isComplete(){
    	if(!left && !right)
    		return true;
    
    	int hl = left?left->heigth():-1;
    	int hr = right?right->heigth():-1;
    
    	if(hl != hr || hl != hr+1)
    		return false;
    
    	int sl = left?left->size():0;
    	int sr = right?right->size():0;
    
    	if(hr == hl){//case1
    		int fullsz = 2*pow(hl+1)-1
    		if( fullsz != sl)
    			return false;
    		return right->isComplete();
    	}else{
    		int fullsz = 2*pow(hr+1)-1
    		if( fullsz != sr)
    			return false;
    		return left->isComplete();
    	}
    }
    You're not using templates for the data??
    Last edited by xErath; 11-09-2004 at 12:08 PM.

  3. #3
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Your return statement has a logic flaw in it. When you hit a leaf
    Code:
     (node->left != NULL && onisbalanced(node->left,level+1,numlevels))
    will evaluate to false, meaning the whole return statement will automatically evaluate to false. This of course will make all previous recursive calls false. Check to see if its a leaf node and return true if its within one of the tree height. THEN do the recursive call.

  4. #4
    GA ichijoji's Avatar
    Join Date
    Nov 2002
    Posts
    179
    Quote Originally Posted by xErath
    Code:
    		int fullsz = 2*pow(hl+1)-1
    Code:
    		int fullsz = 2*pow(hr+1)-1
    I'm a little confused about exactly what you mean by this. I thought the formula for the maximum size of a tree was 2*height - 1, but I put that in here and it doesn't work. I also tried pow(2,h_+1) and pow(h_+1,2), and those both produce bogus results too.
    Illusion and reality become impartiality and confidence.

  5. #5
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    How are you defining the height of a tree. If you use the following logic-- if there is a single node in the tree the tree has height zero. If there is 2 or three nodes in the tree then it has height 1. If there are 4 to seven nodes in the tree then it has height 2--then pow(2, (height + 1)) - 1 gives the number of possible nodes in the balanced binary tree. Alternatively, if a tree with one node has height 1, and a tree with 2 or 3 nodes has height 2, and a tree with 4 to 7 nodes has height 3, then pow(2, height) - 1 gives the number of possible nodes in the balanced binary tree.

  6. #6
    #include<xErath.h> xErath's Avatar
    Join Date
    Jun 2004
    Posts
    722
    Quote Originally Posted by ichijoji
    I'm a little confused about exactly what you mean by this. I thought the formula for the maximum size of a tree was 2*height - 1, but I put that in here and it doesn't work. I also tried pow(2,h_+1) and pow(h_+1,2), and those both produce bogus results too.
    Bah!! SIntax ERROR!!!
    Code:
    //....
    int fullsz = pow(2,hl+1)-1
    //....
    int fullsz = pow(2,hl+1)-1
    Note: e.g. a tree with height 3 has 1+2+4+8 nodes, or 2^(3+1)-1. Recall geometric progressions??

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. binary search tree help
    By noob2c in forum C++ Programming
    Replies: 6
    Last Post: 11-09-2003, 01:51 PM
  2. Binary tree search efficiency
    By ExCoder01 in forum A Brief History of Cprogramming.com
    Replies: 8
    Last Post: 10-23-2003, 10:11 PM
  3. binary tree node structure
    By Kirsten in forum C Programming
    Replies: 2
    Last Post: 04-26-2002, 08:02 PM
  4. read records fron file into a binary tree
    By Kirsten in forum C Programming
    Replies: 1
    Last Post: 04-23-2002, 02:48 PM
  5. Binary Search Tree...
    By D'oh in forum C++ Programming
    Replies: 2
    Last Post: 01-24-2002, 02:12 PM

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