Subato

Resource Files

Ein binärer Suchbaum

In dieser Aufgabe wird zur Realisierung einer Mengenstruktur eine Implementierung eines binären Suchbaums umgesetzt.


nub :: Eq a => [a] -> [a] union :: Eq a => [a] -> [a] -> [a] intersect :: Eq a => [a] -> [a] -> [a] > module Tree where > data Tree a = class Tree<A extends Comparable<? super A>>{ > Empty boolean isEmpty = true; Tree(){} > |Branch (Tree a) a (Tree a) Tree<A> left = null; A element = null; Tree<A> right = null; private Tree(Tree<A> l,A e,Tree<A> r){ left = l; element = e; right = r; isEmpty = false; } > deriving (Show) > size :: Num a => Tree t -> a > size _ = 0 long size(){ if (isEmpty) return 0; return 1 + left.size() + right.size(); } > add :: Ord a => a -> Tree a -> Tree a > add _ t = t void add(A e){ if (isEmpty) { left = new Tree<>(); right = new Tree<>(); element = e; }else if (e.compareTo(element)<0){ left.add(e); }else { right.add(e); } } > infixr 5 +> > (+>) el t = add el t 00002BinTree$ ghci solution/Tree.lhs GHCi, version 8.6.5: http://www.haskell.org/ghc/ :? for help [1 of 1] Compiling Tree ( solution/Tree.lhs, interpreted ) Ok, one module loaded. *Tree> let t1 = 17 +> 42 +> -1 +> 100 +> 576576576 +> Empty *Tree> t1 Branch (Branch (Branch Empty (-1) (Branch (Branch Empty 17 Empty) 42 Empty)) 100 Empty) 576576576 Empty *Tree> size t1 5 *Tree> > contains :: Ord a => a -> Tree a -> Bool > contains _ _ = False boolean contains(A e){ if (isEmpty) return false; if (e.compareTo(element)==0) return true; if (e.compareTo(element)<0) return left.contains(e); return right.contains(e); } > remove :: Ord a => a -> Tree a -> Tree a > remove _ t = t void remove(A e){ if (isEmpty) return; if (e.compareTo(element)<0) left.remove(e); else if (e.compareTo(element)>0) right.remove(e); else rebuild(left,right); } private void rebuild(Tree<A> l,Tree<A> r){ if (l.isEmpty) { left = r.left; element = r.element; right = r.right; isEmpty = r.isEmpty; }else if (r.isEmpty) { left = l.left; element = l.element; right = l.right; isEmpty = l.isEmpty; }else { element = l.element; left = l.left; right.rebuild(l.right,r); } } > infixr 5 >- > (>-) t el = remove el t > inorder :: Tree t -> [t] > inorder _ = [] java.util.List<A> inorder(){ var result = new java.util.ArrayList<A>(); inorder(result); return result; } void inorder(java.util.List<A> result){ if (isEmpty) return; left.inorder(result); result.add(element); right.inorder(result); } > reduce :: Ord t => t1 -> (t1 -> t -> t1) -> Tree t -> t1 > reduce x _ _ = x <B> B reduce(B start,java.util.function.BiFunction<B,A,B> f){ if (isEmpty) return start; remove(element); return reduce(f.apply(start,element),f); } } //end of class Tree > infixl 5 \/ > (\/) :: Ord a => Tree a -> Tree a -> Tree a > xs \/ ys = Empty > infixl 5 /\ > (/\) :: Ord a => Tree a -> Tree a -> Tree a > xs /\ ys = Empty > instance (Ord a) => Eq (Tree a) where > _ == _ = False > tmap :: (Ord a,Ord b) => (a -> b) -> Tree a -> Tree b > tmap f xs = Empty > s1 = 56 +> 5 +> 67 +> 17 +> 4 > +> -576 +> 42 +> 1000000078979887657 +> Empty > t2 = "hallo" +> "welt" +> "witzebitzelbritz" > +> "pandudel" +> "sowieso" +> "klaro" +> Empty > summe = reduce 0 (+) > > produkt = reduce 1 (*) > mappe _ Empty = Empty > mappe f (Branch l el r) = Branch (mappe f l)(f el)(mappe f r) > mapReduce f s op Empty = s > mapReduce f s op (Branch l el r) > = (f el) `op` (mapReduce f s op l) `op` (mapReduce f s op r) > > mapReduce2 f s op tree = reduce s op $ mappe f tree > size2 = \t -> summe $mappe (\x->1) t > size3 = mapReduce (\_->1) 0 (+) > containsWithProp p tree = reduce False (||) $ mappe (\x-> p x) tree > haslongelement :: Tree [a] -> Bool > haslongelement = containsWithProp (\x->length x > 10)
lhs