关于树（AboutTrees）

• 下载源代码 - 10.83 KB

引言

看看这个

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

我不知道这是否是全新的东西，但我认为，这可以作为许多层次化数据结构的基础。由于它是一棵通用的树，值可以是任何东西。
让我们做一个小的扩展，看看它运行起来

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 

实际上我现在完成了，但我希望添加一些关于遍历树的内容。你是对的，我说的是“遍历”，而不是“递归”。（这是个双关语吗？）。

更多内容

递归的主要缺点是，你需要为每种全元素访问方式创建一个特殊函数。
如果能用简单的 ForEach 循环遍历所有节点该有多好！
是的，我们开始了

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

当然，我们的树想要其中一个很棒的类 - 啊，慷慨一点 - 给它两个。一个用于遍历它的子节点，另一个用于包括自身在内的遍历。

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

HEnumerating 对象封装在 Root-/Child-Enumerating() 函数中。实际上，大多数节点不需要实例化它们。

现在我们可以毫不费力地进行不同的选择。

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 

尝试使用常规递归编写这三个搜索！

还要注意 .CurrentDepth() 和 .SkipChildren() 的好处。

Postscript

给出的代码有点脏，我知道（哎呀，没有属性！！）。但希望它能清楚地展示背后的想法。

历史

• 2008年1月15日：初始发布