complete binary tree using an array help

Question

schmidty169 2 Light Poster

20 Years Ago

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.

c++ data-structure

1 Contributor
3 Replies
580 Views
2 Days Discussion Span
Latest Post 20 Years Ago Latest Post by schmidty169

Dani AI

Generated 10 Months Ago

Good progress, — you tracked down the linker error (missing constructor) and cleaned up several problems. The remaining odd behavior comes from a few specific, common mistakes: mixing NULL with integer indices, returning too early from the recursive traversal, and an incorrect height calculation / inconsistent use of the size member. Fix those three and the traversal will behave predictably.

Key fixes and why they matter

Use a clear sentinel for “no child” (for example -1) and never compare integer child indices to NULL. NULL can be 0 on some platforms; you want a value that clearly means “no node” and is different from a valid index.
Parent formula needs a guard for the root. Check if (i <= 0) return -1; before computing (i-1)/2 — otherwise integer division of negatives leads to wrong results for index 0.
The inorder routine must not return the recursive call for the left subtree. Either make it void and just call traverse(left); print; traverse(right); or, if you return something, do the recursion and combine results rather than returning immediately.
Don’t print cout << traverseinorder(0) if the function itself prints; call it as a statement once its return type is void.

Small, safe helpers (examples you can drop in)

int parentIndex(int i, int capacity) {
    if (i <= 0) return -1;
    int p = (i - 1) / 2;
    return (p >= capacity /*or treenodes[p]==sentinel*/)? -1 : p;
}

int heightFromCount(int nodeCount) { // returns number of levels
    if (nodeCount == 0) return 0;
    int h = 0;
    while (nodeCount > 0) { ++h; nodeCount >>= 1; }
    return h;
}

Practical tips

Rename size to capacity and keep a separate count for actual filled nodes; that avoids confusion when filling only first N entries of a large array.
Always check bounds before indexing treenodes[rv].
Test with tiny trees (1 node, 2 nodes, full 3-level tree) and add a simple trace (print visited indices) to confirm recursion order.

Those changes will remove the “weird” right-side output and give you a correct height.

Reply to this topic

Be a part of the DaniWeb community

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

schmidty169 2 Light Poster · Answer 1 · 2006-07-17T06:53:18+00:00

I solved the height

int BTree::height()
{
    
    return sizeof(leftchild(0));
}

schmidty169 2 Light Poster · Answer 2 · 2006-07-18T00:56:36+00:00

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.

schmidty169 2 Light Poster · Answer 3 · 2006-07-19T08:57:10+00:00

// 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;
}