Page 1 of 1

A Basic Binary Trees Rate Topic: -----

#1 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 9582
  • View blog
  • Posts: 36,319
  • Joined: 12-June 08

Posted 21 July 2011 - 12:03 PM

Binary trees - a classic data structure. Humorously I was inspired to writing up the structure in VB.NET I figure - why not share it with the rest of the world?

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!

Is This A Good Question/Topic? 2
  • +

Page 1 of 1