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:

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.

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

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!

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.

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.

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?

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

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.

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

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

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.

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

Work with freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely, and get projects done right.

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