0

嘿,我想编写一个函数 delete 给定一棵树,我可以删除树中的一个节点,所以它应该返回原始树减去该节点的节点和子树。每个提示都有帮助,并且提前感谢:)

4

1 回答 1

0
(*declaration for tree *)
datatype 'a tree 
  = Empty
  | Node of 'a tree * 'a * 'a tree

(* function to compare trees *)
fun eqTree (t, t' : ''a tree) : bool =
  case (t, t')
    of (Empty, Empty) => true
     | (Node(l,x,r), Node(l',x',r')) =>
         x = x'       andalso
         eqTree(l,l') andalso
         eqTree(r,r')
     | (Empty, Node _) => false
     | (Node _, Empty) => false 

(* function to remove all trees t' from t *)
fun rmTree (t, t' : ''a tree) = 
  case (t, t')
    of (Empty, Empty) => Empty
     | (Node(l,x,r), Node(l',x',r')) => if x=x' andalso eqTree(l, l') andalso eqTree(r, r') then Empty else Node((rmTree(l,t')), x, rmTree(r,t'))
     | (Empty, Node _) => Empty
     | (Node a, Empty) => Node a ;

(* an example *)
rmTree(rmTree((Node(Node(Empty,3,Empty), 2, Node(Empty,2,Empty))), (Node(Empty,2,Empty))), (Node(Empty,2,Empty))); 
于 2011-07-18T10:16:03.110 回答