Module Arbol

    Class Arbol
        Private Enum Sentido
            IZQUIERDA
            CENTRO
            DERECHA
        End Enum
   
        Private izq, der As Arbol
        Private entero As Integer

        Private Sub New()
        End Sub

        Private Sub New(ByVal entero As Integer)
            izq = Nothing
            der = Nothing
            Me.entero = entero
        End Sub

        Public Shared Function insertar(ByVal nodo As Arbol, ByVal entero As Integer) As Arbol
            If nodo Is Nothing Then
                nodo = New Arbol(entero)
            ElseIf entero < nodo.entero Then
                nodo.izq = insertar(nodo.izq, entero)
            Else
                nodo.der = insertar(nodo.der, entero)
            End If
            Return nodo
        End Function

        Public Shared Function quitar(ByVal nodo As Arbol, ByVal entero As Integer) As Arbol
            Return quitar(nodo, entero, Sentido.IZQUIERDA)
        End Function

        Private Shared Function quitar(ByVal nodo As Arbol, ByVal entero As Integer, ByVal rotacion As Sentido) As Arbol
            If nodo IsNot Nothing Then
                If entero = nodo.entero Then
                    Dim pivote As Arbol
                    If nodo.izq Is Nothing Then
                        pivote = nodo.der
                    ElseIf nodo.der Is Nothing Then
                        pivote = nodo.izq
                    ElseIf rotacion = Sentido.IZQUIERDA
                        pivote = nodo.izq
                        While pivote.der IsNot Nothing
                            pivote = pivote.der
                        End While
                        pivote.der = nodo.der
                        pivote = nodo.izq
                    Else
                        pivote = nodo.der
                        While pivote.izq IsNot Nothing
                            pivote = pivote.izq
                        End While
                        pivote.izq = nodo.izq
                        pivote = nodo.der
                    End If
                    nodo = pivote
                ElseIf entero < nodo.entero Then
                    nodo.izq = quitar(nodo.izq, entero, rotacion)
                Else
                    nodo.der = quitar(nodo.der, entero, rotacion)
                End If
            End If
            Return nodo
        End Function

        Public Shared Sub preorden(ByVal raiz As Arbol, ByVal nodo As Arbol)
            If nodo IsNot Nothing Then
                Dim pivote As Arbol = raiz
                Dim hermanos As Integer = 0
                Dim direccion As Sentido = Sentido.CENTRO
                Dim borde1, borde2 As Char
                While pivote IsNot nodo
                    Console.Write(IIf(hermanos = 2 And direccion = Sentido.IZQUIERDA, ChrW(&H2502), " ") & " ")
                    hermanos = 0
                    If pivote.izq IsNot Nothing Then
                        hermanos += 1
                    End If
                    If pivote.der IsNot Nothing Then
                        hermanos += 1
                    End If
                    If nodo.entero < pivote.entero Then
                        pivote = pivote.izq
                        direccion = Sentido.IZQUIERDA
                    Else
                        pivote = pivote.der
                        direccion = Sentido.DERECHA
                    End If
                End While
                borde1 = IIf(direccion = Sentido.CENTRO, ChrW(&H2500), IIf(hermanos = 1 Or direccion = Sentido.DERECHA, ChrW(&H2514), ChrW(&H251C)))
                borde2 = IIf(nodo.izq IsNot Nothing Or nodo.der IsNot Nothing, ChrW(&H252C), ChrW(&H2500))
                Console.WriteLine(borde1 & ChrW(&H2500) & borde2 & " " & nodo.entero)
                preorden(raiz, nodo.izq)
                preorden(raiz, nodo.der)
            End If
        End Sub

        Public Shared Sub inorden(ByVal raiz As Arbol, ByVal nodo As Arbol)
            If nodo IsNot Nothing Then
                inorden(raiz, nodo.izq)
                Dim pivote As Arbol = raiz
                Dim direccion As Sentido = Sentido.CENTRO
                Dim borde1, borde2 As Char
                While pivote IsNot nodo
                    If nodo.entero < pivote.entero Then
                        Console.Write(IIf(direccion = Sentido.DERECHA, ChrW(&H2502), " ") & " ")
                        pivote = pivote.izq
                        direccion = Sentido.IZQUIERDA
                    Else
                        Console.Write(IIf(direccion = Sentido.IZQUIERDA, ChrW(&H2502), " ") & " ")
                        pivote = pivote.der
                        direccion = Sentido.DERECHA
                    End If
                End While
                Select Case direccion
                    Case Sentido.IZQUIERDA
                        borde1 = ChrW(&H250C)
                    Case Sentido.CENTRO
                        borde1 = ChrW(&H2500)
                    Case Sentido.DERECHA
                        borde1 = ChrW(&H2514)
                End Select
                If nodo.izq IsNot Nothing And nodo.der IsNot Nothing Then
                    borde2 = ChrW(&H253C)
                ElseIf nodo.izq IsNot Nothing Then
                    borde2 = ChrW(&H2534)
                ElseIf nodo.der IsNot Nothing Then
                    borde2 = ChrW(&H252C)
                Else
                    borde2 = ChrW(&H2500)
                End If
                Console.WriteLine(borde1 & ChrW(&H2500) & borde2 & " " & nodo.entero)
                inorden(raiz, nodo.der)
            End If
        End Sub

        Public Shared Sub postorden(ByVal raiz As Arbol, ByVal nodo As Arbol)
            If nodo IsNot Nothing Then
                postorden(raiz, nodo.izq)
                postorden(raiz, nodo.der)
                Dim pivote As Arbol = raiz
                Dim hermanos As Integer = 0
                Dim direccion As Sentido = Sentido.CENTRO
                Dim borde1, borde2 As Char
                While pivote IsNot nodo
                    Console.Write(IIf(hermanos = 2 And direccion = Sentido.DERECHA, ChrW(&H2502), " ") & " ")
                    hermanos = 0
                    If pivote.izq IsNot Nothing Then
                        hermanos += 1
                    End If
                    If pivote.der IsNot Nothing Then
                        hermanos += 1
                    End If
                    If nodo.entero < pivote.entero Then
                        pivote = pivote.izq
                        direccion = Sentido.IZQUIERDA
                    Else
                        pivote = pivote.der
                        direccion = Sentido.DERECHA
                    End If
                End While
                borde1 = IIf(direccion = Sentido.CENTRO, ChrW(&H2500), IIf(hermanos = 1 Or direccion = Sentido.IZQUIERDA, ChrW(&H250C), ChrW(&H251C)))
                borde2 = IIf(nodo.izq IsNot Nothing Or nodo.der IsNot Nothing, ChrW(&H2534), ChrW(&H2500))
                Console.WriteLine(borde1 & ChrW(&H2500) & borde2 & " " & nodo.entero)
            End If
        End Sub

        Public Shared Function altura(ByVal nodo As Arbol) As Integer
            If nodo Is Nothing Then
                Return 0
            Else
                Return 1 + Math.max(altura(nodo.izq), altura(nodo.der))
            End If
        End Function

        Public Shared Function balancear(ByVal nodo As Arbol) As Arbol
            If nodo IsNot Nothing Then
                nodo.izq = balancear(nodo.izq)
                nodo.der = balancear(nodo.der)
                Dim diferencia As Integer = altura(nodo.izq) - altura(nodo.der)
                If diferencia > 1 Or diferencia < -1 Then
                    Dim entero As Integer = nodo.entero
                    nodo = balancear(insertar(quitar(nodo, entero, IIf(diferencia > 1, Sentido.DERECHA, Sentido.IZQUIERDA)), entero))
                End If
            End If
            Return nodo
        End Function

        Public Shared Function nodos(ByVal nodo As Arbol) As Integer
            If nodo Is Nothing Then
                Return 0
            Else
                Return 1 + nodos(nodo.izq) + nodos(nodo.der)
            End If
        End Function

        Public Shared Function completo(ByVal nodo As Arbol) As Boolean
            If nodo Is Nothing Then
                Return True
            Else
                Return nodos(nodo.izq) = nodos(nodo.der) And completo(nodo.izq) And completo(nodo.der)
            End If
        End Function

        Public Shared Function balanceado(ByVal nodo As Arbol) As Boolean
            If nodo Is Nothing Then
                Return True
            End If
            Dim diferencia As Integer = altura(nodo.izq) - altura(nodo.der)
            Return diferencia >= -1 And diferencia <= 1 And balanceado(nodo.izq) And balanceado(nodo.der)
        End Function

    End Class

    Sub Main()
        Dim raiz As Arbol = Nothing
        Dim opcion As Char
        Dim entero, i As Integer
        Dim rand As Random = New Random()
        Do
            Console.Clear()
            Console.WriteLine("MEN" & ChrW(&HDA))
            Console.WriteLine("1.- Insertar entero")
            Console.WriteLine("2.- Insertar n" & ChrW(&HFA) & "meros aleatorios")
            Console.WriteLine("3.- Quitar entero")
            Console.WriteLine("4.- Listado en preorden")
            Console.WriteLine("5.- Listado en inorden")
            Console.WriteLine("6.- Listado en postorden")
            Console.WriteLine("7.- Balancear")
            Console.WriteLine("8.- Consultar propiedades")
            Console.WriteLine("9.- Salir" & vbCrLf)
            Console.Write("Seleccione una opci" & ChrW(&HF3) & "n: ")
            Do
                opcion = Console.ReadKey(True).KeyChar
            Loop While opcion < "1" Or opcion > "9"
            Console.WriteLine(opcion & vbCrLf)
            If raiz Is Nothing And opcion <> "1" And opcion <> "2" And opcion <> "8" And opcion <> "9" Then
                Console.WriteLine("El " & ChrW(&HE1) & "rbol est" & ChrW(&HE1) & " vac" & ChrW(&HED) & "o.")
            Else
                Select Case opcion
                    Case "1"
                        Console.Write("Ingrese el entero a insertar: ")
                        entero = Integer.Parse(Console.ReadLine())
                        raiz = Arbol.insertar(raiz, entero)
                        Console.WriteLine(vbCrLf & "Entero agregado correctamente.")
                    Case "2":
                        Console.Write("Ingrese la cantidad de n" & ChrW(&HFA) & "meros a insertar: ")
                        entero = Integer.Parse(Console.ReadLine())
                        For i = 1 To entero
                            raiz = Arbol.insertar (raiz, rand.Next(2000) - 1000)
                        Next i
                        Console.WriteLine(vbCrLf & "N" & ChrW(&HFA) & "meros agregados correctamente.")
                    Case "3"
                        Console.Write("Ingrese el entero a quitar: ")
                        entero = Integer.Parse(Console.ReadLine())
                        raiz = Arbol.quitar(raiz, entero)
                        Console.WriteLine(vbCrLf & "Entero borrado correctamente.")
                    Case "4"
                        Arbol.preorden(raiz, raiz)
                    Case "5"
                        Arbol.inorden(raiz, raiz)
                    Case "6"
                        Arbol.postorden(raiz, raiz)
                    Case "7":
                        raiz = Arbol.balancear(raiz)
                        Console.WriteLine(ChrW(&HC1) & "rbol balanceado correctamente.")
                    Case "8":
                        Console.WriteLine("Altura    : " & Arbol.altura(raiz))
                        Console.WriteLine("Nodos     : " & Arbol.nodos (raiz))
                        Console.WriteLine("Completo  : " & IIf(Arbol.completo  (raiz), "si", "no"))
                        Console.WriteLine("Balanceado: " & IIf(Arbol.balanceado(raiz), "si", "no"))
                End Select
            End If
            If opcion <> "9" Then
                Console.WriteLine()
                Shell ("cmd /c pause", AppWinStyle.NormalFocus, True)
            End If
        Loop While opcion <> "9"
    End Sub

End Module