>给定的 bin tree defn :
// 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 )) )) )) )
此树的顺序 SHD 为 : 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)
}
}
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))
}
首先,我认为顺序遍历将导致 3,1,5,9,15 而不是 OP 的 3,5,1,9,15。而且,很抱歉,我无法让您的代码按原样编译。另外,正如保罗所建议的,你混淆了"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))
}
}