Subversion Repositories programming

Rev

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

Rev 34 Rev 35
Line 194... Line 194...
194 
        if( this.isLeaf() ) { return true; }
 194 
        if( this.isLeaf() ) { return true; }
195 
        if( Math.abs(left.height() - right.height()) < 2 ) { return true; }
 195 
        if( Math.abs(left.height() - right.height()) < 2 ) { return true; }
196 
        if( left.isBalanced() && right.isBalanced() ) { return true; }
 196 
        if( left.isBalanced() && right.isBalanced() ) { return true; }
197 
        return false;
 197 
        return false;
198 
    }
 198 
    }
199 
    /*
 199
200 
    public int pathLength() {
200 
    public int pathLength() {
- 
 
 201 
        int answer=0;
- 
 
 202 
        Queue queue = new Queue();
- 
 
 203 
        queue.enqueue(this);
- 
 
 204 
 
- 
 
 205 
        while( !queue.isEmpty() ) {
- 
 
 206 
            BinaryTree temp = (BinaryTree)queue.dequeue();
- 
 
 207 
            answer += level(temp.root);
- 
 
 208 
            if( temp.left != null ) { queue.enqueue(temp.left); }
- 
 
 209 
            if( temp.right != null ) { queue.enqueue(temp.right); }
- 
 
 210 
        }
- 
 
 211 
 
- 
 
 212 
        return answer;
- 
 
 213 
    }
- 
 
 214
- 
 
 215 
    public BinaryTree reverse() {
- 
 
 216 
        //both left and right are null
- 
 
 217 
        if( this.isLeaf() ) { return new BinaryTree(root); }
- 
 
 218
- 
 
 219 
        //left must be null, right must not be null
- 
 
 220 
        if( this.left == null )
- 
 
 221 
            return new BinaryTree(root,right.reverse(),null);
- 
 
 222 
 
- 
 
 223 
        //right must be null, left must not be null
- 
 
 224 
        if( this.right == null )
- 
 
 225 
            return new BinaryTree(root,null,left.reverse());
- 
 
 226
- 
 
 227 
        //both sides are not null
- 
 
 228 
        return new BinaryTree(root,right.reverse(),left.reverse());
201 
    }
 229 
    }
202
230
203 
    public BinaryTree reverse() { }
 - 
 
204 
    */
 - 
 
205
- 
 
206 
    public int level( Object x ) {
231 
    public int level( Object x ) {
207 
        if( !this.contains(x) ) { return -1; }  //not found
 232 
        if( !this.contains(x) ) { return -1; }  //not found
208 
        if( this.root.equals(x) ) { return 0; } //found here
 233 
        if( this.root.equals(x) ) { return 0; } //found here
209 
        int ansLeft = left.level(x);
 234 
        int ansLeft = left.level(x);
210 
        int ansRight = right.level(x);
 235 
        int ansRight = right.level(x);
211
236
212 
        int answer = Math.max(ansLeft,ansRight);
 237 
        int answer = Math.max(ansLeft,ansRight);
213 
        if( answer >= 0 ) { return answer + 1; }
 238 
        if( answer >= 0 ) { return answer + 1; }
214 
        return answer;
 239 
        return answer;
215 
    }
 240 
    }
216 
    /*
 241
217 
    public boolean isDisjointFrom( BinaryTree that ) { }
 242 
    public boolean isDisjointFrom( BinaryTree that ) {
- 
 
 243 
        if( that == null ) { return true; }
- 
 
 244 
        if( this.contains(that.root) ) { return false; }
- 
 
 245 
 
- 
 
 246 
        return isDisjointFrom(that.left) && isDisjointFrom(that.right);
- 
 
 247 
    }
- 
 
 248
218 
    public boolean isValid() { }
 249 
    public boolean isValid() {
- 
 
 250 
        if( this.isLeaf() ) { return true; }
- 
 
 251 
        boolean answer;
- 
 
 252
- 
 
 253 
        if( left != null ) { answer = left.isDisjointFrom(right); }
- 
 
 254 
        else { answer = right.isDisjointFrom(left); }
- 
 
 255 
 
- 
 
 256 
        return answer;
219 
    */
 257 
    }
- 
 
 258
220 
    public boolean equals( Object object ) {
 259 
    public boolean equals( Object object ) {
221 
        //if we are not a BinaryTree, return false
 260 
        //if we are not a BinaryTree, return false
222 
        if( !(object instanceof BinaryTree) ) { return false; }
261 
        if( !(object instanceof BinaryTree) ) { return false; }
223 
        BinaryTree x = (BinaryTree)object; //typed instance of Object
 262 
        BinaryTree x = (BinaryTree)object; //typed instance of Object
224
263