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
上がメインです。