Листинг 32

internal  class Node{
    var iData: Int = 0
    var dData: Double = 0.toDouble()
    var leftChild: Node? = null
    var rightChild: Node? = null

    fun displayNode(){
        print("{$iData, $dData} ")
    }

    internal class Tree{
        private var root: Node?
        init { root = null }

        fun find(key:Int):Node?{
            var current = root
            while (current!!.iData != key){
                if (key < current.iData) current = current.leftChild
                else current = current.rightChild
                if (current == null) return null
            }
            return current
        }

        fun insert(id:Int, dd: Double){
            val newNode = Node()
            newNode.iData = id
            newNode.dData = dd
            if (root == null) root = newNode
            else{
                var current = root
                var parent: Node
                while (true){
                    parent = current
                    if (id < current!!.iData){
                        current = current.leftChild
                        if (current == null){
                            parent.leftChild = newNode
                            return
                        }
                    }else{
                        current = current.rightChild
                        if (current == null){
                            parent.rightChild = newNode
                            return
                        }
                    }
                }
            }
        }

        fun delete(key:Int):Boolean{
            var current = root
            var parent: Node = root
            var isLeftChild = true
            while (current!!.iData != key){
                parent = current
                if (key < current.iData){
                    isLeftChild = true
                    current = current.leftChild
                }else{
                    isLeftChild = false
                    current = current.rightChild
                }
                if (current == null) return false
            }

            if (current.leftChild == null && current.rightChild == null){
                if (current == root) root = null
                else if (isLeftChild) parent.leftChild = null
                else parent.rightChild = null
            }

            else if(current.leftChild == null)
                if (current == root) root = current.leftChild
                else if (isLeftChild) parent.leftChild = current.leftChild
                else parent.rightChild = current.leftChild

            else if (current.leftChild == null)
                if (current == root) root = current.rightChild
                else if (isLeftChild) parent.leftChild = current.rightChild
                else parent.rightChild = current.rightChild

            else{
                var successor = getSuccessor(current)
                if (current == root) root = successor
                else if (isLeftChild) parent.leftChild = successor
                else parent.rightChild = successor
                successor.leftChild = current.leftChild
            }

            return true
        }

        private fun getSuccessor(delNode:Node): Node{
            var successorParent = delNode
            var successor = delNode

            var current = delNode.rightChild
            while (current != null) {
                successorParent = successor
                successor = current
                current = current.leftChild
            }
            if (successor !== delNode.rightChild){
                successorParent.leftChild = successor.rightChild
                successor.rightChild = delNode.rightChild
            }
            return  successor
        }

        private  fun preOrder(localRoot: Node?){
            if (localRoot != null){
                print("${localRoot.iData} ")
                preOrder(localRoot.leftChild)
                preOrder(localRoot.rightChild)
            }
        }

        private  fun inOrder(localRoot: Node?){
            if (localRoot != null){
                inOrder(localRoot.leftChild)
                print("${localRoot.iData} ")
                inOrder(localRoot.rightChild)
            }
        }

        private fun postOrder(localRoot: Node?){
            if (localRoot != null){
                postOrder(localRoot.leftChild)
                postOrder(localRoot.rightChild)
                rint("${localRoot.iData} ")
            }
        }

    }

}