complete binary tree using an array help
 

This is what I have to do
We will initialize the tree by hard coding the values illustrated below. You will need to write, test and execute a driver program that will use the complete binary tree implementation.

// this will initialize the tree node values
treenodes[0]=5;
treenodes[1]=10;
treenodes[2]=2;
treenodes[3]=5;
treenodes[4]=7;
treenodes[5]=12;
treenodes[6]=3;
treenodes[7]=9;
treenodes[8]=8;
treesize=9;
print leftchild(3);
print height();
print isleaf(7);
print isleaf(2);
print parent(5);
traverseinorder();
This is what I got:

// CPP btree.cpp : Defines the entry point for the console application.

//



#include "stdafx.h"



class BTree 

{

public:

        int treenodes[1000];  // structure to store the tree nodes values

        

        int size;  // the number of nodes in the tree



        BTree(void);  // the "constructor"



        bool isleaf(int nodeindex);  // returns true if the node is a leaf

        int parent(int nodeindex);  // returns the index of the parent

        int leftchild(int nodeindex);  // returns the index of the left child

        int rightchild(int nodeindex);  // returns the index of the right child



        int height();  // returns the height of the tree

        int traverseinorder(int);  // a recursive function to print the nodes values based on an inorder traversal

};



bool BTree::isleaf(int nodeindex) //returns true if the node is a leaf

{

    return (BTree::leftchild(nodeindex)==NULL && BTree::rightchild(nodeindex)==NULL) ;

}

 

int BTree::parent(int nodeindex)  // returns the index of the parent

{

        int rv =0; 



    rv = (nodeindex - 1) / 2; 

    if (rv >= size)  

        rv = -1 ;



    return rv ;

}



int BTree::leftchild(int nodeindex)  // returns the index of the left child

{

    int rv =0; 



    rv = (nodeindex +1) *2 - 1; 

    if (rv >= size)  

        rv = -1 ;



    return rv ;

}



int BTree::rightchild(int nodeindex)  // returns the index of the right child

{

    int rv =0; 



    rv = (nodeindex +1) * 2; 

    if (rv <= size)  

        rv = -1 ;



    return rv ;

}



int BTree::traverseinorder(int nodeindex)  // a recursive function to print the nodes values based on an inorder traversal

{

    if (nodeindex == -1)  return -1 ;

    return traverseinorder(leftchild(nodeindex)) ;

    

    //print the treenode values 

    cout << "Tree node " << nodeindex << " = " << treenodes[nodeindex] << endl;



    traverseinorder(rightchild(nodeindex)); 

}

 // end traverseinorder()



int BTree::height()

{

    return 0;

}  



int main(int argc, char* argv[])

{

    BTree tree1;



        tree1.treenodes[0]=5;

        tree1.treenodes[1]=10;

        tree1.treenodes[2]=2;

        tree1.treenodes[3]=5;

        tree1.treenodes[4]=7;

        tree1.treenodes[5]=12;

        tree1.treenodes[6]=3;

        tree1.treenodes[7]=9;

        tree1.treenodes[8]=8;



        //set the size here.  size is a member of the bTree class so we need our object.member syntax

        tree1.size = 9;



        cout << "The left child of node 3 is:  " << tree1.leftchild(3) << endl;

        //cout << "The height of the tree is:    " << tree1.height() << endl;

        cout << "The node 7 is a leaf:         " << tree1.isleaf(7) << endl;

        cout << "The node 2 is a leaf:         " << tree1.isleaf(2) << endl;

        cout << "The parent of node 5 is:      " << tree1.parent(5) << endl;



        cout << "Values for inorder traversal: " <<  endl;

        cout << tree1.traverseinorder(0);



        return 0;

}

If I put in the Btree(void); it get CPP btree error LNK2019: unresolved external symbol "public: __thiscall BTree::BTree(void)" (??0BTree@@QAE@XZ) referenced in function _main
Ok so I take it out. With it out I have a few problems with the inordertraversal. One if I take out the search of the rightchild it works. If I put in the rightchild it gives me really wierd values. I even tried to take out the left and all I get on the right in 0 = 5? This tells me I'm getting a rightside tree. I still don't have the height done either.

Re: complete binary tree using an array help
 

I solved the height

int BTree::height()

{

    

    return sizeof(leftchild(0));

}

Re: complete binary tree using an array help
 

Ok I took care of the overload error by adding

BTree::BTree(void)  // builds the "constructor"

{

    for(int i = 0; i < 1000; ++i) treenodes[i] = -1;

}

But the inorder traversal still has a problem. I don't think it is the traversal but something with how the right side is not being built right. If I take out the traverseinorder(rightchild(nodeindex)); then the left side displays perfect to the root. If I run the traverseinorder(rightchild(nodeindex)); only I get only the root.

Re: complete binary tree using an array help
 

// CPP btree.cpp : Defines the entry point for the console application.

//



#include "stdafx.h"



class BTree 

{

public:

        int treenodes[1000];  // structure to store the tree nodes values

        

        int size;  // the number of nodes in the tree

        int count;            // the number of filled nodes in the tree

        int level;            // the current depth



        BTree(void);  // the "constructor"



        bool isleaf(int nodeindex);  // returns true if the node is a leaf

        int parent(int nodeindex);  // returns the index of the parent

        int leftchild(int nodeindex);  // returns the index of the left child

        int rightchild(int nodeindex);  // returns the index of the right child



        int height();  // returns the height of the tree

        int traverseinorder(int);  // a recursive function to print the nodes values based on an inorder traversal

};



BTree::BTree(void)  // builds the "constructor"

: size(sizeof(treenodes)/sizeof(int))

    , count(0)

    , level(0)

{

    for(int i = 0; i < size; ++i)

        treenodes[i] = -1;   // set all nodes empty

}



bool BTree::isleaf(int nodeindex) //returns true if the node is a leaf

{

    return leftchild(nodeindex)==-1 && rightchild(nodeindex)==-1;

}

 

int BTree::parent(int nodeindex)  // returns the index of the parent

{

    int rv = (nodeindex - 1) / 2;

   

    return (rv >= size || treenodes[rv] == -1)? -1 : rv;

}



int BTree::leftchild(int nodeindex)  // returns the index of the left child

{

    int rv = (nodeindex +1) *2 - 1;

   

    return (rv >= size || treenodes[rv] == -1)? -1 : rv;

}



int BTree::rightchild(int nodeindex)  // returns the index of the right child

{

    int rv = (nodeindex +1) * 2;

   

    return (rv >= size || treenodes[rv] == -1)? -1 : rv;

}



int BTree::traverseinorder(int nodeindex)  // a recursive function to print the nodes values based on an inorder traversal

{

    if (nodeindex == -1)  return -1 ;

        traverseinorder(leftchild(nodeindex));



     //print the treenode values

     cout << "Tree node " << nodeindex << " = " << treenodes[nodeindex] << endl;



     traverseinorder(rightchild(nodeindex)); 

}

 // end traverseinorder()



int BTree::height()

{

    return level;

}  



int main(int argc, char* argv[])

{

    BTree tree1;



        tree1.treenodes[0]=5;

        tree1.treenodes[1]=10;

        tree1.treenodes[2]=2;

        tree1.treenodes[3]=5;

        tree1.treenodes[4]=7;

        tree1.treenodes[5]=12;

        tree1.treenodes[6]=3;

        tree1.treenodes[7]=9;

        tree1.treenodes[8]=8;



        //set the size here.  size is a member of the bTree class so we need our object.member syntax

        tree1.size = 9;



        cout << "The left child of node 3 is:  " << tree1.leftchild(3) << endl;

        cout << "The height of the tree is:    " << tree1.height() << endl;

        cout << "The node 7 is a leaf:         " << tree1.isleaf(7) << endl;

        cout << "The node 2 is a leaf:         " << tree1.isleaf(2) << endl;

        cout << "The parent of node 5 is:      " << tree1.parent(5) << endl;



        cout << "Values for inorder traversal: " <<  endl;

        tree1.traverseinorder(0);



        return 0;

}