Implement a complete binary tree using an array

Posted on 2004-08-28
Last Modified: 2011-10-03
Ok.  I am willing to post a second 500 pointer to anyone who can assist me here.  I am a C++ dummy, so be kind.  I am trying to convert an algorithm from VB6 to C++, but I don't know where to start.  C++ is WAY out of my league.

Anyway...I have a program in VB that does the assigned task (an old homework problem from my VB classes, but is right along the same lines as what I'm trying to accomplish in C++).

The program performs a binary tree sort using an array.  The treesize is only 10, and the values will change from time to time, but for the moment let's assume the nodes are initialized as follows:

treesize=10; //as mentioned above

I need to have a program that'll utilize the int parent, int leftchild, and int rightchild to organize these ten values.  This is so vastly different from VB6 that I don't even know where to start.

I am trying to teach myself C++ and I'm using my VB code as a guideline to write C++ code.  Can anyone get me the source code that can perform this function?  Our C++ instructor for the college I work at recently had a heart attack, and is in the hospital and out of commission for a while.  They threw me into this position to "sub" for him being that I am the only other instructor with any background in programming....unfortunately, just the wrong kind (SQL and VB6).  Further...I am a networking guru.  I have tried adamantly to AVOID programming.  LOL.  Now, here I am...knee deep in it.

I've scoured the net and found a lot of code on arrays and BSTs, but can't really find one that will show me how to create a binary tree sort using an array.  I've got to sub for this guy for up to the next six weeks (unless the college can find a temp substitute sooner), so I am hoping someone here can help me out from time to time when I need it.

Thanks in advance!

Question by:jamesreddy
  • 4
  • 4
  • 2
  • +1
LVL 11

Expert Comment

ID: 11924488
Binary Trees are trees where every node has at most 2 child. The left child and the right child
So to implement a binary tree as an array

you take array[0] as the root of the binary tree

and its two child are  array[1] , --left child
                               array[2]  - right child

similarly array[1] as two child  left-> array[3] and right -> array[4]

so basically each node "i" has two children  the left child is array[2i +1 ] and right child is array[2i +2 ]

now you have to sort the binary tree

for representation also read "Arrayed Binary Trees" in


LVL 11

Expert Comment

ID: 11924498
for sorting  you have to convert the binary tree into a heap
the theory part is quite lengthy to type here so i will just give a link

teh sorting algorithm is explained in  with a java implementation .


Author Comment

ID: 11924534
While I appreciate the links, my problem is simply this...none of it makes sense to me yet.  I am at a complete loss at how to do this having no background in C++.  Can you supply the code and/or supply a link that can show me exactly how to write this out?  I understand the PREMISE of a binary tree sort and array, but the code is completely out of my league.  These students have a project due by Monday and I'm hoping that I can have the answer by then.  How do I write a binary tree sort using an array that will organize ten values such as the ones I have listed above?

This whole C++ thing has caught me completely off guard.

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

LVL 17

Expert Comment

ID: 11924787
You've been put into an impossible possition, which sounds very stressful. I'm sure it would be more valuable for the students if you taught them about networking instead. Alternatively, you need to change the format of your teaching to allow students to work through the problems and act as a kind of facilitator. Asking for lecture notes from EE the day before each lecture certainly won't cut the mustard. Good luck.
LVL 11

Expert Comment

ID: 11924800
plus telling bout heap and heapsort is going to be a bit difficult without being able to draw diagrams etc
hence i provided the link which had diagrams.


Author Comment

ID: 11925463
It's not an impossible position.  I just need someone to supply me with some code that can help me correct this project.  I need some basis to know if the students did this correctly so I can correct the work.  I'm just the fill-in until we get someone who can understand this stuff.  How hard can this be?  I can do it in VB easily.  Is C++ really that much more complicated?

Author Comment

ID: 11925601
Ok...I don't know if this will help.  Here is a code in VB that performs a similar function (from my old class I took bak in college).  I don't know if anyone knows VB in here, but how can I convert this to C++?

  MultiUse = -1  'True
  Persistable = 0  'NotPersistable
  DataBindingBehavior = 0  'vbNone
  DataSourceBehavior  = 0  'vbNone
  MTSTransactionMode  = 0  'NotAnMTSObject
Attribute VB_Name = "clsHeap"
Attribute VB_GlobalNameSpace = False
Attribute VB_Creatable = True
Attribute VB_PredeclaredId = False
Attribute VB_Exposed = False
Option Explicit

Private Type HeapItem
    Key As Variant
    Data As Variant
End Type

Dim Items() As HeapItem
Dim lSize As Long ' Number of items in the heap
Public Property Get Count() As Long
    Count = lSize
End Property

Private Sub RebuildHeap(ByVal Root As Long)
    Dim ChildIndex As Long
    Dim RightChildIndex As Long

    ChildIndex = 2 * Root + 1 ' Index of root's left child, if any
    If ChildIndex < lSize Then

        RightChildIndex = ChildIndex + 1 ' Index of right child, if any.

        If (RightChildIndex < lSize) And (Items(RightChildIndex).Key > Items(ChildIndex).Key) Then
            ChildIndex = RightChildIndex ' Index of larger child
        End If

        If Items(Root).Key < Items(ChildIndex).Key Then
            Dim Temp As HeapItem
            Temp = Items(Root)
            Items(Root) = Items(ChildIndex)
            Items(ChildIndex) = Temp

            RebuildHeap ChildIndex
        End If
    End If
End Sub

Public Function Remove() As Variant

    If lSize > 0 Then
        Remove = Items(0).Data
        lSize = lSize - 1
        Items(0) = Items(lSize)
        RebuildHeap 0
        ReDim Preserve Items(lSize)
        Remove = Empty ' Heap empty
    End If
End Function

Public Sub Add(ByVal Key As Variant, ByVal Data As Variant)

    ReDim Preserve Items(lSize) ' Make room for the new item.
    Items(lSize).Key = Key
    Items(lSize).Data = Data
    Dim Place As Long, Parent As Long
    Place = lSize
    Parent = (Place - 1) / 2
    Do While Parent >= 0 And (Items(Place).Key > Items(Parent).Key)
        ' swap Items(Place) and Items(Parent)
        Dim Temp As HeapItem
        Temp = Items(Parent)
        Items(Parent) = Items(Place)
        Items(Place) = Temp
        Place = Parent
        Parent = (Place - 1) / 2
    lSize = lSize + 1
End Sub

It's not exactly what these students are doing, but it's close enough for government work.  How can I perform the same function in C++?  I already understood I'd need to build a heap and what not, but after that....the code is where I'm dead.  C++ is so different....or is it?  I don't know.  Everywhere I've looked online suggest that C++ is more complicated.  While I can read code that I find online and guess at what it does, I cannot formulate it on my own.

In any event...if this is too complicated, then tell me.  I'm trying to have something for these guys this week.

LVL 11

Assisted Solution

avizit earned 200 total points
ID: 11926137
go to link

if you scroll down you have a link for a cpp program for heapsort using arrays for heaps.

the link to the program is
LVL 49

Accepted Solution

DanRollins earned 300 total points
ID: 11926625
Here is a litteral translation of your VB code into roughly-equivallent C++

//Private Type HeapItem
//    Key As Variant
//    Data As Variant
//End Type

//Dim Items() As HeapItem
//Dim lSize As Long ' Number of items in the heap
//Public Property Get Count() As Long
//    Count = lSize
//End Property

typedef struct {
      int nKey;   // the value that will indicate order
      int nData;  // the value that will be sorted
} HeapItem;

#define CNUM_MaxSize 100

HeapItem garItems[CNUM_MaxSize];  // for simplicity, let the array have 100 items
int      gnSize= 0;               // make make both of these global variables

//Private Sub RebuildHeap(ByVal Root As Long)
//    Dim ChildIndex As Long
//    Dim RightChildIndex As Long
//    ChildIndex = 2 * Root + 1 ' Index of root's left child, if any
//    If ChildIndex < lSize Then
//        RightChildIndex = ChildIndex + 1 ' Index of right child, if any.
//        If (RightChildIndex < lSize) And (Items(RightChildIndex).Key > Items(ChildIndex).Key) Then
//            ChildIndex = RightChildIndex ' Index of larger child
//        End If
//        If Items(Root).Key < Items(ChildIndex).Key Then
//            Dim Temp As HeapItem
//            Temp = Items(Root)
//            Items(Root) = Items(ChildIndex)
//            Items(ChildIndex) = Temp
//            RebuildHeap ChildIndex
//        End If
//    End If
//End Sub

void RebuildHeap( int nRootIdx )
      int nChildIdx;
      int nRightChildIdx;

      nChildIdx= (2 * nRootIdx) + 1; // Index of root's left child, if any
      if ( nChildIdx < gnSize ) {
            nRightChildIdx = nChildIdx + 1;   // Index of right child, if any.
            if ( (nRightChildIdx < gnSize) && (garItems[nRightChildIdx].nKey > garItems[nChildIdx].nKey) ) {
                  nChildIdx= nRightChildIdx; //  ' Index of larger child
            if ( garItems[nRootIdx].nKey < garItems[ nChildIdx].nKey ) {
                  HeapItem rTemp= garItems[ nRootIdx];
                  garItems[ nRootIdx]= garItems[ nChildIdx];
                  garItems[ nChildIdx]= rTemp;
                  RebuildHeap( nChildIdx ); // recursive call to "sort from here"

//Public Function Remove() As Variant
//    If lSize > 0 Then
//        Remove = Items(0).Data
//        lSize = lSize - 1
//        Items(0) = Items(lSize)
//        RebuildHeap 0
//        ReDim Preserve Items(lSize)
//    Else
//        Remove = Empty ' Heap empty
//    End If
//End Function

int Remove()
      int nRet= 0;
      if ( gnSize > 0 ) {
            nRet= garItems[0].nData;
            gnSize= gnSize - 1;
            garItems[0]= garItems[ gnSize ];
            RebuildHeap( 0 );
      else {
            nRet= 0;
      return nRet;

//Public Sub Add(ByVal Key As Variant, ByVal Data As Variant)
//    ReDim Preserve Items(lSize) ' Make room for the new item.
//    Items(lSize).Key = Key
//    Items(lSize).Data = Data
//    Dim Place As Long, Parent As Long
//    Place = lSize
//    Parent = (Place - 1) / 2
//    Do While Parent >= 0 And (Items(Place).Key > Items(Parent).Key)
//        ' swap Items(Place) and Items(Parent)
//        Dim Temp As HeapItem
//        Temp = Items(Parent)
//        Items(Parent) = Items(Place)
//        Items(Place) = Temp
//        Place = Parent
//        Parent = (Place - 1) / 2
//    Loop
//    lSize = lSize + 1
//End Sub

void Add( int nKeyVal, int nDataVal )
      garItems[ gnSize].nKey=  nKeyVal;
      garItems[ gnSize].nData= nDataVal;

      int nPlaceIdx, nParentIdx;
      nPlaceIdx= gnSize;
      nParentIdx = (nPlaceIdx - 1) / 2;

      while ( (nParentIdx >= 0) && (garItems[ nPlaceIdx].nKey > garItems[nParentIdx].nKey) ) {
            //  swap Items(Place) and Items(Parent)
            HeapItem rTemp= garItems[ nParentIdx ];

            garItems[ nParentIdx ]= garItems[ nPlaceIdx ];
            garItems[ nPlaceIdx ]= rTemp;

            nPlaceIdx= nParentIdx;
            nParentIdx= (nPlaceIdx - 1) / 2;

void CD24Dlg::OnButton1()

      // TODO: Add your control notification handler code here
LVL 49

Expert Comment

ID: 11926650
I cannot vouch for how well that program code works, but I think that it is accurate.  If the VB functions do what you want, then the C++ should do the same thing (I think :-).

IMO C++ is not any more complicated that BASIC for such "logic" tasks as this.  It *is* much more compicated for many things... especially interfacing to COM objects and for interactions with GUI, etc.  But that does not apply here.

The reason that all examples of C++ code appear to be complicated to a VB veteran is probably that most array sorting an manipulation examples you will see use pointers into the data while VB code uses the simpler concepts of array indexes.  C++ code ends up being more efficient, but harder to read and understand for VB programmers because the concept of a pointer is basically non-existant for VB programmers.

-- Dan

Author Comment

ID: 11927063
Ok avizit...that got me started.  Looking at the code on that site, I was able to start writing my own C++ equivalent.  Then Dan topped it off for me.  Thanks much for the help.  Hopefully, I won't be needing it again.  I'd like to avoid C++ if at all possible in the future.  Needless to say, I will be helping them find a suitable replacement this week so I can go back to what I do best.

Thanks again!


Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

685 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question