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!