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.

I solved the height

``````int BTree::height()
{

return sizeof(leftchild(0));
}``````

``````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.

``````// 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;
}``````
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.