Subversion Repositories programming

Rev

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

Rev 36 Rev 37
Line 141... Line 141...
141 
    // method to calculate the height of the tree
 141 
    // method to calculate the height of the tree
142 
    // Precondition:  none
 142 
    // Precondition:  none
143 
    // Postcondition: returns the height of the tree
 143 
    // Postcondition: returns the height of the tree
144 
    public int height() {
 144 
    public int height() {
145 
        if( this.isLeaf() ) { return 0; }
 145 
        if( this.isLeaf() ) { return 0; }
146 
        int l=1,r=1;
 146 
        int l=0,r=0;
- 
 
 147
147 
        l += left.height();
 148 
        if( left != null ) { l = 1 + left.height(); }
148 
        r += right.height();
 149 
        if( right != null ) { r = 1 + right.height(); }
149 
 
 150
150 
        return Math.max(l,r);
 151 
        return Math.max(l,r);
151 
    }
 152 
    }
152
153
153 
    // method to search the tree for an object
 154 
    // method to search the tree for an object
154 
    // Precondition:  object is non-null
 155 
    // Precondition:  object is non-null
155 
    // Postcondition: returns true if the tree contains the object,
 156 
    // Postcondition: returns true if the tree contains the object,
156 
    //                and false if the tree doesn't contain the object
 157 
    //                and false if the tree doesn't contain the object
157 
    public boolean contains( Object object ) {
158 
    public boolean contains( Object object ) {
158 
        if( root.equals(object) ) { return true; }
 159 
        if( root.equals(object) ) { return true; }
159 
        if( this.isLeaf() ) { return false; }
 160 
        //if( this.isLeaf() ) { return false; }
- 
 
 161 
 
- 
 
 162 
        boolean l=false, r=false;
- 
 
 163 
        if( left != null ) { l=left.contains(object); }
160 
        return left.contains(object) || right.contains(object);
 164 
        if( right != null ) { r=right.contains(object); }
- 
 
 165
- 
 
 166 
        return l || r;
161 
    }
 167 
    }
162
168
163 
    // method to find the number of leaves in the tree
 169 
    // method to find the number of leaves in the tree
164 
    // Precondition:  none
 170 
    // Precondition:  none
165 
    // Postcondition: returns the number of leaves in the tree
 171 
    // Postcondition: returns the number of leaves in the tree
166 
    public int numLeaves() {
172 
    public int numLeaves() {
167 
        if( this.isLeaf() ) { return 1; }
 173 
        if( this.isLeaf() ) { return 1; }
- 
 
 174 
 
- 
 
 175 
        int l=0, r=0;
- 
 
 176 
 
- 
 
 177 
        if( left != null ) { l = left.numLeaves(); }
168 
        return left.numLeaves() + right.numLeaves();
 178 
        if( right != null ) { r = right.numLeaves(); }
- 
 
 179
- 
 
 180 
        return l + r;
169 
    }
 181 
    }
170
182
171 
    // method to find the number of a certain object in the tree
 183 
    // method to find the number of a certain object in the tree
172 
    // Precondition:  the object in non-null
 184 
    // Precondition:  the object in non-null
173 
    // Postcondition: returns the number of the object that
 185 
    // Postcondition: returns the number of the object that
Line 192... Line 204...
192 
    }
 204 
    }
193
205
194 
    // method to check if the tree is balanced
 206 
    // method to check if the tree is balanced
195 
    // Precondition:  none
 207 
    // Precondition:  none
196 
    // Postcondition: returns true if the tree is balanced, false otherwise
 208 
    // Postcondition: returns true if the tree is balanced, false otherwise
197 
    public boolean isBalanced() {
209 
    public boolean isBalanced() {
198 
        if( this.isLeaf() ) { return true; }
 210 
        if( this.isLeaf() ) { return true; }
- 
 
 211
- 
 
 212 
        //get left and right heights as applicable
- 
 
 213 
        int l=0, r=0;
- 
 
 214 
        if( left != null ) { l = left.height(); }
199 
        if( Math.abs(left.height() - right.height()) < 2 ) { return true; }
 215 
        if( right != null ) { r = right.height(); }
- 
 
 216
- 
 
 217 
        //check for the criteria of balance. If we are balanced, then
- 
 
 218 
        //check our subtrees for balance recursively
- 
 
 219 
        if( Math.abs( l-r ) < 2 ) {
- 
 
 220 
            if( left != null && right != null ) //check both
200 
        if( left.isBalanced() && right.isBalanced() ) { return true; }
 221 
                return left.isBalanced() && right.isBalanced();
- 
 
 222 
            if( left != null ) //right is null (check left)
201 
        return false;
 223 
                return left.isBalanced();
- 
 
 224 
            //left is null, right is not null
- 
 
 225 
            return right.isBalanced(); //check right
- 
 
 226 
        }
- 
 
 227 
        return false; //the criteria of balance was not met
202 
    }
 228 
    }
203
229
204 
    // method to get the total path length of the current tree
 230 
    // method to get the total path length of the current tree
205 
    // Precondition:  none
 231 
    // Precondition:  none
206 
    // Postcondition: returns the sum of all the root to node paths in
 232 
    // Postcondition: returns the sum of all the root to node paths in
Line 244... Line 270...
244 
    // Precondition:  x is not null
 270 
    // Precondition:  x is not null
245 
    // Postcondition: returns the level of the deepest object x in the tree
 271 
    // Postcondition: returns the level of the deepest object x in the tree
246 
    public int level( Object x ) {
272 
    public int level( Object x ) {
247 
        if( !this.contains(x) ) { return -1; }  //not found
 273 
        if( !this.contains(x) ) { return -1; }  //not found
248 
        if( this.root.equals(x) ) { return 0; } //found here
 274 
        if( this.root.equals(x) ) { return 0; } //found here
249 
        int ansLeft = left.level(x);
 275 
        int ansLeft=0, ansRight=0;
- 
 
 276 
        if( left != null ) { ansLeft = left.level(x); }
250 
        int ansRight = right.level(x);
 277 
        if( right != null ) { ansRight = right.level(x); }
251
278
252 
        int answer = Math.max(ansLeft,ansRight);
 279 
        int answer = Math.max(ansLeft,ansRight);
253 
        if( answer >= 0 ) { return answer + 1; }
 280 
        if( answer >= 0 ) { return answer + 1; }
254 
        return answer;
 281 
        return answer;
255 
    }
 282 
    }
Line 342... Line 369...
342 
        System.out.print( tree.root + " " );
 369 
        System.out.print( tree.root + " " );
343 
        if( tree.right != null ) { inOrderPrint(tree.right); }
 370 
        if( tree.right != null ) { inOrderPrint(tree.right); }
344 
    }
 371 
    }
345 
}
 372 
}
346 
 
 373 
 
347 
/*
 - 
 
348 
      BufferedReader kb = new BufferedReader(
 - 
 
349 
                              new InputStreamReader(System.in));
 - 
 
350 
 
 - 
 
351 
 
 - 
 
352 
      BufferedReader br = new BufferedReader(
 - 
 
353 
                              new InputStreamReader(
 - 
 
354 
                                  new FileInputStream(filename)));
 - 
 
355 
 
 - 
 
356 
      PrintStream ps = new PrintStream(
 - 
 
357 
                           new FileOutputStream(
 - 
 
358 
                               new File(filename)));
 - 
 
359 
 
 - 
 
360 
*/
 - 
 
361 
 
 -