二叉検索ツリー(二叉検索ツリーor二叉ソートツリー)(scala)コード実装-データ構造

ツリーの左サブツリーの値はルートノードまたは親ノードより小さく、右サブ数の値はルートノードまたは親ノードより大きく、scalaでツリーの作成、挿入、削除などの操作を実現します.

package com.dxt.tree

/**
  *        
  */
object Learn2Tree {

  class Node {
    var vlaue: Int = _
    var leftNode: Node = _
    var rightNode: Node = _
  }

  //   
  class Tree {
    var root: Node = _ //     

    def insertTree(root: Node, newNode: Node): Unit = {
      if (newNode.vlaue < root.vlaue) {
        //           
        if (root.leftNode == null) {
          root.leftNode = newNode
        } else {
          insertTree(root.leftNode, newNode)
        }
      } else {
        if (root.rightNode == null) {
          root.rightNode = newNode
        } else {
          insertTree(root.rightNode, newNode)
        }
      }
    }

    def insert(v: Int) {
      var newNode: Node = new Node //        
      newNode.vlaue = v //       
      if (root == null) {
        //             ，     Node  root,        null
        root = newNode
      } else {
        //       null，                 ，      ，      
        insertTree(root, newNode) //           ，                ，           
      }
    }

    //            （    ）
    def teavelTree(root: Node) {
      if (root != null) {
        teavelTree(root.leftNode)
        println("value= " + root.vlaue)
        teavelTree(root.rightNode)
      }
    }

    //       
    def travel() {
      teavelTree(root)
    }


    //           
    def min(): Int = {
      var minTree = this.root
      while (!(minTree.leftNode == null)) {
        minTree = minTree.leftNode
      }
      minTree.vlaue
    }

    //          
  def max(): Unit = {
    var maxTree = this.root
    while (!(maxTree.rightNode == null)) {
      maxTree = maxTree.rightNode
    }
    maxTree.vlaue
  }


//        .  ，        ，            ，             

    def find(va: Int): Node = {
      var tmpNode = this.root //       null
      while (tmpNode != null) {
        if (tmpNode.vlaue == va) {
          return tmpNode
        } else if (va < tmpNode.vlaue) {
          tmpNode = tmpNode.leftNode
        } else if (va > tmpNode.vlaue) {
          tmpNode = tmpNode.rightNode
        }
      }
      return tmpNode
    }

      /**
      *         
      * @param node
      * @return
      */
    def getMinValueNode(node: Node): Node = {
      if (node.leftNode == null) {
        return node
      } else {
        return getMinValueNode(node)
      }

    }

      /**
      *     
      * @param node
      * @param value
      * @return
      */
    def removeNode(node: Node, value: Int): Node = {

      if (node == null) {
        return null
      }
      if (node.vlaue == value) {
        //      
        //①        
        if (node.leftNode == null && node.rightNode == null) {
          return null
        }
        //②     
        if (node.leftNode == null) {
          return node.rightNode //       
        }
        //③     
        if (node.rightNode == null) {
          return node.leftNode //       
        }
        //④         ，
        //              ，                                
        var tempNode = getMinValueNode(node.rightNode)
        node.vlaue = tempNode.vlaue
        node.rightNode = removeNode(node.rightNode, tempNode.vlaue)

        return node
      } else if (value < node.vlaue) {

        node.leftNode = removeNode(node.leftNode, value)
        return node.leftNode

      } else {
        node.rightNode = removeNode(node.rightNode, value)
        return node.rightNode

      }
    }
  }

  def main(args: Array[String]): Unit = {
    var tree = new Tree
    tree.insert(50)
    tree.insert(30)
    tree.insert(60)
    //tree.travel()
    println(tree.min())
  }
}

参考記事:https://www.jianshu.com/p/6a4b7f261e99