函数式编程实验3/华科

编写函数listToTree: int list -> tree，将一个表转换成一棵平衡树。

提示：可调用split函数，split函数定义如下：

如果L非空，则存在L1, x, L2，满足：

split L = (L1, x, L2) 且 L = L1 @ x :: L2 且 length(L1)和length(L2)差值小于1。

datatype tree=Empty | Node of tree*int*tree;

fun split [] =([],[])
  | split [x]=([],[x])
  | split (x::y::L)=let val (A,B)=split L
		        				in (x::A,y::B)
 			   						end;

fun listToTree []=Empty
  | listToTree L=let val( l1 , x::r1 ) = split L
		             in Node(listToTree l1,x,listToTree r1)
		             end; 

对于递归的深刻理解（在这门课上，上课听讲，会对递归有一个更深的认识），listToTree得到的是平衡树

Node(listToTree l1 , x , listToTree r1)得到的一定也是平衡树

编写函数revT: tree -> tree，对树进行反转，使trav(revT t) = reverse(trav t)。（trav为树的中序遍历函数）。假设输入参数为一棵平衡二叉树，验证程序的正确性，并分析该函数的执行性能（work和span）。

fun revT Empty:tree=Empty:tree
 |  revT (Node(l1,x,r1))=Node(revT r1,x,revT l1);

同上，递归的思路，大一上的数据结构课里有类似的递归算法

work = O(n)

span = O(log n)

编写函数binarySearch: tree * int -> bool。当输入参数1为有序树时，如果树中包含值为参数2的节点，则返回true；否则返回false。要求：程序中请使用函数Int.compare（系统提供），不要使用<, =, >。

datatype order = GREATER | EQUAL | LESS

fun binarySearch (Empty,x)=false
 |  binarySearch (Node(L,x,R),y)= 
										case Int.compare(x,y) of
										EQUAL => true
										| 	_ 	 => binarySearch(L,y) orelse binarySearch(R,y);

还是数据结构里树的思想

一棵minheap树定义为： 1. t is Empty; 2. t is a Node(L, x, R), where R, L are minheaps and values(L), value® >= x (value(T)函数用于获取树T的根节点的值）

编写函数

treecompare, SwapDown 和heapify：treecompare: tree * tree -> order(* when given two trees, returns a value of type order, based on which tree has a largervalue at the root node *)

fun treecompare (Empty,Empty) = EQUAL
|   treecompare (Node(l,x,r),Empty)=GREATER
|   treecompare (Empty,Node(l,x,r))=LESS
|   treecompare (Node(l1,x,r1),Node(l2,y,r2))=Int.compare(x,y);

SwapDown: tree -> tree(* REQUIRES the subtrees of t are both minheaps* ENSURES swapDown(t) = if t is Empty or all of t’s immediate children are empty then* just return t, otherwise returns a minheap which contains exactly the elements in t. *)

fun SwapDown Empty=Empty
  | SwapDown (Node(Empty,x,Empty))=Node(Empty,x,Empty)
  | SwapDown (Node(Empty,x,R)) =
	    					let val Node(l,t,r) = R
								in	case Int.compare(x,t) of
										GREATER => Node(Empty,t,SwapDown(Node(l,x,r)))
										| _ => Node(l,t,r)
								end
	| SwapDown (Node(L,x,Empty)) =
								let val Node(l,t,r) = L
								in	case Int.compare(x,t) of
										GREATER => Node(SwapDown(Node(l,x,r)),t,Empty)
										| _ => Node(l,t,r)
								end
	| SwapDown (Node(L,x,R))=
								let val Node(l1,x1,r1)=L val Node(l2,x2,r2)=R
			    			in 
 										case treecompare(L,R) of
 										GREATER => if Int.compare(x,x2)=GREATER 
 												 						then Node(L,x2,SwapDown(Node(l2,x,r2)))
 				  									 	 else Node(L,x,R)
										|  _	=> if Int.compare(x,x1)=GREATER
						    									  then Node(SwapDown(Node(l1,x,r1)),x1,R)
				  		     						 else Node(L,x,R)
								 end;

可以参考数据结构堆排序，最小堆