scala中的二叉树遍历
scala中的二叉树遍历
提问于 2012-10-08 05:21:53
给定的二叉树定义：
// 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)
}
}回答 2
Stack Overflow用户
发布于 2019-01-31 18: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))
}Stack Overflow用户
发布于 2012-10-09 02: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))
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/12772964
复制相关文章
相似问题
腾讯云开发者
