Imports System

​

Public Module Module1

​

    Public Structure BinTree

        Dim value As Integer

        Dim leftpointer As Integer

        Dim rightpointer As Integer

        Dim prevpointer As Integer

    End Structure

​

    Public Structure ptr

        Dim root As Integer

        Dim current As Integer

        Dim free As Integer

    End Structure

​

    Public Const nullpointer As Integer = -1

​

    Public Sub Main()

        Dim tree(19) As BinTree

        Dim pointer As ptr

        Dim rng As New Random

        Dim num As Integer

​

        pointer.root = 0

        pointer.current = pointer.root

        tree(pointer.current).value = rng.Next(1, 10)

        tree(pointer.current).leftpointer = nullpointer

        tree(pointer.current).rightpointer = nullpointer

        tree(pointer.current).prevpointer = nullpointer

​

        For i = 0 To 8

            num = rng.Next(1, 10)

            additem(tree, pointer.current, pointer.free, pointer.root, num)

        Next

​

        Dim valueoutput As String

        Dim leftoutput As String

        Dim rightoutput As String

        Dim prevoutput As String

​

        Console.WriteLine("List printed as array:")

Console.WriteLine("RAM  | Val  | Left  | Right  | Prev")

​

        For i = 0 To 9

​

            valueoutput = tree(i).value

            leftoutput = tree(i).leftpointer

            rightoutput = tree(i).rightpointer

            prevoutput = tree(i).prevpointer

​

            If valueoutput.Length = 1 Then

                valueoutput = "0" & valueoutput

            End If

​

            If leftoutput.Length = 1 Then

                leftoutput = "0" & leftoutput

            End If

​

            If rightoutput.Length = 1 Then

                rightoutput = "0" & rightoutput

            End If

​

            If prevoutput.Length = 1 Then

                prevoutput = "0" & prevoutput

            End If

​

            Console.WriteLine("0{0}   | {1}   | {2}    | {3}     | {4}", i, valueoutput, leftoutput, rightoutput, prevoutput)

​

        Next

​

        Console.WriteLine("")

        Console.WriteLine("List printed as binary tree:")

        print(tree, pointer.current, pointer.root)

​

    End Sub

​

    Public Sub print(tree() As BinTree, ByRef current As Integer, root As Integer)

        Dim branch As String = "left"

        Dim direction As String = "down"

        Dim prevpath As Integer

        If tree(root).leftpointer = nullpointer Then

            branch = "right"

            Console.WriteLine(tree(root).value)

        End If

​

        current = root

​

        Do Until current = root And branch = "right" And direction = "up"

​

            prevpath = current

​

            Select Case direction

​

                Case "down"

​

                    Select Case branch

                        Case "left"

                            current = tree(current).leftpointer

                        Case "right"

                            current = tree(current).rightpointer

                    End Select

​

                Case "up"

​

                    current = tree(current).prevpointer

​

                    Select Case prevpath

                        Case tree(current).leftpointer

                            branch = "left"

                        Case tree(current).rightpointer

                            branch = "right"

                    End Select

​

            End Select

​

            Select Case direction

​

                Case "down"

​

                    If tree(current).leftpointer = nullpointer Then

                        Console.WriteLine(tree(current).value)

                        branch = "right"

                    Else

                        branch = "left"

                    End If

​

                    If tree(current).rightpointer = nullpointer And tree(current).leftpointer = nullpointer Then

                        direction = "up"

​

                        If current = tree(prevpath).leftpointer Then

                            branch = "left"

                        Else

                            branch = "right"

                        End If

​

                    End If

​

                Case "up"

​

                    If branch = "left" And tree(current).rightpointer <> nullpointer Then

                        Console.WriteLine(tree(current).value)

                        direction = "down"

                        branch = "right"

                    End If

​

                    If tree(current).leftpointer <> nullpointer And tree(current).rightpointer = nullpointer Then

                        Console.WriteLine(tree(current).value)

                    End If

​

            End Select

​

            If tree(current).rightpointer = nullpointer And current = root Then

                branch = "right"

                direction = "up"

            End If

​

        Loop

​

    End Sub

​

    Public Sub additem(tree() As BinTree, ByRef current As Integer, ByRef free As Integer, root As Integer, num As Integer)

        Dim prev As Integer

        Dim path As String

        checkforfree(tree, free)

        current = root

        Do

            prev = current

            Select Case num

                Case < tree(current).value

                    current = tree(current).leftpointer

                    path = "left"

                Case >= tree(current).value

                    current = tree(current).rightpointer

                    path = "right"

            End Select

        Loop Until current = nullpointer

        If path = "left" Then

            tree(prev).leftpointer = free

        Else

            tree(prev).rightpointer = free

        End If

        tree(free).value = num

        tree(free).leftpointer = nullpointer

        tree(free).rightpointer = nullpointer

        tree(free).prevpointer = prev

    End Sub

​

    Public Sub checkforfree(tree() As BinTree, ByRef free As Integer)

        For i = 0 To 19

            If tree(i).value = 0 Then

                free = i

                i = 19

            End If

        Next

    End Sub

​

​

​

End Module

​

​