第4章树

二叉查找树

  1 public class BinarySearchTree<AnyType extends Comparable<? super AnyType>>
  2 {
  3     private static class BinaryNode<AnyType> 
  4     {
  5         BinaryNode(AnyType theElement) 
  6         {
  7             this(theElement, null, null);
  8         }
  9 
 10         BinaryNode(AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt) 
 11         {
 12             element = theElement;
 13             left = lt;
 14             right = rt;
 15         }
 16 
 17         AnyType element;
 18         BinaryNode<AnyType> left;
 19         BinaryNode<AnyType> right;
 20     }
 21 
 22     private BinaryNode<AnyType> root;
 23 
 24     public BinarySearchTree() 
 25     {
 26         root = null;
 27     }
 28 
 29     public void makeEmpty() 
 30     {
 31         root = null;
 32     }
 33 
 34     public boolean isEmpty() 
 35     {
 36         return root == null;
 37     }
 38 
 39     public boolean contains(AnyType x)
 40     { return contains(x, root); }
 41     public AnyType findMin()
 42     {
 43         if (isEmpty()) throw new UnderflowException();
 44         return findMin(root).element;
 45     }
 46     public AnyType findMax()
 47     {
 48         if (isEmpty()) throw new UnderflowException();
 49         return findMax(root).element;
 50     }
 51     public void insert(AnyType x)
 52     {
 53         root = insert(x, root);
 54     }
 55     public void remove(AnyType x)
 56     {
 57         root = remove(x, root);
 58     }
 59 
 60     private boolean contains(AnyType x, BinaryNode<AnyType> t)
 61     {
 62         if (t == null)
 63             return false;
 64 
 65         int compareResult = x.compareTo(t.element);
 66 
 67         if (compareResult < 0)
 68             return contains(x, t.left);
 69         if (compareResult > 0)
 70             return contains(x, t.right);
 71         else
 72             return true;
 73     }
 74 
 75     private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t)
 76     {
 77         if (t == null)
 78             return null;
 79         else if (t.left == null)
 80             return t;
 81         return findMin(t.left);
 82     }
 83 
 84     private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t) 
 85     {
 86         if (t != null)
 87             while (t.right != null)
 88                 t = t.right;
 89 
 90         return t;
 91     }
 92 
 93     private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t)
 94     {
 95         if (t == null)
 96             return new BinaryNode<>(x, null, null);
 97 
 98         int compareResult = x.compareTo(t.element);
 99 
100         if (compareResult < 0)
101             t.left = insert(x, t.left);
102         if (compareResult > 0)
103             t.right = insert(x, t.right);
104         else
105             ;
106         return t;
107     }
108 
109     private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t)
110     {
111         if (t == null)
112             return t;
113 
114         int compareResult = x.compareTo(t.element);
115 
116         if (compareResult < 0)
117             t.left = remove(x, t.left);
118         else if (compareResult > 0)
119             t.right = remove(x, t.right);
120         else if (t.left != null && t.right != null)
121         {
122             t.element = findMin(t.right).element;
123             t.right = remove(t.element, t.right);
124         }
125         else
126             t = (t.left != null) ? t.left : t.right;
127         return t;
128     }
129 
130     public void printTree()
131     {
132         if (isEmpty())
133             System.out.println("Empty tree");
134         else
135             printTree(root);
136     }
137 
138     public void printTree(BinaryNode<AnyType> t)
139     {
140         if (t != null)
141         {
142             printTree(t.left);
143             System.out.println(t.element);
144             printTree(t.right);
145         }
146     }
147 }

1 public class UnderflowException extends RuntimeException {
2 }

懒惰删除：当一个元素要被删除时，它仍留在树中，而只是被标记为删除。

AVL树

  1 public class AvlTree<AnyType extends Comparable<? super AnyType>>
  2 {
  3     public AvlTree() { root = null; }
  4     
  5     public void insert(AnyType x){ root = insert(x, root); }
  6     public void remove(AnyType x){ root = remove(x, root); }
  7     
  8     private AvlNode<AnyType>remove(AnyType x, AvlNode<AnyType> t)
  9     {
 10         if (t == null)
 11             return t;
 12         
 13         int compareResult = x.compareTo(t.element);
 14         
 15         if (compareResult < 0)
 16             t.left = remove(x, t.left);
 17         else if (compareResult > 0)
 18             t.right = remove(x, t.right);
 19         else if (t.left != null && t.right != null)
 20         {
 21             t.element = findMin(t.right).element;
 22             t.right = remove(t.element, t.right);
 23         }
 24         else 
 25             t = (t.left != null) ? t.left : t.right;
 26         return balance(t);
 27     }
 28     
 29     public AnyType findMin()
 30     {
 31         if (isEmpty())
 32             throw new UnderflowException();
 33         return findMin(root).element;
 34     }
 35     
 36     public AnyType findMax()
 37     { 
 38         if (isEmpty())
 39             throw new UnderflowException();
 40         return findMin(root).element;
 41     }
 42     
 43     public boolean contains(AnyType x){ return contains(x, root); }
 44     
 45     public void makeEmpty(){ root = null; }
 46     
 47     public boolean isEmpty(){ return root == null; }
 48     
 49     public void printTree()
 50     {
 51         if (isEmpty())
 52             System.out.println("Empty tree");
 53         else 
 54             printTree(root);
 55     }
 56     
 57     private static final int ALLOWED_IMBALANCE = 1;
 58     
 59     private AvlNode<AnyType>balance(AvlNode<AnyType>t)
 60     {
 61         if (t == null)
 62             return t;
 63      
 64         if (height(t.left) - height(t.right) > ALLOWED_IMBALANCE)
 65             if (height(t.left.left) - height(t.left.right) > ALLOWED_IMBALANCE)
 66                 t = rotateWithLeftChild(t);
 67             else 
 68                 t = doubleWithLeftChild(t);
 69         
 70         if (height(t.right) - height(t.left) > ALLOWED_IMBALANCE)
 71             if (height(t.right.right) - height(t.right.left) > ALLOWED_IMBALANCE)
 72                 t = rotateWithRightChild(t);
 73             else 
 74                 t = doubleWithRightChild(t);
 75             
 76         t.height = Math.max(height(t.left), height(t.right)) + 1;
 77         return t;
 78     }
 79     
 80     public void checkBalance(){ checkBalance(root); }
 81     
 82     private int checkBalance(AvlNode<AnyType> t)
 83     { 
 84         if (t == null)
 85             return -1;
 86         
 87         if (t != null)
 88         {
 89             int hl = checkBalance(t.left);
 90             int hr = checkBalance(t.right);
 91             if (Math.abs(height(t.left) - height(t.right)) > 1 || height(t.left) != hl || height(t.right) != hr)
 92                 System.out.println("OOPS");
 93         }
 94         
 95         return height(t);
 96     }
 97     
 98     private AvlNode<AnyType> insert(AnyType x, AvlNode<AnyType>t)
 99     {
100         if (t == null)
101             return new AvlNode<>(x, null, null);
102         
103         int compareResult = x.compareTo(t.element);
104         
105         if (compareResult < 0)
106             t.left = insert(x, t.left);
107         else if (compareResult > 0)
108             t.right = insert(x, t.right);
109         else 
110             ;
111         return balance(t);
112     }
113     private AvlNode<AnyType> findMin(AvlNode<AnyType> t)
114     {
115         if (t == null)
116             return t;
117         while (t.left != null)
118             t = t.left;
119 
120         return t;
121     }
122 
123     private AvlNode<AnyType>findMax(AvlNode<AnyType> t)
124     {
125         if (t == null)
126             return t;
127         while (t.right != null)
128             t = t.right;
129 
130         return t;
131     }
132     private boolean contains(AnyType x, AvlNode<AnyType> t)
133     {
134         while (t != null)
135         {
136             int compareResult = x.compareTo(t.element);
137             if (compareResult < 0)
138                 t = t.left;
139             else if (compareResult > 0)
140                 t = t.right;
141             else
142                 return true;
143         }
144         return false;
145     }
146 
147     private void printTree(AvlNode<AnyType> t)
148     {
149         if (t != null)
150         {
151             printTree(t.left);
152             System.out.println(t.element);
153             printTree(t.right);
154         }
155     }
156 
157     private int height(AvlNode<AnyType> t){ return t == null ? -1 : t.height; }
158     
159     private AvlNode<AnyType> rotateWithLeftChild(AvlNode<AnyType> k2)
160     {
161         AvlNode<AnyType>k1 = k2.left;
162         k2.left = k1.right;
163         k1.right = k2;
164         k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
165         k1.height = Math.max(height(k1.left), k2.height) + 1;
166         return k1;
167     }
168     
169     private AvlNode<AnyType> rotateWithRightChild(AvlNode<AnyType>k1)
170     {
171         AvlNode<AnyType>k2 = k1.right;
172         k1.right = k2.left;
173         k2.left = k1;
174         k1.height = Math.max(height(k1.left), height(k1.right)) + 1;
175         k2.height = Math.max(height(k2.right), k1.height) + 1;
176         return k2;
177     }
178     
179     private AvlNode<AnyType>doubleWithLeftChild(AvlNode<AnyType> k3)
180     {
181         k3.left = rotateWithRightChild(k3.left);
182         return rotateWithLeftChild(k3);
183     }
184     
185     private AvlNode<AnyType>doubleWithRightChild(AvlNode<AnyType>k1)
186     {
187         k1.right = rotateWithLeftChild(k1.right);
188         return rotateWithRightChild(k1);
189     }
190 
191     private static class AvlNode<AnyType>
192     {
193         AvlNode(AnyType theElement)
194         { this(theElement, null, null); }
195         AvlNode(AnyType theElement, AvlNode<AnyType>lt, AvlNode<AnyType>rt)
196         { element = theElement; left = lt; right = rt; height = 0; }
197 
198         AnyType element;
199         AvlNode<AnyType> left;
200         AvlNode<AnyType> right;
201         int height;
202     }
203 
204     private AvlNode<AnyType> root;
205 }

4.10 编写一个程序，该程序列出一个目录中所有的文件和大小

 1 import java.io.File;
 2 
 3 public class FileList
 4 {
 5     public void list(File f)
 6     {
 7         list(f, 0);
 8     }
 9 
10     public void list(File f, int depth)
11     {
12         printName(f, depth);
13         if (f.isDirectory())
14         {
15             File[] files = f.listFiles();
16             for (File i : files)
17                 list(i, depth + 1);
18         }
19     }
20 
21     void printName(File f, int depth)
22     {
23         String name = f.getName();
24         for (int i = 0; i < depth; i++)
25             System.out.print("      ");
26         if (f.isDirectory())
27             System.out.println("Dir: " + name);
28         else
29             System.out.println(f.getName() + " " + f.length());
30     }
31 }

第4章 树

第4章树