Arvore Binaria em Kotlin

a-testar.md

Testar no play kotlin

BinaryTree.kt

class Root<E>(var value: E, var root: Root<E>?, var left: Root<E>? = null, var right: Root<E>? = null)

enum class Ordem { V, R, L }

interface IBinaryTree<E> {

    val size: Int

    fun insert(element: E)

    fun insertAll(vararg element: E)

    fun search(element: E): Boolean

    fun removePorCopia(element: E): Boolean

    fun removePorFusao(element: E): Boolean

    fun elementsEmOrdem(): List<E>

    fun elementsPreOrdem(): List<E>

    fun elementsPosOrdem(): List<E>

    fun elementsPorNivel(): List<E>
}

class BinaryTree<E> : IBinaryTree<E> {

    var root: Root<E>? = null
    private var _size = 0

    override val size get() = _size

    override fun insert(element: E) {
        if (root == null) {
            root = Root(element, null)
            _size++
        } else {
            if(insertRoot(element, root!!))
                _size++
        }
    }

    private fun insertRoot(element: E, root: Root<E>): Boolean {
        val eHash = element.hashCode()
        val rootHash = root.value.hashCode()
        if(eHash < rootHash) {
            val left = root.left
            if(left != null) {
                insertRoot(element, left)
            } else {
                root.left = Root(element, root)
            }
            return true
        } else if(eHash > rootHash) {
            val right = root.right
            if(right != null) {
                insertRoot(element, right)
            } else {
                root.right = Root(element, root)
            }
            return true
        }
        return false
    }

    override fun insertAll(vararg element: E) {
        for (e in element) insert(e)
    }

    override fun search(element: E): Boolean {
        return findRootFromElement(element) != null
    }

    private fun findRootFromElement(element: E, root: Root<E>? = this.root): Root<E>? {
        if(root == null) return null
        val eHash = element.hashCode()
        val rootHash = root.value.hashCode()

        if(eHash == rootHash) {
            return root
        } else if(eHash < rootHash) {
            return findRootFromElement(element, root.left)
        } else { // >
            return findRootFromElement(element, root.right)
        }
    }

    private fun removeCase1e2(eRoot: Root<E>): Boolean {
        val left = eRoot.left
        val right = eRoot.right

        if(left == null || right == null) {
            if (left != null) {
                if (eRoot === root) root = left
                else {
                    val root = eRoot.root!!
                    if (root.left === eRoot) {
                        root.left = left
                    } else if (root.right == eRoot) {
                        root.right = left
                    }
                }
            } else if (right != null) {
                if (eRoot === root) root = right
                else {
                    val root = eRoot.root!!
                    if (root.left === eRoot) {
                        root.left = right
                    } else if (root.right == eRoot) {
                        root.right = right
                    }
                }
            } else {
                if (eRoot === root) root = null
                else {
                    val root = eRoot.root!!
                    if(root.left === eRoot) {
                        root.left = null
                    } else if(root.right === eRoot) {
                        root.right = null
                    }
                }
            }

            _size--
            return true
        }
        return false
    }

    override fun removePorCopia(element: E): Boolean {
        val eRoot = findRootFromElement(element) ?: return false

        if(!removeCase1e2(eRoot)) {
            val bigger = biggerFromRoot(eRoot.left!!)
            eRoot.value = bigger.value
            removeCase1e2(bigger)
        }

        return true
    }

    override fun removePorFusao(element: E): Boolean {
        val eRoot = findRootFromElement(element) ?: return false

        if(!removeCase1e2(eRoot)) {
            val bigger = biggerFromRoot(eRoot.left!!)
            val right = eRoot.right

            bigger.right = right
            eRoot.right = null

            removeCase1e2(eRoot)
        }

        return true
    }

    private fun biggerFromRoot(root: Root<E>): Root<E> {
        return if(root.right == null) root else biggerFromRoot(root.right!!)
    }

    fun mostrarPorIdentacao() {
        if(root == null) println("Arvore binaria vazia")
        else mostrarPorIdentacao("", root!!)
    }

    private fun mostrarPorIdentacao(indentacao: String, root: Root<E>, right: Boolean? = null) {
        println(indentacao + root.value.toString() + "(${if(right != null) if(right) "right" else "left" else ""})")
        if(root.left != null) {
            mostrarPorIdentacao(indentacao + "\t", root.left!!, false)
        }
        if(root.right != null) {
            mostrarPorIdentacao(indentacao + "\t", root.right!!, true)
        }
    }

    override fun elementsEmOrdem(): List<E> {
        return if(root != null) elementsOrdem(root!!, listOf(Ordem.L, Ordem.V, Ordem.R)) else emptyList()
    }

    private fun elementsOrdem(root: Root<E>, ordens: List<Ordem>): List<E> {
        val list = mutableListOf<E>()

        for (ordem in ordens) {
            when(ordem) {
                Ordem.V -> list += root.value
                Ordem.L -> if(root.left != null) list += elementsOrdem(root.left!!, ordens)
                Ordem.R -> if(root.right != null) list += elementsOrdem(root.right!!, ordens)
            }
        }

        return list
    }

    override fun elementsPreOrdem(): List<E> {
        return if(root != null) elementsOrdem(root!!, listOf(Ordem.V, Ordem.L, Ordem.R)) else emptyList()
    }


    override fun elementsPosOrdem(): List<E> {
        return if(root != null) elementsOrdem(root!!, listOf(Ordem.L, Ordem.R, Ordem.V)) else emptyList()
    }

    override fun elementsPorNivel(): List<E> {
        return if(root != null) elementsPorNivelRoots(listOf(root!!)) else emptyList()
    }

    private fun elementsPorNivelRoots(nivel: List<Root<E>>): List<E> {
        if(nivel.isEmpty()) return emptyList()

        val nextNivelRoots = nivel.flatMap {
            listOfNotNull(it.left, it.right)
        }

        val nivelElements = nivel.map { it.value }

        return nivelElements + elementsPorNivelRoots(nextNivelRoots)
    }

}

Teste.kt

fun main() {
    val tree = BinaryTree<String>()
    tree.insert("Rafaela")
    tree.insert("Gabriel")
    tree.insert("Emily")
    tree.insert("Souza")
    tree.insert("Games")
    tree.insert("Kotlin")

    tree.mostrarPorIdentacao()

    println("-".repeat(30))

    val tree2 = BinaryTree<Int>()
    tree2.insert(5)
    tree2.insert(3)
    tree2.insert(20)
    tree2.insert(15)
    tree2.insert(4)
    tree2.insert(6)
    tree2.insert(7)
    tree2.insert(20)
    tree2.insert(23)

    tree2.mostrarPorIdentacao()

    println()

    println("Tem 15? ${tree2.search(15)}")
    println("Tem 16? ${tree2.search(16)}")

    println()

    println("Pre Ordem: ${tree2.elementsPreOrdem()}")

    println()

    val tree3 = BinaryTree<Char>()
    tree3.insertAll('K', 'G', 'L', 'B', 'A', 'C', 'D', 'L', 'O', 'P', 'U')

    tree3.mostrarPorIdentacao()

    println("Pre Ordem: ${tree3.elementsPreOrdem()}")
    println("Pos Ordem: ${tree3.elementsPosOrdem()}")
    println("Em Ordem: ${tree3.elementsEmOrdem()}")
    println("Por Nivel: ${tree3.elementsPorNivel()}")

    println("-".repeat(30))

    println("Exclusao do P: ${tree3.removePorCopia('P')}") // caso 1 e 2

    println()

    tree3.mostrarPorIdentacao()

    println("-".repeat(30))

    println("Inserindo 4, 7, 5, 8, 9, 1, 2, 0")

    tree3.insertAll('4', '7', '5', '8', '9', '1', '2', '0')

    tree3.mostrarPorIdentacao()

    println("Exclusao do 7 por fusao: ${tree3.removePorFusao('7')}")

    tree3.mostrarPorIdentacao()

    println("-".repeat(30))

    println("Exclusao do 4 por copia: ${tree3.removePorCopia('4')}")

    tree3.mostrarPorIdentacao()
}