0

このクラスが機能していない理由を理解するのに苦労しています。これは、データ構造に関するコースの割り当ての一部でした (編集: 割り当ての締め切りが過ぎました。それを理解したいだけです...)。このノードは BST に基づいて構築された AVL ツリーの一部であり、私がそれを実装するために選択した方法は、Node クラス内にメソッドを作成して Balance 係数と高さを見つけることです。

クラスは次のように構成されています。

public class Node<T extends Comparable<? super T>> {

public T data;
public Node left;
public Node right;

public Node(T IN) {
    data = IN;
}

public Node(T IN, Node L, Node R) {
    this(IN);
    left = L;
    right = R;
}

@Override
public String toString() {
    return data.toString();
}

@Override
public Node clone() {
    return new Node(this.data) ;
}

public int getHeight() {
    return getHeight(this) ;
}

public int getBF() {

        //Calculate BF
        int balanceFactor = 0;
        if (right != null && left != null)
            balanceFactor = getHeight(right) - getHeight(left);
        else if (left != null) {
            balanceFactor = 0 - getHeight(left) ;
        }
        else if (right != null) {
            balanceFactor = getHeight(right) ;
        }
        else
            balanceFactor = 0 ;
        return balanceFactor ;
}

private int getHeight(Node p) {
    if (p.left == null && p.right == null ) {
        return 0 ;
    }
    else if (p.left != null && p.right != null) {
        return 1 + max(p.left.getHeight(), p.right.getHeight());
    }
    else if (p.left != null) {
        return 1 + p.left.getHeight() ;
    }
    else if (p.right != null) {
        return 1 + p.right.getHeight() ;
    }
    else {
        return 0;
    }
}

private int max(int x, int y) {
    if (x >= y) {
        return x;
    } else {
        return y;
    }
}

}

メソッドを呼び出す関数は次のとおりです。

@Override
public boolean insert(T el) {
    boolean test = super.insert(el) ;
    if (test) {
        return checkBalance(root) ;
    }
    else
        return false ;
}

私が受け取る例外は、次の繰り返しです。

Exception in thread "main" java.lang.StackOverflowError
at Node.getHeight(Node.java:54)
at Node.getHeight(Node.java:33)
at Node.getHeight(Node.java:58)
4

2 に答える 2

4

あなたの木が変形しているか、非常に大きいことをお勧めします。コードに問題はないようです。

ツリーが変形しNodeて同じツリーに 2 回挿入されると、このコードは壊れます。

追加- 必要以上のスタックを消費しています - etc に置き換えるp.left.getHeight()と、getHeight(p.left)再帰ごとに 1 つのスタック プッシュを回避できます。あなたの問題が単に大きな木である場合、これはあなたをこすり落とすかもしれませんが、これは問題を先延ばしにするだけです.

于 2013-04-02T10:29:23.503 に答える
2

両方の getHeight メソッドを見ると、ツリーではなく循環グラフのように見えます。ルートのみで構成されるツリーでテストを開始し、無限再帰が観察されるまでノードを追加する必要があります。ツリーを再調整する関数にエラーがある可能性があります。

編集:そして、属性(少なくとも左と右)を非公開にする必要があります。

于 2013-04-02T10:28:52.720 に答える