Subversion Repositories programming

Rev

Rev 35 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 35 Rev 36
Line 31... Line 31...
31 
        this.right = right;
 31 
        this.right = right;
32 
    }
 32 
    }
33 
 
 33 
 
34 
    // copy constructor, creates a tree which has the same structure and
 34 
    // copy constructor, creates a tree which has the same structure and
35 
    // whose nodes reference the same objects as the _that_ tree
 35 
    // whose nodes reference the same objects as the _that_ tree
36 
    public BinaryTree( BinaryTree that ) {
36 
    public BinaryTree( BinaryTree that ) {
- 
 
 37 
        root = that.root;
37 
        System.out.println("Don't use me yet");
 38 
        left = null; right = null;
- 
 
 39
- 
 
 40 
        if( that.left != null ) { left = new BinaryTree(that.left); }
- 
 
 41 
        if( that.right != null ) { right = new BinaryTree(that.right); }
38 
    }
 42 
    }
39 
 
 43 
 
40 
    //getter methods --------------------------------------------------------
 44 
    //getter methods --------------------------------------------------------
41 
 
 45 
 
42 
    // method which returns the root data
 46 
    // method which returns the root data
Line 195... Line 199...
195 
        if( Math.abs(left.height() - right.height()) < 2 ) { return true; }
 199 
        if( Math.abs(left.height() - right.height()) < 2 ) { return true; }
196 
        if( left.isBalanced() && right.isBalanced() ) { return true; }
 200 
        if( left.isBalanced() && right.isBalanced() ) { return true; }
197 
        return false;
 201 
        return false;
198 
    }
 202 
    }
199
203
- 
 
 204 
    // method to get the total path length of the current tree
- 
 
 205 
    // Precondition:  none
- 
 
 206 
    // Postcondition: returns the sum of all the root to node paths in
- 
 
 207 
    //                the tree
200 
    public int pathLength() {
 208 
    public int pathLength() {
201 
        int answer=0;
 209 
        int answer=0;
202 
        Queue queue = new Queue();
 210 
        Queue queue = new Queue();
203 
        queue.enqueue(this);
 211 
        queue.enqueue(this);
204 
 
 212 
 
Line 209... Line 217...
209 
            if( temp.right != null ) { queue.enqueue(temp.right); }
 217 
            if( temp.right != null ) { queue.enqueue(temp.right); }
210 
        }
 218 
        }
211 
 
 219 
 
212 
        return answer;
 220 
        return answer;
213 
    }
 221 
    }
214
222
- 
 
 223 
    // method to create a reverse of the tree
- 
 
 224 
    // Precondition:  none
- 
 
 225 
    // Postcondition: returns a new BinaryTree with the structure
- 
 
 226 
    //                reversed as if it were seen in a mirror
215 
    public BinaryTree reverse() {
227 
    public BinaryTree reverse() {
216 
        //both left and right are null
 228 
        //both left and right are null
217 
        if( this.isLeaf() ) { return new BinaryTree(root); }
 229 
        if( this.isLeaf() ) { return new BinaryTree(root); }
218
230
219 
        //left must be null, right must not be null
 231 
        //left must be null, right must not be null
Line 226... Line 238...
226
238
227 
        //both sides are not null
 239 
        //both sides are not null
228 
        return new BinaryTree(root,right.reverse(),left.reverse());
 240 
        return new BinaryTree(root,right.reverse(),left.reverse());
229 
    }
 241 
    }
230
242
- 
 
 243 
    // a method to find the level of an object in the tree
- 
 
 244 
    // Precondition:  x is not null
- 
 
 245 
    // Postcondition: returns the level of the deepest object x in the tree
231 
    public int level( Object x ) {
246 
    public int level( Object x ) {
232 
        if( !this.contains(x) ) { return -1; }  //not found
 247 
        if( !this.contains(x) ) { return -1; }  //not found
233 
        if( this.root.equals(x) ) { return 0; } //found here
 248 
        if( this.root.equals(x) ) { return 0; } //found here
234 
        int ansLeft = left.level(x);
 249 
        int ansLeft = left.level(x);
235 
        int ansRight = right.level(x);
 250 
        int ansRight = right.level(x);
Line 237... Line 252...
237 
        int answer = Math.max(ansLeft,ansRight);
 252 
        int answer = Math.max(ansLeft,ansRight);
238 
        if( answer >= 0 ) { return answer + 1; }
 253 
        if( answer >= 0 ) { return answer + 1; }
239 
        return answer;
 254 
        return answer;
240 
    }
 255 
    }
241
256
- 
 
 257 
    // method to check if the current tree is disjoint from "that" tree
- 
 
 258 
    // disjoint: no element in both this tree and that tree
- 
 
 259 
    // Precondition:  none
- 
 
 260 
    // Postcondition: returns true if and only if no element from "that"
- 
 
 261 
    //                tree is in "this" tree
242 
    public boolean isDisjointFrom( BinaryTree that ) {
262 
    public boolean isDisjointFrom( BinaryTree that ) {
243 
        if( that == null ) { return true; }
 263 
        if( that == null ) { return true; }
244 
        if( this.contains(that.root) ) { return false; }
 264 
        if( this.contains(that.root) ) { return false; }
245 
 
 265 
 
246 
        return isDisjointFrom(that.left) && isDisjointFrom(that.right);
 266 
        return isDisjointFrom(that.left) && isDisjointFrom(that.right);
247 
    }
 267 
    }
248
268
- 
 
 269 
    // method to check if a tree is valid
- 
 
 270 
    // valid: all of it's subtrees are disjoint
- 
 
 271 
    // Precondition:  none
- 
 
 272 
    // Postcondition: returns true if the tree is valid, false otherwise
249 
    public boolean isValid() {
273 
    public boolean isValid() {
250 
        if( this.isLeaf() ) { return true; }
 274 
        if( this.isLeaf() ) { return true; }
251 
        boolean answer;
 275 
        boolean answer;
252
276
253 
        if( left != null ) { answer = left.isDisjointFrom(right); }
 277 
        if( left != null ) { answer = left.isDisjointFrom(right); }
254 
        else { answer = right.isDisjointFrom(left); }
 278 
        else { answer = right.isDisjointFrom(left); }
255 
 
 279 
 
256 
        return answer;
 280 
        return answer;
257 
    }
 281 
    }
258
282
- 
 
 283 
    // method to check if one tree is equal to another
- 
 
 284 
    // Precondition:  object should be a BinaryTree (this is checked anyway)
- 
 
 285 
    // Postcondition: return true only if both trees are equal
259 
    public boolean equals( Object object ) {
 286 
    public boolean equals( Object object ) {
260 
        //if we are not a BinaryTree, return false
 287 
        //if we are not a BinaryTree, return false
261 
        if( !(object instanceof BinaryTree) ) { return false; }
288 
        if( !(object instanceof BinaryTree) ) { return false; }
262 
        BinaryTree x = (BinaryTree)object; //typed instance of Object
 289 
        BinaryTree x = (BinaryTree)object; //typed instance of Object
263
290
Line 265... Line 292...
265 
        boolean ansLeft=false, ansRight=false;
 292 
        boolean ansLeft=false, ansRight=false;
266
293
267 
        //check for the root data equality
 294 
        //check for the root data equality
268 
        if( !this.root.equals(x.root) ) { return false; }
 295 
        if( !this.root.equals(x.root) ) { return false; }
269
296
270 
        //need this check to make sure that the recursive operations are ok
 - 
 
271 
        if( left != null && right != null ) {
 297 
        if( left != null ) { //check left
272 
            //check the left
 - 
 
273 
            if( left.equals(x.left) ) { ansLeft = true; }
 298 
            if( left.equals(x.left) ) { ansLeft = true; }
- 
 
 299 
        }
- 
 
 300 
 
274 
            //check the right
 301 
        if( right != null ) { //check right
275 
            if( right.equals(x.right) ) { ansRight = true; }
 302 
            if( right.equals(x.right) ) { ansRight = true; }
276 
        }
 303 
        }
277
304
278 
        //if both are null, we are still okay
 305 
        //if both are null, we are still okay
279 
        if( left == null && x.left == null ) { ansLeft = true; }
 306 
        if( left == null && x.left == null ) { ansLeft = true; }