问scala中的二叉树遍历
EN

Stack Overflow用户

提问于 2012-10-07 21:21:53

回答 2查看 6K关注 0票数 2

给定的二叉树定义：

// a binary tree node
 case class Node( var data:(Int), 
     left:Option[Node],
     right:Option[Node] 
       )

我需要得到二叉树的顺序树遍历。例如：

val testtree = Node( (3),
                     None,
                     Some(Node( (5),
                                Some(Node( (1),
                                     None,
                                     None )),
                             Some(Node( (9),
                                      None,
                                      Some(Node( (15), 
                                                 None,
                                                 None )) ))  ))  )

这棵树的顺序应该是: 3,5,1,9,15

我尝试过的代码：

 def inOrder(t: Node): Unit ={  
   def print(data:Int,t:Option[Node]):Unit={
      if(t!=None)
                    {
                        print(data,t.left)
            Console.print(data)
            print(data,t.right)
        }      
   }
   print(t.data,t)  
 }

但这并不能解决问题。谁能帮帮我。

完整代码：

    case class Node( var data:(Int), 
         left:Option[Node],
         right:Option[Node] 
           )

object Ch15 {

  def main( args:Array[String] ) = {
   val tree =Node( (3), None,Some(Node( (5), Some(Node( (1), None, None )), Some(Node( (9), None,Some(Node( (15), None, None )) )) )) )    
   inOrder( tree ) 
  }

  def inOrder(t: Node): Unit ={  
   def print(data:Int,t:Option[Node]):Unit={
      if(t!=None)
      {
            print(data,t.left)
            Console.print(data)
            print(data,t.right)
        }      
   }
   print(t.data,t)  
 }

}

scala

binary-tree

回答 2

Stack Overflow用户

发布于 2019-01-31 10:52:20

case class Branch(node: Int, left: Option[Branch] = None, right: Option[Branch] = None)

object TreeTraverse extends App {
  val branch = Branch(1, Some(Branch(2, Some(Branch(4)), Some(Branch(5)))), Some(Branch(3, Some(Branch(6)), Some(Branch(7)))))

  def preOrder(branch: Branch): Unit = {
    print(branch.node)
    if (branch.left.isDefined) preOrder(branch.left.get)
    if (branch.right.isDefined) preOrder(branch.right.get)
  }

  def inOrder(branch: Branch): Unit = {
    if (branch.left.isDefined) inOrder(branch.left.get)
    print(branch.node)
    if (branch.right.isDefined) inOrder(branch.right.get)
  }

  def postOrder(branch: Branch): Unit = {
    if (branch.left.isDefined) postOrder(branch.left.get)
    if (branch.right.isDefined) postOrder(branch.right.get)
    print(branch.node)
  }

  println("  -> PreOrder" + preOrder(branch))
  println("  -> InOrder " + inOrder(branch))
  println("  -> PostOrder " + postOrder(branch))
}

票数 4

Stack Overflow用户

发布于 2012-10-08 18:42:36

首先，我认为顺序遍历将导致3,1,5,9,15，而不是OP的3,5,1,9,15。很抱歉，我不能按原样编译您的代码。此外，正如Paul建议的那样，您混淆了“t”。

以下是我对实现的看法：

object Ch15 {
  def main( args:Array[String] ) = {
   val tree =Node( (3), None,Some(Node( (5), Some(Node( (1), None, None )), Some(Node( (9), None,Some(Node( (15), None, None )) )) )) )    
   inOrder( tree ) 
  }

  def inOrder(t: Node): Unit ={  
    def printNode(node:Option[Node]):Unit={
      node match {
        case Some(aliveNode) => {
          printNode(aliveNode.left)
          Console.print(aliveNode.data + ", ")
          printNode(aliveNode.right)
        }
        case None => {}
      }
    }
    printNode(Option(t))  
  }
}