I implemented a binary search tree and would like to make a subclass that is self-balancing (AVL). I was getting strange results, and so I decided, to isolate the problem, I made an exact copy of the parent class MyTreeMap, and called it dumbchild extends MyTreeMap. Again, it's exactly the same and works correctly. Then I delete one of the methods in dumbchild expecting it to inherit it from MyTreeMap, and that changed the behavior of the class.
我实现了一个二叉搜索树，并希望创建一个自平衡（AVL）的子类。我得到了奇怪的结果，所以我决定，为了隔离问题，我制作了父类MyTreeMap的精确副本，并称之为dumbchild扩展MyTreeMap。同样，它完全相同并且正常工作。然后我删除了dumbchild中的一个方法，期望它从MyTreeMap继承它，并且改变了类的行为。
This seems like a very straightforward application of inheritance, but it's not working. I thought maybe it could have to do with the data structure being recursive.
这似乎是一个非常简单的继承应用程序，但它不起作用。我想也许这可能与数据结构递归有关。
EDIT: it was requested that I include all of the code
编辑：要求我包含所有代码
import java.util.Iterator;
public class MyTreeMap<K extends Comparable<? super K>, V> implements Iterable<K>{
public K key;
public V value;
public int height = 0;
public MyTreeMap<K, V> left, right;
protected void setHeight(){ // if key is not null, left and right should not be null
if(key == null){
height = 0;
}
else{
height = 1 + Math.max(left.height, right.height);
}
System.out.println("set of " + key + " height to " + height);
}
public V put(K key, V value){
if(key == null){
throw new NullPointerException();
}
V ret;
if(this.key == null){ // empty leaf, place found
this.key = key;
this.value = value;
left = new MyTreeMap<>();
right = new MyTreeMap<>();
ret = null;
}
else{
int compare = key.compareTo(this.key);
if(compare == 0){ //replace
this.value = value;
ret = value;
}
else if(compare < 0){ // put to left
ret = left.put(key, value);
}
else{
ret = right.put(key, value);
}
}
setHeight();
return ret;
}
public Iterator<K> iterator(){
return new Iterator<K>(){
Iterator<K> l, r;
K current = MyTreeMap.this.key;
{
if(left != null) l = left.iterator();
if(right != null) r = right.iterator();
}
public boolean hasNext(){
return current != null;
}
public K next(){
K ret = current;
if(l!= null && l.hasNext()){
current = l.next();
}
else if(r!= null && r.hasNext()){
current = r.next();
}
else{
current = null;
}
return ret;
}
};
}
public static void main(String[] args){
MyTreeMap<Integer, String> t = new MyTreeMap<>();
for(int i = 0; i<64; i++){
t.put(i, null);
}
Iterator<Integer> it = t.iterator();
while(it.hasNext()){
System.out.println(it.next());
}
System.out.println("height: " + t.height);
}
}
and here is dumbchild's declaration:
这是dumbchild的声明：
public class dumbchild<K extends Comparable<? super K>, V> extends MyTreeMap<K, V> implements Iterable<K>{
dumbchild does not have setHeight, but it is exactly the same in every other way (copied and pasted, replace "MyTreeMap" text with "dumbchild"). They even have the same main method for testing.
dumbchild没有setHeight，但它在其他方面完全相同（复制和粘贴，用“dumbchild”替换“MyTreeMap”文本）。他们甚至拥有相同的主要测试方法。
The test is to add a bunch of stuff, and then iterator through it in preorder, printing out the values, and then print the height.
测试是添加一堆东西，然后按顺序通过它进行迭代，打印出值，然后打印高度。
MyHashMap prints the correct height, dumbchild prints 0. If I remove other methods from dumbchild, other things go wrong too.
MyHashMap打印正确的高度，dumbchild打印0.如果我从dumbchild中删除其他方法，其他事情也会出错。
What am I missing?
我错过了什么？
Thanks
谢谢
1 个解决方案
#1
1
I tested with the following code, and dumbchild correctly prints the height as 64. Was there any problem originally? All I did is to add definition of remove() in the code that returning an anonymous instance of Iterator<T>.
我测试了下面的代码，并且dumbchild正确地将高度打印为64.原来有什么问题吗？我所做的就是在返回Iterator
import java.util.Iterator;
class dumbchild<K extends Comparable<? super K>, V> extends MyTreeMap<K, V> implements Iterable<K>{
}
public class MyTreeMap<K extends Comparable<? super K>, V> implements Iterable<K>{
public K key;
public V value;
public int height = 0;
public MyTreeMap<K, V> left, right;
protected void setHeight(){ // if key is not null, left and right should not be null
if(key == null){
height = 0;
}
else{
height = 1 + Math.max(left.height, right.height);
}
System.out.println("set of " + key + " height to " + height);
}
public V put(K key, V value){
if(key == null){
throw new NullPointerException();
}
V ret;
if(this.key == null){ // empty leaf, place found
this.key = key;
this.value = value;
left = new MyTreeMap<>();
right = new MyTreeMap<>();
ret = null;
}
else{
int compare = key.compareTo(this.key);
if(compare == 0){ //replace
this.value = value;
ret = value;
}
else if(compare < 0){ // put to left
ret = left.put(key, value);
}
else{
ret = right.put(key, value);
}
}
setHeight();
return ret;
}
public Iterator<K> iterator(){
return new Iterator<K>() {
Iterator<K> l, r;
K current = MyTreeMap.this.key;
{
if(left != null) l = left.iterator();
if(right != null) r = right.iterator();
}
public boolean hasNext(){
return current != null;
}
public K next(){
K ret = current;
if(l!= null && l.hasNext()){
current = l.next();
}
else if(r!= null && r.hasNext()){
current = r.next();
}
else{
current = null;
}
return ret;
}
@Override
public void remove() {
// ?
}
};
}
public static void main(String[] args){
/*
MyTreeMap<Integer, String> t = new MyTreeMap<>();
for(int i = 0; i<64; i++){
t.put(i, null);
}
Iterator<Integer> it = t.iterator();
while(it.hasNext()){
System.out.println(it.next());
}
System.out.println("height: " + t.height);
*/
dumbchild<Integer, String> c = new dumbchild<>();
for(int i = 0; i<64; i++){
c.put(i, null);
}
Iterator<Integer> ct = c.iterator();
while(ct.hasNext()){
System.out.println(ct.next());
}
System.out.println("height: " + c.height);
}
}
#1
1
I tested with the following code, and dumbchild correctly prints the height as 64. Was there any problem originally? All I did is to add definition of remove() in the code that returning an anonymous instance of Iterator<T>.
我测试了下面的代码，并且dumbchild正确地将高度打印为64.原来有什么问题吗？我所做的就是在返回Iterator
import java.util.Iterator;
class dumbchild<K extends Comparable<? super K>, V> extends MyTreeMap<K, V> implements Iterable<K>{
}
public class MyTreeMap<K extends Comparable<? super K>, V> implements Iterable<K>{
public K key;
public V value;
public int height = 0;
public MyTreeMap<K, V> left, right;
protected void setHeight(){ // if key is not null, left and right should not be null
if(key == null){
height = 0;
}
else{
height = 1 + Math.max(left.height, right.height);
}
System.out.println("set of " + key + " height to " + height);
}
public V put(K key, V value){
if(key == null){
throw new NullPointerException();
}
V ret;
if(this.key == null){ // empty leaf, place found
this.key = key;
this.value = value;
left = new MyTreeMap<>();
right = new MyTreeMap<>();
ret = null;
}
else{
int compare = key.compareTo(this.key);
if(compare == 0){ //replace
this.value = value;
ret = value;
}
else if(compare < 0){ // put to left
ret = left.put(key, value);
}
else{
ret = right.put(key, value);
}
}
setHeight();
return ret;
}
public Iterator<K> iterator(){
return new Iterator<K>() {
Iterator<K> l, r;
K current = MyTreeMap.this.key;
{
if(left != null) l = left.iterator();
if(right != null) r = right.iterator();
}
public boolean hasNext(){
return current != null;
}
public K next(){
K ret = current;
if(l!= null && l.hasNext()){
current = l.next();
}
else if(r!= null && r.hasNext()){
current = r.next();
}
else{
current = null;
}
return ret;
}
@Override
public void remove() {
// ?
}
};
}
public static void main(String[] args){
/*
MyTreeMap<Integer, String> t = new MyTreeMap<>();
for(int i = 0; i<64; i++){
t.put(i, null);
}
Iterator<Integer> it = t.iterator();
while(it.hasNext()){
System.out.println(it.next());
}
System.out.println("height: " + t.height);
*/
dumbchild<Integer, String> c = new dumbchild<>();
for(int i = 0; i<64; i++){
c.put(i, null);
}
Iterator<Integer> ct = c.iterator();
while(ct.hasNext()){
System.out.println(ct.next());
}
System.out.println("height: " + c.height);
}
}