Attribute VB_Name = "BTrees"
'This code was written by Jorge H. Abarca Winkler
'Feel free to use it, but please give me some credit... :P

' Tec-Nico

Public Type BTNode
 Info(0) As Integer
 Type As String
 Level As Long
 Parent As Long
 ChildLeft As Long
 ChildRight As Long
End Type

Public Type BTree
 Name As String
 Node() As BTNode
 Root As Boolean
 Index As Long
 Height As Long
 Grade As Integer
End Type

Public Tree As BTree

Public Sub InOrden(n() As BTNode, num As Long)
If n(num).ChildLeft > 0 Then InOrden n(), n(num).ChildLeft
MsgBox "InOrden Tree(" & num & ") " & n(num).Info(0) 'Info
If n(num).ChildRight > 0 Then InOrden n(), n(num).ChildRight
End Sub

Public Sub PreOrden(n() As BTNode, num As Long)
MsgBox "PreOrden Tree(" & num & ") " & n(num).Info(0) 'Info
If n(num).ChildLeft > 0 Then PreOrden n(), n(num).ChildLeft
If n(num).ChildRight > 0 Then PreOrden n(), n(num).ChildRight
End Sub

Public Sub PostOrden(n() As BTNode, num As Long)
If n(num).ChildLeft > 0 Then PostOrden n(), n(num).ChildLeft
If n(num).ChildRight > 0 Then PostOrden n(), n(num).ChildRight
MsgBox "PostOrden Tree(" & num & ") " & n(num).Info(0) '.Info
End Sub

Public Sub InsertarN(Arbol As BTree, Data As Integer)
Dim FndNd As Long
Dim CntTr As Long
ReDim Preserve Arbol.Node(Arbol.Index)

Arbol.Grade = 2
CntTr = 1

If Arbol.Root = False Then
 Arbol.Root = True
 Arbol.Node(Arbol.Index).Parent = -1
 Arbol.Node(Arbol.Index).Type = "Root"
 AgregarN Arbol, Data
 Arbol.Node(Arbol.Index - 1).Level = CntTr
 If cntr > Arbol.Height Then Arbol.Height = CntTr
 Exit Sub
End If

FndNd = 0
CntTr = 2

Do
 If Arbol.Node(FndNd).Info(0) >= Data Then
 'For The ChildLeft Branch
  If Arbol.Node(FndNd).ChildLeft = -1 Then
   If Arbol.Node(FndNd).Type <> "Root" Then Arbol.Node(FndNd).Type = "Interior"
   Arbol.Node(FndNd).ChildLeft = Arbol.Index
   AgregarN Arbol, Data
   
   Arbol.Node(Arbol.Index - 1).Parent = FndNd
   Arbol.Node(Arbol.Index - 1).Level = CntTr
   If CntTr > Arbol.Height Then Arbol.Height = CntTr
   FndNd = -1
  Else
   FndNd = Arbol.Node(FndNd).ChildLeft
   CntTr = CntTr + 1
  End If
 Else
 'For the ChildRight Branch
  If Arbol.Node(FndNd).ChildRight = -1 Then
   If Arbol.Node(FndNd).Type <> "Root" Then Arbol.Node(FndNd).Type = "Interior"
   Arbol.Node(FndNd).ChildRight = Arbol.Index
   AgregarN Arbol, Data
   
   Arbol.Node(Arbol.Index - 1).Parent = FndNd
   Arbol.Node(Arbol.Index - 1).Level = CntTr
   If CntTr > Arbol.Height Then Arbol.Height = CntTr
   FndNd = -1
  Else
   FndNd = Arbol.Node(FndNd).ChildRight
   CntTr = CntTr + 1
  End If
 End If
Loop Until FndNd = -1
Balancear Arbol
End Sub

Public Sub AgregarN(Arbol As BTree, Data As Integer)
If Arbol.Node(Arbol.Index).Type <> "Root" Then Arbol.Node(Arbol.Index).Type = "Leaf"

Arbol.Node(Arbol.Index).Info(0) = Data
Arbol.Node(Arbol.Index).ChildLeft = -1
Arbol.Node(Arbol.Index).ChildRight = -1

Arbol.Index = Arbol.Index + 1
End Sub

Public Sub Balancear(Arbol As BTree)

End Sub

Public Function BuscarN(Arbol As BTree, Data As Integer) As Long
Dim FndNd As Long

If Arbol.Root = False Then
 BuscarN = -1
 Exit Function
End If

FndNd = 0

Do
 If Arbol.Node(FndNd).Info(0) > Data Then
 'If the Data is in the ChildLeft Branch
  If Arbol.Node(FndNd).ChildLeft = -1 Then
  'Data Not Found
   FndNd = -1
  Else
   FndNd = Arbol.Node(FndNd).ChildLeft
  End If
 ElseIf Arbol.Node(FndNd).Info(0) < Data Then
 'If the Data is in the ChildRight Branch
  If Arbol.Node(FndNd).ChildRight = -1 Then
  'Data Not Found
   FndNd = -1
  Else
   FndNd = Arbol.Node(FndNd).ChildRight
  End If
 ElseIf Arbol.Node(FndNd).Info(0) = Data Then
 'If the Data is Found
  Exit Do
 End If
Loop Until FndNd = -1

BuscarN = FndNd
End Function