AboutTrees

• Download source - 10.83 KB

Introduction

Look at this:

Public Class Tree(Of T) : Inherits List(Of Tree(Of T))
    Public Value As T
End Class

I don't know, whether it's real new, but I think, this could be the base for a lot of hierarchical data-structures. Since it's a generic Tree, Value can be anything.
Let's do a small extension and see it running:

Public Class Tree(Of T) : Inherits List(Of Tree(Of T))
        Public Value As T

        Public Sub New(ByVal Value As T)
            Me.Value = Value
        End Sub

        Public Function AddNew(ByVal Value As T) As Tree(Of T)
            Dim Node As New Tree(Of T)(Value)
            MyBase.Add(Node)
            Return Node
        End Function
    End Class

    Sub EnumerateTree(Of T)(ByVal Parent As Tree(Of T))
        WriteLine(Parent.Value)
        Indent += 2
        For Each Child In Parent
            EnumerateTree(Child)
        Next
        Indent -= 2
    End Sub

    Sub Main()
        Dim Vehicles As New Tree(Of String)("Vehicle")
        With Vehicles
            With .AddNew("OnWater")
                .AddNew("SurfBoard")
                With .AddNew("Ship")
                    With .AddNew("Motorboat")
                        .AddNew("Steamboat")
                        .AddNew("Submarine")
                        .AddNew("Tanker").AddNew("Tanker2").AddNew("Tanker3")
                        .AddNew("Speedboat")
                    End With
                    With .AddNew("Sailboat")
                        .AddNew("Cog")
                        .AddNew("Frigate")
                        .AddNew("Catamaran")
                    End With
                End With
            End With
            With .AddNew("OnAir")
                .AddNew("Plane")
                With .AddNew("Rocket")
                    .AddNew("Challenger")
                    .AddNew("Apollo 13")
                End With
                .AddNew("Balloon")
            End With
            With .AddNew("OnEarth")
                .AddNew("Horse")
                With .AddNew("Car")
                    .AddNew("Trabant")
                End With
                .AddNew("Bike")
                .AddNew("Foot")
            End With
        End With
        EnumerateTree(Vehicles)
    End Sub 

Actually I'm finished now, but I'd like to append some stuff about iterating trees. You're right, I said "iterating", not "recursing". (Was that a pun?).

Some More

Recursion has the principle lack, that you need to create a special function for each kind of all-element-access.
How nice it would be, to loop all nodes with simple ForEach!
Jepp, and here we go:

Public Class HEnumerating : Implements IEnumerable

    Protected _Enrt As New Enumerator

    Public Sub New(ByVal Roots As IEnumerable)
        _Enrt.Roots = Roots.GetEnumerator
    End Sub

    Public Function GetEnumerator() As IEnumerator Implements IEnumerable.GetEnumerator
        _Enrt.Reset()
        Return _Enrt
    End Function

    Public Sub SkipChildren()
        _Enrt._ParentEnumerators.Pop()
    End Sub

    Public ReadOnly Property CurrentDepth() As Integer
        Get
            Return _Enrt._ParentEnumerators.Count - 2
        End Get
    End Property

    Protected Class Enumerator : Implements IEnumerator

        Friend Roots As IEnumerator
        'since iteration can't use a function-recursion-stack, we have to manage 
        'the stack by ourselves
        Friend _ParentEnumerators As New Stack(Of IEnumerator)
        Private _EnrtCurr As IEnumerator

        Public Sub Reset() Implements IEnumerator.Reset
            _ParentEnumerators.Clear()
            Roots.Reset()
            _ParentEnumerators.Push(Roots)
        End Sub

        Private Function MoveNext() As Boolean Implements IEnumerator.MoveNext
            'try walk forward - return True, if success
            'return False indicates the end of the ForEach-Loop
            While _ParentEnumerators.Count > 0
                _EnrtCurr = _ParentEnumerators.Peek
                If _EnrtCurr.MoveNext Then
                    'push the new star on _ParentEnumerators heaven
                    _ParentEnumerators.Push( _
                        DirectCast(_EnrtCurr.Current, IEnumerable).GetEnumerator)
                    Return True          'success
                Else
                    _ParentEnumerators.Pop() 'it failed - pop it!
                End If
                'if fails, try another _ParentEnumerator
            End While
            Return False  'all trials failed - Enumeration is finished
        End Function

        Private ReadOnly Property Current() As Object Implements IEnumerator.Current
            Get
                Return _EnrtCurr.Current
            End Get
        End Property

    End Class 'Enumerator
End Class 'HEnumerating

Of course our tree wants one of this fabulous class - ah, be generous - give him two. One to iterate his children, and one to get iterated, including himself.

Public Class Tree(Of T) : Inherits List(Of Tree(Of T))

    Public Value As T

    Public Sub New(ByVal Value As T)
        Me.Value = Value
    End Sub

    Public Function AddNew(ByVal Value As T) As Tree(Of T)
        Dim Node As New Tree(Of T)(Value)
        MyBase.Add(Node)
        Return Node
    End Function

    Public Function ChildEnumerating() As HEnumerating
        Static ChildRetVal As New HEnumerating(Me)
        Return ChildRetVal
    End Function

    Public Function RootEnumerating() As HEnumerating
        'to include Myself, I get boxed as only Element of an Array
        'and pass the Array as Root-Object to the HEnumerating
        Static RetVal As New HEnumerating(New Tree(Of T)() {Me})
        Return RetVal
    End Function

    Public Function GetNodeCount() As Integer
        For Each Nd As Tree(Of T) In Me
            GetNodeCount += 1 + Nd.GetNodeCount
        Next
    End Function

End Class

The HEnumerating - objects are encapsulated in the Root-/Child-Enumerating()-function. In effect most nodes never need to instantiate them.

Now we can do different selections without any effort.

For Each Nd As Tree(Of String) In Vehicles.RootEnumerating()
    If Nd.Value.StartsWith("S") Then WriteLine(Nd.Value)
Next
WriteLine()
Dim RootEnumerating = Vehicles.RootEnumerating()
For Each Nd As Tree(Of String) In RootEnumerating
    If RootEnumerating.CurrentDepth > 2 Then WriteLine(Nd.Value)
Next
WriteLine()
For Each Nd As Tree(Of String) In RootEnumerating
    If RootEnumerating.CurrentDepth > 2 Then
        RootEnumerating.SkipChildren()
    Else
        WriteLine(Nd.Value)
    End If
Next 

Try write these three searches using usual recursion!

Also note the benefit of .CurrentDepth() and .SkipChildren().

Postscript

The given code is quite dirty, I know (booh, no Properties!!). But it shows the Ideas behind quite clearly, I hope.

History

• 15^th January, 2008: Initial post