Binary trees are specific trees that are only allowed to have two child nodes. There are a multiple variations of the types of binary trees - some that balance so everyone has the maximum number of nodes on the same level, some are "perfect", and so on.
The type of tree we area dealing with here is the most basic - a rooted binary tree. It will allow inserts of all kind (well some exceptions), won't balance, and shows great recursion. Speaking of - that's how we'll do printing the tree and a basic search.
Rules for the tree:
- External insertion. We are keeping it simple and just adding to external nodes. Internal insertion is something more complex.
- Insertion is easy - for a given node if the value is less insert it to the left, if more insert it to the right!
Side note - there's a small commentary about recursion after the code.
As with most of my tutorials the comments in the code should suffice explaining the code as it happens.
The first let's make the Node class!
The node will have a left and right node defaulted to nothing.
The node will also have a value to compare!
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
Our tree that makes use of the node 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.
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.
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.
'-- 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).
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"
'-- and record's its value, and return true. This trickles up to the root and out we go.
'-- If the value isn't found returning false let's everyone know this.
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
The Main:
Spoiler
Recursion
A brief side note on recursion. Recursion is calling a method from inside that method. It helps cut down on complex code, but increases your headache. It's easy to go off the path and cause an infinite loop.
Take the case of the InOrder. Let's walk through it procedurally.
Our small tree. The dash is the level, the L&R are the left and right.
6
-L 3
--L 2
--R 5
-R 9
Try and envision the periods are spaces and... 6 is the top node with a child 3 and 9. 3 has children 2 and 5.
......6........
..../..\.......
...3....9......
../\...........
.2..5..........
Iteration - start at the root aka 6
1: on 6, check left, is a value go left
2: On 3, check left, is a value, go left
3: on 2, check left, no left
3: print '2'
3: check right, no right,
3: iteration done.
2: print '3'
2: check right, is a value, go right.
4: on 5, check left, no left
4: print '5'
4: check right, no right,
4: iteration done.
2: iteration done
1: print '6'
1: check right, is a value, go right
5: on 9, check left, no value
5: print '9'
5: check right, no value
5: iteration done
1: iteration done.
End game is you get: 2, 3, 5, 6, 9
Advance topics:
take this to a balancing tree
internal insertion
better visuals!
use it with a sort
make the value a generic "object"
using nodes create a 'graph' structure.
Enjoy the first steps of your journey into the fun of trees!
MultiQuote
| 