Construct a binary tree
Below are several attempts at a program to build a binary tree. The InsertNode procedure does the real work. The ViewTree procedure builds an output string that allows you to see the values of the pointers at any time during the construction of the tree.
The first version, InsertNode1, is a rather clumsy attempt which tries to deal with each node separately. It is however worth inspection because it illustrates what the program ultimately needs to achieve, and how it should go about it.
The second version, InsertNode2, makes use of a loop to deal with the insertion of a new node. However, if you step through this code and watch the contents of the arrays, you can see it assume the arrays are 1 based. This means the element zero of each array remains unused. It works, but it’s not ideal.
The third version, InsertNode3, is the best of the three iterative implementations below. It makes use of a loop to deal with the insertion of a new node but does not leave element 0 of any array unused. Notice how the exit condition is at the bottom of the Do Loop construct.
The fourth version shown here, Insert_Node takes a recursive approach. It treats every new node as it it were a root.
Public Class Form1
Dim aData(9) As String
Dim aLeft_Pointer(9) As Integer
Dim aRight_Pointer(9) As Integer
Dim iPosition As Integer
Private Sub NewItem_Click(sender As Object, e As EventArgs) Handles NewItem.Click
Dim stNewItem As String
stNewItem = Me.TextBox1.Text
Call InsertNode1(stNewItem)
Me.TextBox1.Text = ""
Me.TextBox1.Select()
End Sub
Private Sub ViewTree_Click(sender As Object, e As EventArgs) Handles ViewTree.Click
Dim x As Integer
Dim strOut As String
For x = 0 To 9
strOut = strOut & "Data: " & aData(x) & " " &
"LP: " & aLeft_Pointer(x) & " " &
"RP: " & aRight_Pointer(x) & vbNewLine
Next x
MsgBox(strOut)
End Sub
Sub InsertNode1(NewItem As String)
iPosition = iPosition + 1
'insert root node, easy!
If iPosition = 1 Then
aData(1) = NewItem
aLeft_Pointer(1) = 0
aRight_Pointer(1) = 0
End If
'insert second node
If iPosition = 2 Then
aData(2) = NewItem
If NewItem < aData(1) Then
aLeft_Pointer(1) = 2
ElseIf NewItem > aData(1) Then
aRight_Pointer(1) = 2
End If
End If
'insert third node
If iPosition = 3 Then
aData(3) = NewItem
If NewItem < aData(1) And aLeft_Pointer(1) = 0 Then
aLeft_Pointer(1) = 3
Exit Sub
End If
If NewItem < aData(1) And NewItem < aData(2) Then
aLeft_Pointer(2) = 3
Exit Sub
Else
aRight_Pointer(2) = 3
Exit Sub
End If
If NewItem > aData(1) And aRight_Pointer(1) = 0 Then
aRight_Pointer(1) = 3
Exit Sub
End If
If NewItem > aData(1) And NewItem > aData(2) Then
aRight_Pointer(2) = 3
Exit Sub
Else
aLeft_Pointer(2) = 3
Exit Sub
End If
End If
'***NOW THIS IS GETTING SILLY!!!***************
'***TIME TO START THINKING ABOUT ANOTHER APPROACH*****
End Sub
Sub InsertNode2(Data As String)
'works as if using 1 based arrays, for simplicity
'but element zero of each array remains unused
Dim ptr As Integer
ptr = 1 'node pointer
iPosition = iPosition + 1
aData(iPosition) = Data
If iPosition = 1 Then 'root node
aLeft_Pointer(iPosition) = 0
aRight_Pointer(iPosition) = 0
Else
'scan the tree
Do Until ptr = 0
If Data > aData(ptr) Then
If aRight_Pointer(ptr) = 0 Then
aRight_Pointer(ptr) = iPosition
ptr = 0
Else
ptr = aRight_Pointer(ptr)
End If
ElseIf Data < aData(ptr) Then
If aLeft_Pointer(ptr) = 0 Then
aLeft_Pointer(ptr) = iPosition
ptr = 0
Else
ptr = aLeft_Pointer(ptr)
End If
End If
Loop
End If
End Sub
Sub InsertNode3(Data As String)
'works properly with zero based arrays
Dim ptr As Integer
ptr = 0 'root node is postion 0
'iPosition = iPosition + 1 'moved to after loop so it starts at 0 for root
aData(iPosition) = Data
If iPosition = 0 Then 'root node is at postion 0
aLeft_Pointer(iPosition) = 0
aRight_Pointer(iPosition) = 0
Else
'scan the tree
Do 'exit condition i.e. ptr=0 at bottom of loop so checks the root
If Data > aData(ptr) Then
If aRight_Pointer(ptr) = 0 Then
aRight_Pointer(ptr) = iPosition
ptr = 0
Else
ptr = aRight_Pointer(ptr)
End If
ElseIf Data < aData(ptr) Then
If aLeft_Pointer(ptr) = 0 Then
aLeft_Pointer(ptr) = iPosition
ptr = 0
Else
ptr = aLeft_Pointer(ptr)
End If
End If
Loop Until ptr = 0
End If
iPosition = iPosition + 1
End Sub
Sub Insert_Node(root As Integer, Data As String)
'This is approach treats each node as a root, and this procedure calls itself
'Items are numbered from 0
'create the root node
If iPosition = 0 Then
aData(0) = Data
aLeft_Pointer(0) = 0
aRight_Pointer(0) = 0
iPosition = 1 'ready for next item
Exit Sub
End If
'left hand sub-tree search
If Data < aData(root) Then
If aLeft_Pointer(root) = 0 Then
'insert new terminal node here
aData(iPosition) = Data
aLeft_Pointer(iPosition) = 0
aRight_Pointer(iPosition) = 0
'update root pointer
aLeft_Pointer(root) = iPosition
iPosition = iPosition + 1
Else
Call Insert_Node(aLeft_Pointer(root), Data) 'this is were the root becomes another root
End If
End If
'Right hand sub-tree search
If Data > aData(root) Then
If aRight_Pointer(root) = 0 Then
'insert new terminal node here
aData(iPosition) = Data
aLeft_Pointer(iPosition) = 0
aRight_Pointer(iPosition) = 0
'update root pointer
aRight_Pointer(root) = iPosition
iPosition = iPosition + 1
Else
Call Insert_Node(aRight_Pointer(root), Data)
End If
End If
End Sub
End Class