Solved

# Implement a complete binary tree using an array

Posted on 2004-08-28
1,284 Views
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:

treenodes[0]=3;
treenodes[1]=2;
treenodes[2]=23;
treenodes[3]=9;
treenodes[4]=5;
treenodes[5]=14;
treenodes[6]=21;
treenodes[7]=13;
treenodes[8]=17;
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.

James
0
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 http://www.gamedev.net/reference/programming/features/trees2/page2.asp

0

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

http://www.maths.abdn.ac.uk/~igc/tch/mx4002/notes/node60.html

teh sorting algorithm is explained in

http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/heap/heapen.htm  with a java implementation .

0

LVL 9

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.

James
0

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

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

0

LVL 9

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?
0

LVL 9

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++?

===========================================
BEGIN
MultiUse = -1  'True
Persistable = 0  'NotPersistable
DataBindingBehavior = 0  'vbNone
DataSourceBehavior  = 0  'vbNone
MTSTransactionMode  = 0  'NotAnMTSObject
END
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)
Else
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
Loop
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.

James
0

LVL 11

Assisted Solution

avizit earned 200 total points
ID: 11926137

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

the link to the program is

http://www.fortunecity.com/skyscraper/false/780/files/heapsort.cpp
0

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;
}
gnSize++;
}

void CD24Dlg::OnButton1()
{

RebuildHeap(0);

}
0

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
0

LVL 9

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!

James
0

## Featured Post

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…
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.