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....unfortunate
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!
James
This Question has been solved and asker verified All Experts Exchange premium technology solutions are available to subscription members.
Experts Exchange has been collecting answers to technology questions since 1996…3 million and counting! If you have a question, chances are we already have your answer.
If you can't find the exact answer you're looking for, ask our exclusive community of 50,000 experts. You’ll get a personalized answer from a trusted professional.
Thousands of free tech tips, tricks, how-to’s and tutorials are available in our peer reviewed articles section. See for yourself how smart our experts are, no login required.
Save solutions to your questions, answers you’ve discovered through searching plus helpful articles in your personal knowledgebase for easy future access.
Access the answers to your technology questions today.
30-day free trial. Register in 60 seconds.
Members of the expert community talk about why the experience at Experts Exchange is different than what you will find anywhere else.
Try it out and discover for yourself.
30-day free trial. Register in 60 seconds.
Join the community of experts here and help other tech pros by answering question in your area of expertise. You can earn FREE access to all Experts Exchange's premium features and resources.
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.u
teh sorting algorithm is explained in
http://www.iti.fh-flensbur
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
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.
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++?
==========================
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).Ke
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
go to link http://www.fortunecity.com
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
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).Ke
// 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].
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()
{
Add(1,1000);
Add(2,2000);
Add(3,3000);
RebuildHeap(0);
// TODO: Add your control notification handler code here
}
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
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
Business Accounts
Answer for Membership
by: avizitPosted on 2004-08-28 at 22:30:18ID: 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/ref