Die Community zu .NET und Classic VB.

Startseite / Tipps / VB.NET-Tipp 0151: Laufende Daten sortieren mit TreeSort

VB.NET-Tipp 0151: Laufende Daten sortieren mit TreeSort

 von Dario

Schwierigkeitsgrad:

Framework-Version(en): .NET Framework 3.0, .NET Framework 3.5, .NET Framework 4

.NET-Version(en): Visual Basic 2008, Visual Basic 2010

Download: Download des Beispielprojektes [8,44 KB]

' Dieser Quellcode stammt von http://www.activevb.de
' und kann frei verwendet werden. Für eventuelle Schäden
' wird nicht gehaftet.

' Um Fehler oder Fragen zu klären, nutzen Sie bitte unser Forum.
' Ansonsten viel Spaß und Erfolg mit diesem Source!

' Projektversion:   Visual Studio 2008
' Option Strict:    An
' Option Explicit:  An
' Option Infer:     Aus
'
' Referenzen: 
'  - System
'  - System.Data
'  - System.Deployment
'  - System.Xml
'  - System.Core
'  - System.Xml.Linq
'  - System.Data.DataSetExtensions
'
' Imports: 
'  - Microsoft.VisualBasic
'  - System
'  - System.Collections
'  - System.Collections.Generic
'  - System.Data
'  - System.Diagnostics
'  - System.Linq
'  - System.Xml.Linq
'

' ##############################################################################
' ################################ Module1.vb ##################################
' ##############################################################################
Imports System.Linq.Enumerable
Imports System.Collections.Generic

Module TreeSort
    ' Basisklasse für einen Binärbaum
    Public MustInherit Class BinaryTree(Of T As IComparable(Of T)) _
        : Implements IEnumerable(Of T)

        ' Funktionen für die abgeleiteten Klassen: Hinzufügen & Durchlaufen
        Public MustOverride Function Add(ByVal x As T) As BinaryTree(Of T)
        Protected MustOverride Function GetElements() As IEnumerable(Of T)

        ' IEnumerable unterstützen
        Protected Function GetEnumerator() As IEnumerator(Of T) _
                Implements IEnumerable(Of T).GetEnumerator

            Return GetElements.GetEnumerator()
        End Function
        Private Function GetEnumerator1() As IEnumerator _
                Implements IEnumerable.GetEnumerator

            Return GetEnumerator()
        End Function
    End Class

    ' Konstruktorfunktionen:

    ' Einen leeren Baum erstellen
    Public Function Leaf(Of T As IComparable(Of T))() As BinaryTree(Of T)
        Return New LeafNode(Of T)()
    End Function

    ' Einen Baum aus zwei Teilbäumen und einer Wurzel zusammensetzen
    Public Function Node(Of T As IComparable(Of T))(ByVal value As T, _
            ByVal left As BinaryTree(Of T), _
            ByVal right As BinaryTree(Of T)) As BinaryTree(Of T)

        Return New TreeNode(Of T)(value, left, right)
    End Function


    ' Implementierungen der Basisklassen

    ' Implementierung für einen leeren Baum
    Private Class LeafNode(Of T As IComparable(Of T)) _
            : Inherits BinaryTree(Of T)

        ' Neuen Baum erzeugen mit x als Wurzelelement
        Public Overrides Function Add(ByVal x As T) As BinaryTree(Of T)
            Return Node(x, Leaf(Of T)(), Leaf(Of T)())
        End Function

        ' Keine Elemente zum Zurückgeben vorhanden
        Protected Overrides Function GetElements() As  _
                System.Collections.Generic.IEnumerable(Of T)

            Return New T() {}
        End Function
    End Class

    ' Implementierung für einen Baumknoten
    Private Class TreeNode(Of T As IComparable(Of T)) : Inherits BinaryTree(Of T)
        Private ReadOnly m_Value As T
        Private ReadOnly m_Right, m_Left As BinaryTree(Of T)

        Public Sub New(ByVal x As T, ByVal left As BinaryTree(Of T), _
                       ByVal right As BinaryTree(Of T))
            m_Value = x : m_Left = left : m_Right = right
        End Sub

        ' Linker Teilbaum & Wurzel & rechter Teilbaum
        Protected Overrides Function GetElements() As  _
                System.Collections.Generic.IEnumerable(Of T)

            Return m_Left.Concat(New T() {m_Value}).Concat(m_Right)
        End Function

        ' Rekursives Einfügen
        Public Overrides Function Add(ByVal x As T) As BinaryTree(Of T)
            If x.CompareTo(m_Value) < 0 Then
                ' Wenn x kleiner als die Wurzel ist, in den linken 
                '  Teilbaum einfügen
                Return Node(m_Value, m_Left.Add(x), m_Right)
            Else
                ' ... sonst in den rechten
                Return Node(m_Value, m_Left, m_Right.Add(x))
            End If
        End Function
    End Class
End Module

Module Module1

    Sub Main()
        ' Zufällige Daten erzeugen
        Dim random As New Random()
        Dim data As IEnumerable(Of Integer) = _
            From i In Range(1, 25) Select random.Next(1, 10)

        ' Den Baum schrittweise aus den Daten zusammenbauen
        Dim sortedTree As BinaryTree(Of Integer) = Leaf(Of Integer)()
        For Each i As Integer In data
            sortedTree = sortedTree.Add(i)
        Next

        ' Ausgeben
        Console.WriteLine("Daten: ")
        For Each x As Integer In data
            Console.WriteLine(x)
        Next

        Console.WriteLine("Sortierte Daten: ")

        For Each x As Integer In sortedTree
            Console.WriteLine(x)
        Next

        Console.ReadLine()
    End Sub

End Module