Const XGAP = 60
Const YGAP = 120

Dim Wid As Single
Dim Hgt As Single


Dim Root As SortNode


Dim MaxBox As Integer



Private Sub InsertItem(node As SortNode, new_value As Integer)
Dim child As SortNode

If node Is Nothing Then

Set node = New SortNode
node.Value = new_value
MaxBox = MaxBox + 1
Load NodeLabel(MaxBox)
Set node.Box = NodeLabel(MaxBox)
With NodeLabel(MaxBox)
.Caption = Format$(new_value)
.Visible = True
End With
ElseIf new_value <= node.Value Then
' Branch left.
Set child = node.LeftChild
InsertItem child, new_value
Set node.LeftChild = child
Else
' Branch right.
Set child = node.RightChild
InsertItem child, new_value
Set node.RightChild = child
End If
End Sub

Private Sub DeleteItem(node As SortNode, target_value As Integer)
Dim target As SortNode
Dim child As SortNode
If node Is Nothing Then
Beep
MsgBox "Item " & Format$(target_value) & _
" is not in the tree."
Exit Sub
End If

If target_value < node.Value Then

Set child = node.LeftChild
DeleteItem child, target_value
Set node.LeftChild = child
ElseIf target_value > node.Value Then

Set child = node.RightChild
DeleteItem child, target_value
Set node.RightChild = child
Else
' This is the target.
Set target = node
If target.LeftChild Is Nothing Then
' Replace target with its right child.
Set node = node.RightChild
ElseIf target.RightChild Is Nothing Then
' Replace target with its left child.
Set node = node.LeftChild
Else
'
Set child = node.LeftChild
ReplaceRightmost node, child
Set node.LeftChild = child
End If
End If
End Sub


Private Sub ReplaceRightmost(target As SortNode, repl As SortNode)
Dim old_repl As SortNode
Dim child As SortNode

If Not (repl.RightChild Is Nothing) Then
' Move farther down to the right.
Set child = repl.RightChild
ReplaceRightmost target, child
Set repl.RightChild = child
Else

Set old_repl = repl


Set repl = repl.LeftChild


Set old_repl.LeftChild = target.LeftChild
Set old_repl.RightChild = target.RightChild
Set target = old_repl
End If
End Sub

Private Sub CmdAdd_Click()
Dim new_value As Integer
Dim g As Integer

new_value = CInt(ValueText.Text)
InsertItem Root, new_value
DisplayTree
ValueText.Text = ""
ValueText.SetFocus
End Sub

Private Sub CmdRemove_Click()
Dim target_value As Integer

target_value = CInt(ValueText.Text)
DeleteItem Root, target_value
11
ValueText.Text = ""
ValueText.SetFocus
End Sub


Private Sub DisplayNode(node As SortNode, xmin As Single, ByVal y As Single)
Dim x1 As Single
Dim y1 As Single
Dim child As SortNode

If node Is Nothing Then Exit Sub


y1 = y + Hgt + YGAP
x1 = xmin
Set child = node.LeftChild
If child Is Nothing Then
x1 = x1 + Wid
Else
DisplayNode child, x1, y1
End If

Set child = node.RightChild
If child Is Nothing Then
If Not (node.LeftChild Is Nothing) _
Then x1 = x1 + Wid + XGAP
Else
x1 = x1 + XGAP
DisplayNode child, x1, y1
End If


node.Box.Move (xmin + x1) / 2 - Wid / 2, y
node.Box.Visible = True
xmin = x1
End Sub


Private Sub DisplayTree()
Dim xmin As Single

xmin = 0
DisplayNode Root, xmin, NodeLabel(0).Top
Refresh
End Sub


Private Sub DrawLines(node As SortNode)
Dim x As Single
Dim y As Single
Dim child As SortNode

If node Is Nothing Then Exit Sub

x = node.Box.Left + node.Box.Width / 2
y = node.Box.Top + node.Box.Height / 2

DrawLines node.LeftChild
DrawLines node.RightChild


Set child = node.LeftChild
If Not (child Is Nothing) Then _
Line (x, y)- _
(child.Box.Left + child.Box.Width / 2, _
child.Box.Top + child.Box.Height / 2)

Set child = node.RightChild
If Not (child Is Nothing) Then _
Line (x, y)-( _
child.Box.Left + child.Box.Width / 2, _
child.Box.Top + child.Box.Height / 2)
End Sub
Function MaxDepth(t As SortNode) As Integer
Dim D1 As Integer, D2 As Integer

If Not t.LeftChild Is Nothing Then
D1 = MaxDepth(t.LeftChild)
End If

If Not t.RightChild Is Nothing Then
D2 = MaxDepth(t.RightChild)
End If

MaxDepth = IIf(D1 > D2, D1 + 1, D2 + 1)
End Function


Private Sub Command1_Click()
Dim t As New SortNode
Set t.LeftChild = New SortNode
Set t.RightChild = New SortNode
Set t.RightChild.LeftChild = New SortNode

MsgBox MaxDepth(t)
End Sub

Private Sub Form_Load()
Wid = NodeLabel(0).Width
Hgt = NodeLabel(0).Height

DisplayTree
End Sub

Private Sub Form_Paint()
DrawLines Root
End Sub


Private Sub Form_QueryUnload(Cancel As Integer, UnloadMode As Integer)
Set Root = Nothing
Unload Me
End Sub

Private Sub mnuFileExit_Click()
Set Root = Nothing
Unload Me
End Sub

Private Sub mnuHelpAbout_Click()
Dim txt As String

txt = "This program allows you to manipulate a sorted binary tree." & vbCrLf & vbCrLf
txt = txt & "Enter a number and click the Add button to add an item to the tree." & vbCrLf & vbCrLf
txt = txt & "Enter a number and click the Remove button to remove an item from the tree."

MsgBox txt, vbOKOnly, "Help About ... Treesort"
End Sub

Private Sub ValueText_Change()
CmdAdd.Enabled = (ValueText.Text <> "")
CmdRemove.Enabled = CmdAdd.Enabled
End Sub

Option Explicit

Public LeftChild As SortNode
Public RightChild As SortNode
Public Value As Integer
Public inf As Integer
Public z_next As SortNode
Public Box As Label

Public Function DeleteDescendant(target As SortNode) As Boolean
If LeftChild Is target Then
Set LeftChild = Nothing
DeleteDescendant = True
Exit Function
End If
If RightChild Is target Then
Set RightChild = Nothing
DeleteDescendant = True
Exit Function
End If

If Not (LeftChild Is Nothing) Then
If LeftChild.DeleteDescendant(target) Then
DeleteDescendant = True
Exit Function
End If
End If
If Not (RightChild Is Nothing) Then
If RightChild.DeleteDescendant(target) Then
DeleteDescendant = True
Exit Function
End If
End If
End Function

Public Function FindNode(ctl As Label) As SortNode
Dim node As SortNode


If ctl = Box Then
Set FindNode = Me
Exit Function
End If


If Not LeftChild Is Nothing Then
Set node = LeftChild.FindNode(ctl)
If Not (node Is Nothing) Then
Set FindNode = node
Exit Function
End If
End If


If Not (RightChild Is Nothing) Then
Set node = RightChild.FindNode(ctl)
If Not (node Is Nothing) Then
Set FindNode = node
Exit Function
End If
End If

Set FindNode = Nothing
End Function


'Private Sub Class_Terminate()
' Unload Box
'End Sub