Generic Binary Tree

This blog post is a result of me, trying to decipher what was happen with tjoney's code in this post.

I've broken the post in to three distinct sections;-
1. Nodes
2. Tree
3. Proof of Concept Code

---

1. Node(Of T)

The basic layout of node is this.

                        LeftNode : Node(Of T)
                       /
Parent : Node(Of T) <-(Value : T)
                       \
                        RighNode : Node(Of T)

Value => What this node's value is.
Parent => Which node is the Parent of this Node
LeftNode => The Child to the Left of this Node
RighNode => The Child to the Right of the Node. (Note: I'm using Righ so the code layout looks cleaner.

Public Class Node(Of T As IComparable(Of T))
#Region "Instance Variables"
    Protected _Value As T
    Protected _LeftNode As Node(Of T)
    Protected _RighNode As Node(Of T)
    Protected _Parent As Node(Of T)
#End Region

    Public Sub New(v As T, p As Node(Of T))
        _Value = v
        _Parent = p
    End Sub

Let's us create a new instance of the Node Class, along with this Node Value and Parent.

    Public Overrides Function ToString() As String
        Return _Value.ToString
    End Function

Overriding the ToString() Function to Display the Node's Value. (It's also used by the watch window in the debugger.)

#Region "Properties"
    Property Parent() As Node(Of T)
        Get
            Return _Parent
        End Get
        Protected Friend Set(value As Node(Of T))
            _Parent = value
        End Set
    End Property
    Public Property Value As T
        Get
            Return _Value
        End Get
        Protected Friend Set(value As T)
            _Value = value
        End Set
    End Property
    Public Property Left As Node(Of T)
        Get
            Return _LeftNode
        End Get
        Protected Friend Set(value As Node(Of T))
            _LeftNode = value
        End Set
    End Property
    Public Property Righ As Node(Of T)
        Get
            Return _RighNode
        End Get
        Protected Friend Set(value As Node(Of T))
            _RighNode = value
        End Set
    End Property
#End Region

The follow helpers makes the code easier read and type.

#Region "Helpers"
    Public Function HasLeft() As Boolean
        Return _LeftNode IsNot Nothing
    End Function
    Public Function HasRigh() As Boolean
        Return _RighNode IsNot Nothing
    End Function
    Public Function ParentAbsent() As Boolean
        Return _Parent Is Nothing
    End Function
    Public Function LeftIsEmpty() As Boolean
        Return _LeftNode Is Nothing
    End Function
    Public Function RighIsEmpty() As Boolean
        Return _RighNode Is Nothing
    End Function
#End Region

The Operators
I've define some comparison operators to save me writting a.Value.CompareTo(b.Value) == 0 whenever I want check if to nodes have the same value. Also I've add some the compare a Node against a value.

#Region "Comparision Operators"
#Region "Node Based"
    Public Shared Operator =(a As Node(Of T), b As Node(Of T)) As Boolean
        Return a.Value.CompareTo(b.Value) = 0
    End Operator
    Public Shared Operator <>(a As Node(Of T), b As Node(Of T)) As Boolean
        Return a.Value.CompareTo(b.Value) <> 0
    End Operator
    Public Shared Operator <(a As Node(Of T), b As Node(Of T)) As Boolean
        Return a.Value.CompareTo(b.Value) < 0
    End Operator
    Public Shared Operator <=(a As Node(Of T), b As Node(Of T)) As Boolean
        Return a.Value.CompareTo(b.Value) <= 0
    End Operator
    Public Shared Operator >(a As Node(Of T), b As Node(Of T)) As Boolean
        Return a.Value.CompareTo(b.Value) > 0
    End Operator
    Public Shared Operator >=(a As Node(Of T), b As Node(Of T)) As Boolean
        Return a.Value.CompareTo(b.Value) >= 0
    End Operator
#End Region
#Region "Comparision Operators with Value"
    Public Shared Operator =(a As Node(Of T), v As T) As Boolean
        Return a.Value.CompareTo(v) = 0
    End Operator
    Public Shared Operator <>(a As Node(Of T), v As T) As Boolean
        Return a.Value.CompareTo(v) <> 0
    End Operator
    Public Shared Operator <(a As Node(Of T), v As T) As Boolean
        Return a.Value.CompareTo(v) < 0
    End Operator
    Public Shared Operator >(a As Node(Of T), v As T) As Boolean
        Return a.Value.CompareTo(v) > 0
    End Operator
    Public Shared Operator <=(a As Node(Of T), v As T) As Boolean
        Return a.Value.CompareTo(v) <= 0
    End Operator
    Public Shared Operator >=(a As Node(Of T), v As T) As Boolean
        Return a.Value.CompareTo(v) >= 0
    End Operator
#End Region
#End Region

End Class

And that's it, rather a simple class.

---

2. BTree(Of T)

        (3)
      /
    (16)
      \
        (22)
  /
(24)
  \
        (37)
      /
    (45)
      \
        (99)

Note: The Left child is the higher of the branches.

Public Class BTree(Of T As IComparable(Of T))
#Region "Instance Variables"
    Protected _root As Node(Of T)
#End Region
    Public Sub New()
        _root = Nothing
    End Sub

A Null value at the Root indicates the Tree is empty.

#Region "Insert Methods"
#Region "Insert based on value"
    Public Sub Insert(ByRef i As T)
        If _root Is Nothing Then
            _root = New Node(Of T)(i, Nothing)
        Else
            Insert(_root, i)
        End If
    End Sub

    Protected Sub Insert(ByRef ThisNode As Node(Of T), Value As T)
        If ThisNode > Value Then
            If ThisNode.LeftIsEmpty Then
                ThisNode.Left = New Node(Of T)(Value, ThisNode)
            Else
                Insert(ThisNode.Left, Value)
            End If
        Else
            If ThisNode.RightIsEmpty Then
                ThisNode.Righ = New Node(Of T)(Value, ThisNode)
            Else
                Insert(ThisNode.Righ, Value)
            End If
        End If
    End Sub
#End Region

You may be asking yourself why the two Insert methods. The first is the public method it makes clean simple API for the user.
It calls a second Protected method, which is internal mechanics of the insertion. This is because I utilise recursion, it save the user remembering who the correctly call it.

There's another protected insertion method inside the BinTree Class, it is utilised by the delete method.

#Region "Insert Based on nodes"
    Protected Sub Insert(ByRef ThisNode As Node(Of T), NodeBeingInserted As Node(Of T))
        If NodeBeingInserted < ThisNode Then
            If ThisNode.LeftIsEmpty Then
                ThisNode.Left = NodeBeingInserted
                NodeBeingInserted.Parent = ThisNode
            Else
                Insert(ThisNode.Left, NodeBeingInserted)
            End If
        Else
            If ThisNode.RightIsEmpty Then
                ThisNode.Righ = NodeBeingInserted
                NodeBeingInserted.Parent = ThisNode
            Else
                Insert(ThisNode.Righ, NodeBeingInserted)
            End If
        End If
    End Sub
#End Region
#End Region

Contains searches the BinTree to see if a key exists, it will only find the first occurrence of the key.

#Region "Contains"

    Public Function Contains(ByVal key As T) As Boolean
        Return _Contains(key) IsNot Nothing
    End Function

    Private Function _Contains(ByVal key As T) As Node(Of T)
        Dim current As Node(Of T) = _root
        While (current IsNot Nothing) AndAlso (current <> key)
            current = If(current > key, current.Left, current.Righ)
        End While
        Return current
    End Function
#End Region

When were clearing the BinTree, we need to get rid of all the references to the Nodes.
We can't simply set _root to nothing and be done with.

#Region "Deletion"
    Public Sub Clear()
        Dim NodeList As New List(Of Node(Of T))
        Traverse_InOrder_Nodes(_root, NodeList)
        NodeList.ForEach(Sub(n)
                             SetLinksToNull(n)
                             n = Nothing
                         End Sub)
        _root = Nothing
    End Sub

Deleting a Key

    Public Function Delete(ByVal key As T) As Boolean
        Dim NodeLoci = _Contains(key)
        ' Not Found is idicated by a null value.
        If NodeLoci Is Nothing Then Return False
        Dim ChildrenOfNode = Traverse_InOrder_Nodes_ExceptMe(NodeLoci)
        If NodeLoci.ParentAbsent Then
            _root = Nothing
            ChildrenOfNode.ForEach(Sub(n)
                                       SetLinksToNull(n)
                                       If _root Is Nothing Then
                                           _root = n
                                       Else
                                           Insert(_root, n)
                                       End If
                                   End Sub)
            Return True
        Else
            Dim MoveChildren = Function()
                                   ChildrenOfNode.ForEach(Sub(n) Insert(_root, SetLinksToNull(n))) ' Insert(NodeLoci.Parent, SetLinksToNull(n)))
                                   Return True
                               End Function
            With NodeLoci.Parent
                If .HasLeft AndAlso (.Left = NodeLoci) Then
                    .Left = Nothing : Return MoveChildren()
                ElseIf .HasRigh AndAlso (.Righ = NodeLoci) Then
                    .Righ = Nothing : Return MoveChildren()
                End If
            End With
        End If
        Return False
    End Function
#End Region

#Region "Helper Methods"
    Private Function SetLinksToNull(ByRef n As Node(Of T)) As Node(Of T)
        n.Left = Nothing
        n.Righ = Nothing
        n.Parent = Nothing
        Return n
    End Function
#End Region

Traversal of the Nodes in the BinTree

#Region "In-Order Traversals"

    Public Function Travers_InOrder_Values() As List(Of T)
        Dim rl As New List(Of Node(Of T))
        Traverse_InOrder_Nodes(_root, rl)
        Return rl.Select(Function(n) n.Value).ToList
    End Function

    Private Function Traverse_InOrder_Nodes_ExceptMe(ByRef thisNode As Node(Of T)) As List(Of Node(Of T))
        Dim Children_Left As New List(Of Node(Of T))
        Dim Children_Righ As New List(Of Node(Of T))
        If thisNode IsNot Nothing Then
            If thisNode.HasLeft Then Traverse_InOrder_Nodes(thisNode.Left, Children_Left)
            If thisNode.HasRigh Then Traverse_InOrder_Nodes(thisNode.Righ, Children_Righ)
        End If
        Children_Left.Reverse()
        Return Children_Left.Concat(Children_Righ).ToList()
    End Function

    Private Sub Traverse_InOrder_Nodes(ByVal thisNode As Node(Of T), ByRef NodeList As List(Of Node(Of T)))
        If thisNode IsNot Nothing Then
            If thisNode.HasLeft Then Traverse_InOrder_Nodes(thisNode.Left, NodeList)
            NodeList.Add(thisNode)
            If thisNode.HasRigh Then Traverse_InOrder_Nodes(thisNode.Righ, NodeList)
        End If
    End Sub

Outputting the BinTree.

The first PrintOut prints out the nodes values on one line.
(Note: The Input parameter is of type System.IO.TextWriter) which allow the outputted not only to console, but could be outputted to a file.
The Second PrintIndented outputs the BinTree as an ASCII Representation.

        (3)
      /
    (16)
      \
        (22)
  /
(24)
  \
        (37)
      /
    (45)
      \
        (99)

#Region "Output Displays"

    Public Sub PrintOut(cout As System.IO.TextWriter)
        Travers_InOrder_Values.ForEach(Sub(n) cout.Write("{0} ", n))
        cout.WriteLine()
        cout.Flush()
    End Sub 

    Public Sub PrintIndented(cout As System.IO.TextWriter)
        Traverse_InOrder_Indented(_root, cout, 0)
    End Sub

    Private Shared Sub Traverse_InOrder_Indented(ByVal thisNode As Node(Of T), cout As System.IO.TextWriter, Optional Indent As Integer = 0)
        If thisNode IsNot Nothing Then
            If thisNode.HasLeft Then
                Traverse_InOrder_Indented(thisNode.Left, cout, Indent + 4)
                cout.WriteLine("{0}{1}", New String(" ", 2 + Indent), "/")
            End If
            cout.WriteLine("{0}({1})", New String(" ", Indent), thisNode.Value.ToString)
            If thisNode.HasRigh Then
                cout.WriteLine("{0}{1}", New String(" ", 2 + Indent), "\")
                Traverse_InOrder_Indented(thisNode.Righ, cout, Indent + 4)
            End If
        End If
        cout.Flush()
    End Sub
#End Region


#End Region


End Class

---

3. Proof of Concept code.

Now let's try out our BinTree Class.

Module Module1
    Sub Main()
        Dim nums As New BTree(Of Integer)()
        nums.Insert(24)
        nums.Insert(45)
        nums.Insert(16)
        nums.Insert(37)
        nums.Insert(3)
        nums.Insert(99)
        nums.Insert(22)

        Console.WriteLine("Inorder Traversal: " & vbCrLf)
        nums.PrintOut(Console.Out)
        nums.PrintIndented(Console.Out)
        Console.WriteLine()
        Console.WriteLine()

        nums.Delete(45)
        nums.PrintOut(Console.Out)
        nums.PrintIndented(Console.Out)
        Console.WriteLine()
        Console.WriteLine()

        nums.Delete(16)
        nums.PrintOut(Console.Out)
        nums.PrintIndented(Console.Out)
        Console.WriteLine()
        Console.WriteLine()

        nums.Delete(24)
        nums.PrintOut(Console.Out)
        nums.PrintIndented(Console.Out)
        Console.WriteLine()
        Console.WriteLine()

        Console.Write("Press enter to continue. ")
        Console.ReadLine()
    End Sub

End Module

:shuriken: