Subversion Repositories programming

Rev

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

Rev 32 Rev 33
Line 111... Line 111...
111 
        //return the assembled string
 111 
        //return the assembled string
112 
        return answer;
 112 
        return answer;
113 
    }
 113 
    }
114
114
115 
    //misc methods ----------------------------------------------------------
 115 
    //misc methods ----------------------------------------------------------
- 
 
 116
- 
 
 117 
    // method to check if the current node is a leaf
- 
 
 118 
    // Precondition:  none
- 
 
 119 
    // Postcondition: returns true if the current node is a leaf, and false
- 
 
 120 
    //                in any other case
116 
    public boolean isLeaf() {
121 
    public boolean isLeaf() {
117 
        if( (left == null) && (right == null) ) { return true; }
 122 
        if( (left == null) && (right == null) ) { return true; }
118 
        return false;
 123 
        return false;
119 
    }
 124 
    }
120
125
- 
 
 126 
    // method to find the size of the tree
- 
 
 127 
    // Precondition:  none
- 
 
 128 
    // Postcondition: returns the size of the tree
121 
    public int size() {
129 
    public int size() {
122 
        int answer=1; // 1 for the node we are at
 130 
        int answer=1; // 1 for the node we are at
123 
        if( !(left == null) ) { answer += left.size(); }
 131 
        if( !(left == null) ) { answer += left.size(); }
124 
        if( !(right == null) ) { answer += right.size(); }
 132 
        if( !(right == null) ) { answer += right.size(); }
125 
 
 133 
 
126 
        return answer;
 134 
        return answer;
127 
    }
 135 
    }
128
136
- 
 
 137 
    // method to calculate the height of the tree
- 
 
 138 
    // Precondition:  none
- 
 
 139 
    // Postcondition: returns the height of the tree
129 
    public int height() {
 140 
    public int height() {
130 
        if( this.isLeaf() ) { return 0; }
 141 
        if( this.isLeaf() ) { return 0; }
131 
        int l=1,r=1;
 142 
        int l=1,r=1;
132 
        l += left.height();
 143 
        l += left.height();
133 
        r += right.height();
 144 
        r += right.height();
134 
 
 145 
 
135 
        return Math.max(l,r);
 146 
        return Math.max(l,r);
136 
    }
 147 
    }
137
148
- 
 
 149 
    // method to search the tree for an object
- 
 
 150 
    // Precondition:  object is non-null
- 
 
 151 
    // Postcondition: returns true if the tree contains the object,
- 
 
 152 
    //                and false if the tree doesn't contain the object
138 
    public boolean contains( Object object ) {
153 
    public boolean contains( Object object ) {
139 
        if( root.equals(object) ) { return true; }
 154 
        if( root.equals(object) ) { return true; }
140 
        if( this.isLeaf() ) { return false; }
 155 
        if( this.isLeaf() ) { return false; }
141 
        return left.contains(object) || right.contains(object);
 156 
        return left.contains(object) || right.contains(object);
142 
    }
 157 
    }
143
158
- 
 
 159 
    // method to find the number of leaves in the tree
- 
 
 160 
    // Precondition:  none
- 
 
 161 
    // Postcondition: returns the number of leaves in the tree
144 
    public int numLeaves() {
162 
    public int numLeaves() {
145 
        if( this.isLeaf() ) { return 1; }
 163 
        if( this.isLeaf() ) { return 1; }
146 
        return left.numLeaves() + right.numLeaves();
 164 
        return left.numLeaves() + right.numLeaves();
147 
    }
 165 
    }
148
166
- 
 
 167 
    // method to find the number of a certain object in the tree
- 
 
 168 
    // Precondition:  the object in non-null
- 
 
 169 
    // Postcondition: returns the number of the object that
- 
 
 170 
    //                are in the tree
149 
    public int count( Object x ) {
171 
    public int count( Object x ) {
150 
        int answer=0;
 172 
        int answer=0;
151 
        if( root.equals(x) ) { answer=1; }
 173 
        if( root.equals(x) ) { answer=1; }
152 
        if( !(left == null) ) { answer += left.count(x); }
 174 
        if( !(left == null) ) { answer += left.count(x); }
153 
        if( !(right == null) ) { answer += right.count(x); }
 175 
        if( !(right == null) ) { answer += right.count(x); }
154 
        return answer;
 176 
        return answer;
155 
    }
 177 
    }
156 
    /*
 178
- 
 
 179 
    // method to check if the tree is full
- 
 
 180 
    // Precondition:  none
- 
 
 181 
    // Postcondition: returns true if the tree is a full tree,
- 
 
 182 
    //                and false if the tree is not a full tree
157 
    public boolean isFull() { }
 183 
    public boolean isFull() {
- 
 
 184 
        if( this.isLeaf() ) { return true; }
- 
 
 185 
        if( !(left.height() == right.height()) ) { return false; }
- 
 
 186 
        if( left.isFull() == false || right.isFull() == false )
- 
 
 187 
            return false;
- 
 
 188 
        return true;
- 
 
 189 
    }
- 
 
 190
- 
 
 191 
    // method to check if the tree is balanced
- 
 
 192 
    // Precondition:  none
- 
 
 193 
    // Postcondition: returns true if the tree is balanced, false otherwise
158 
    public boolean isBalanced() { }
 194 
    public boolean isBalanced() {
- 
 
 195
- 
 
 196 
    }
- 
 
 197
159 
    public int pathLength() { }
 198 
    public int pathLength() { }
160 
    public BinaryTree reverse() { }
 199 
    public BinaryTree reverse() { }
161 
    public int level( Object x ) { }
 200 
    public int level( Object x ) { }
162 
    public boolean isDisjointFrom( BinaryTree that ) { }
 201 
    public boolean isDisjointFrom( BinaryTree that ) { }
163 
    public boolean isValid() { }
 202 
    public boolean isValid() { }