|
1
8
9 import java.util.*;
10
11 public class BinarySearchTree {
12 Node root;
13 int size;
14
15 static class Node {
16 Node left;
17 Node right;
18 Comparable  info;
19 }
20
21 static final class Wrapper {
22 Object o;
23 Wrapper(Object o) {
24 this.o = o;
25 }
26 public boolean equals(Object o) {
27 if (!(o instanceof Wrapper)) return false;
28 return this.o == ((Wrapper)o).o;
29 }
30 public int hashCode() {
31 return System.identityHashCode(o);
32 }
33 }
34
35 boolean repOk() {
36 if (root==null) return size==0;
37 if (!isTree()) return false;
38 if (numNodes(root)!=size) return false;
39 if (!isOrdered(root,null,null)) return false;
40 return true;
41 }
42
43 boolean isTree() {
44 Set visited = new HashSet();
45 visited.add(new Wrapper(root));
46 LinkedList workList = new LinkedList();
47 workList.add(root);
48 while (!workList.isEmpty()) {
49 Node current = (Node)workList.removeFirst();
50 if (current.left!=null) {
51 if (!visited.add(new Wrapper(current.left))) return false;
52 workList.add(current.left);
53 }
54 if (current.right!=null) {
55 if (!visited.add(new Wrapper(current.right))) return false;
56 workList.add(current.right);
57 }
58 }
59 return true;
60 }
61
62 int numNodes(Node n) {
63 if (n==null) return 0;
64 return 1 + numNodes(n.left) + numNodes(n.right);
65 }
66
67 boolean isOrdered(Node n, Comparable min, Comparable max) {
68 if ((min!=null && n.info.compareTo(min)<=0) ||
69 (max!=null && n.info.compareTo(max)>=0)) return false;
70 if (n.left!=null)
71 if (!isOrdered(n.left,min,n.info)) return false;
72 if (n.right!=null)
73 if (!isOrdered(n.right,n.info,max)) return false;
74 return true;
75 }
76
77 static Node create(int i) {
78 if (i==0) return null;
79 Node n = new Node();
80 n.left = create(i-1);
81 n.right = create(i-1);
82 return n;
83 }
84
85 public static void main(String [] args) {
86 BinarySearchTree x = new BinarySearchTree();
87 x.root = create(5);
88 x.repOk();
89 }
90
91 }
92 |
Popular Tags |
Java API By Example, From Geeks To Geeks.