カテゴリー
Visual Basic

VBによるBinaryTree、ネットから拾いました。

Public Class Node

 

    Private _leftNode As Node = Nothing

    Private _rightNode As Node = Nothing

 

    Private _lValue As Int32 = 0

 

    Public Property LeftNode As Node

        Get

            Return _leftNode

        End Get

        Set(value As Node)

            _leftNode = value

        End Set

    End Property

 

    Public Property RightNode As Node

        Get

            Return _rightNode

        End Get

        Set(value As Node)

            _rightNode = value

        End Set

    End Property

 

    Public Property Value As Int32

        Get

            Return _lValue

        End Get

        Set(value As Int32)

            _lValue = value

        End Set

    End Property

 

    Public Sub New(ByVal value As Int32)

'-- new nodes don't have children yet, just a value

        _leftNode = Nothing

        _rightNode = Nothing

        _lValue = value

    End Sub

 

End Class


Public Class BinTree

    Private _root As Node = Nothing '-- tree has to have a root.ツリーにはルートが必要です



    Public Sub New(ByVal value As Int32)

        _root = New Node(value)  '-- create our nodeノードを作成します

        Console.WriteLine(String.Format("Root Inserting: {0}", value)) '-- output what we have done.行ったことを出力します

    End Sub



    '-- Inserting takes two nodes.  The current node we want to do the insert on, and a next node for the loop.
    '--挿入には2つのノードが必要です。挿入を実行する現在のノードと、ループの次のノード

    Public Sub InsertNode(ByVal input As Int32)

            Dim currentNode As Node = _root

            Dim nextNode As Node = _root



        '-- loop through all the nodes left to right based on our rule of greater than/less than.
        '--より大きい/より小さいというルールに基づいて、すべてのノードを左から右にループします

        '--  When we find a node who doesn't have any more children we know we have found spot to insert! 
        '--子がもうないノードを見つけると、挿入する場所が見つかりました。

        '-- (because we have been filtered down here by our rules to this point)
        '--(これまでのルールによってここでフィルタリングされているため)

        '-- Side note - this could probably be done recursively but doing EVERYTHING recursively might be boring.
        '--補足-これはおそらく再帰的に実行できますが、すべてを再帰的に実行するのは退屈かもしれません。

        While currentNode.Value <> input AndAlso nextNode IsNot Nothing

                currentNode = nextNode

                If nextNode.Value < input Then

                    nextNode = nextNode.RightNode

                Else

                    nextNode = nextNode.LeftNode

                End If

            End While



        '-- Once we find our node with no children that follow our rules check our rules one last time to figure out
        '--ルールに従っている子がないノードを見つけたら、最後にもう一度ルールをチェックして把握します

        '-- which side to tack on our node. 
        '--どちら側をノードにタックするか。

        '-- Oh, and no duplicates!  They screw up the order of things!
        '--ああ、重複はありません!彼らは物事の順序を台無しにします!

        If currentNode.Value = input Then

                Console.WriteLine("Can't insert duplicates!")

            ElseIf currentNode.Value < input Then

                currentNode.RightNode = New Node(input)

                Console.WriteLine(String.Format("Inserting: {0}", input))

            Else

                currentNode.LeftNode = New Node(input)

                Console.WriteLine(String.Format("Inserting: {0}", input))

            End If

        End Sub



    '-- Printing is loads of recursive fun.  I have two basic types here: Inorder and PreOrder.
    '--印刷は再帰的な楽しみの山です。ここには、InorderとPreOrderの2つの基本的なタイプがあります。

    Public Sub Print(ByVal doInOrder As Boolean)

            If doInOrder Then

                InOrder(_root)

            Else

                PreOrder(_root, 0, "")

            End If

        End Sub



    '-- InOrder follows a depth first run.  check left, print, check right.
    '--InOrderは、深さ優先実行に従います。左をチェックし、印刷し、右をチェックします。

    '-- It attempts to find a right node.  If found it goes to the right node and then searches all the left nodes, prints, and goes to the right node.
    '--適切なノードを見つけようとします。見つかった場合は、右側のノードに移動し、次に左側のすべてのノードを検索して印刷し、右側のノードに移動します。

    '-- The joys of recursion are over floweth here.
    '--再帰の喜びはここに溢れています

    Private Sub InOrder(ByVal myNode As Node)

            If myNode.LeftNode IsNot Nothing Then InOrder(myNode.LeftNode)

            Console.WriteLine(myNode.Value)

            If myNode.RightNode IsNot Nothing Then InOrder(myNode.RightNode)

        End Sub





    '-- PreOrder I decided to take some liberties and make it pretty.  I added a hyphen to signify the level, and
    '--事前注文私はいくつかの自由を取り、それをきれいにすることにしました。レベルを示すためにハイフンを追加し、

    '-- also visual indicators on which node (left or right) the value is from. 
    '--また、値がどのノード(左または右)からのものであるかを視覚的に示します。

    '-- The idea here is we print which node we are on, check left, check right.
    '--ここでの考え方は、現在のノードを印刷し、左をチェックし、右をチェックすることです。

    '--

    '-- The level As Int32 is only needed for printing the hyphen.. you can remove it and it still works (sans printing hyphens).
    '--レベルAsInt32は、ハイフンを印刷するためにのみ必要です。それを削除しても、引き続き機能します(ハイフンの印刷はありません)。

    Private Sub PreOrder(ByVal myNode As Node, ByVal level As Int32, ByVal side As String)

            Dim sVal As String = String.Empty



            For i As Int32 = 0 To level - 1

                sVal += "-"

            Next

        '-- Actual meat of the method.  '--メソッドの実際の肉。

        Console.WriteLine(String.Format("{0}{1} {2}", sVal, side, myNode.Value))

            If myNode.LeftNode IsNot Nothing Then PreOrder(myNode.LeftNode, level + 1, "L")

            If myNode.RightNode IsNot Nothing Then PreOrder(myNode.RightNode, level + 1, "R")

        End Sub



    '-- Here we will take in a value and attempt to find the path to that value. 
    '--ここでは、値を取り込んで、その値へのパスを見つけようとします。

    Public Sub FindPathToNode(ByVal input As Int32)

            Console.WriteLine(String.Format("Finding value: {0}", input))

        Dim path As New List(Of Int32) '-- instead of printing the path we will have it saved to a list. '--パスを印刷する代わりに、リストに保存します。

        Dim bFound As Boolean = False '-- helps us determine if was found or not. '--見つかったかどうかを判断するのに役立ちます。

        Dim sPath As String = String.Empty



        '-- basic check to make sure the root wasn't it!
        '--ルートがそれではなかったことを確認するための基本的なチェック!
        If _root.Value = input Then

                Console.WriteLine("root is input!")

            Else

            '-- Dive into the recursion.    '--再帰に飛び込みます。

            bFound = PostOrder(_root, input, path)



                If bFound Then

                '-- print our the path - from the root to the searched node
                '--ルートから検索されたノードまでのパスを出力します'-
                '-- (the path is in the order of found node then it exits each itteration to the root)
                '--(パスは見つかったノードの順序であり、ルートへの各イテレーションを終了します)
                For i As Int32 = path.Count - 1 To 0 Step -1

                        sPath += path(i).ToString + " "

                    Next

                    Console.WriteLine("Path: " + sPath)

                Else

                    Console.WriteLine("No found!")

                End If

            End If

        End Sub



    '-- A modification of the post order.  We take in a node, the value we are looking for, and the path from the node back up to the root.
    '--ポストオーダーの変更。ノード、探している値、およびノー??ドからルートに戻るパスを取り込みます。
    '-- The trick with this one is we evaluate the nodes first then interact with our current node.  In this case we look left, we look right, and then
    '--これの秘訣は、最初にノードを評価してから、現在のノードと対話することです。この場合、左を見て、右を見て、次に
    '-- evaluate if we are the node in question.  If we are record our value on the list and exit with a 'return true'.  The calling iteration then receives this "true"
    '--問題のノードであるかどうかを評価します。リストに値を記録し、「returntrue」で終了する場合。次に、呼び出し元の反復はこの「真」を受け取ります
    '--  and record's its value, and return true.  This trickles up to the root and out we go.
    '--して、その値を記録し、trueを返します。これは根元まで滴り落ち、私たちは出て行きます。
    '-- If the value isn't found returning false let's everyone know this.
    '--値がfalseを返すことが見つからない場合は、誰もがこれを知ってみましょう。
    Private Function PostOrder(ByVal myNode As Node, ByVal input As Int32, ByVal thePath As List(Of Int32)) As Boolean

        '-- check the l

        If myNode.LeftNode IsNot Nothing Then

            If PostOrder(myNode.LeftNode, input, thePath) Then

                thePath.Add(myNode.Value)

                Return True

            End If

        End If



        If myNode.RightNode IsNot Nothing Then

            If PostOrder(myNode.RightNode, input, thePath) Then

                thePath.Add(myNode.Value)

                Return True

            End If

        End If





        If myNode.Value = input Then

            thePath.Add(myNode.Value)

            Return True

        End If



        Return False

    End Function

End Class
Imports System
Module Program
    Sub Main(args As String())
        Dim bar As New BinTree(5)

        bar.InsertNode(2)

        bar.InsertNode(1)

        bar.InsertNode(8)

        bar.InsertNode(3)

        bar.InsertNode(10)

        bar.InsertNode(7)

        bar.InsertNode(12)

        Console.WriteLine("------------------")

        bar.Print(False)

        Console.WriteLine("------------------")

        bar.Print(True)

        Console.WriteLine("------------------")

        bar.FindPathToNode(12)

        Console.WriteLine("------------------")

        bar.FindPathToNode(13)



        Console.ReadLine()
    End Sub
End Module

上がメインです。

コメントを残す

メールアドレスが公開されることはありません。

inserted by FC2 system