hangscer

scala写算法-Tree.delete以及print等方法补充

2017/04/19

本程序意在实现算法本身,并不涉及scala的范型以及协变逆变等等概念.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
trait Tree{self=>
import Tree.compare
def findMin:Tree=self match {
case EmptyTree => EmptyTree
case Node(_,left,_) => left match {
case EmptyTree => self
case _ => left.findMin
}
}
def findMax:Tree=self match {
case EmptyTree => EmptyTree
case Node(_,_,right)=> right match {
case EmptyTree => self
case _ => right.findMax
}
}
def delete(x:Int):Tree=self match {
case EmptyTree => EmptyTree
case Node(value,left,right)=> compare(x,value) match { //返回 1 或者 0 或者 -1 ,0代表x==value 即为找到了将被删除的节点
case 1 =>Node(value,left,right.delete(x))
case 0 =>(left,right) match {
case (_,_) if(left!=EmptyTree&&right!=EmptyTree) =>right.findMin match {
//当被删除节点有两个节点时 该节点被右节点的最小值取代(v) 同时将最小值v从右节点删除
case Node(v,_,_)=>Node(v,left,right.delete(v))
}
case (_,_) if(left==EmptyTree) =>right // 当被删除节点没有左节点时 将其右节点返回 即可删除该节点
case (_,_) if(right==EmptyTree) =>left // 当被删除节点没有右节点时 将其左节点返回 即可删除该节点
}
case -1=>Node(value,left.delete(x),right)
}
}
def print:Unit={
def loop(tree:Tree,height:Int):Unit=tree match {
case EmptyTree =>Unit
case Node(value,left,right) =>
loop(right,height+1)
println(" "*height+value)
loop(left,height+1)
}
loop(self,1)
}
}