2

これがノードを使用した初めてのコーディングであるため、これが正しく行われているかどうかはわかりません。しかし、誰かがそれを見て、私が何か間違っているかどうかを理解するのを手伝ってくれるなら、これまでの私のコードです。また、私の挿入/削除方法も苦労しています。教授はそのための疑似コードをくれましたが、この種のコードをこれまでやったことがないので、それを Java コードに解釈する方法を理解できないようです。主に、高さをチェックしてツリーのバランスが取れているかどうかを確認するifステートメントがあるため、これに高さをどのように実装しますか? ヒントやヘルプは大歓迎です。私はしばらくこれにこだわっています。ありがとう！

また、コンストラクターを正しく実行したとは思わず、それについて確信が持てません。挿入/削除のリターンは無視できます。コードの残りの部分が確実にコンパイルされるようにするためにそこに入れられただけです。

public class AvlNode{

    public static void main(String[]args){

    }
    //constructor
    public class AvlTreeNode{
        private int num;
        private AvlTreeNode left;
        private AvlTreeNode right;

        public AvlTreeNode left(){
            return this.left;
        }

        public AvlTreeNode right(){
            return this.right;
        }

        public int value(){
            return this.num;
        }
    }
    //method to find the number specified on the node
    public AvlTreeNode find(AvlTreeNode t, int x){
        if(t == null){
            return null;
        }
        if( t.value() == x){
            return t;
        }
        else if(x < t.value()){
            return find(t.left(), x);
        }
        else{
            return find(t.right(), x);
        }
    }
    //method to insert a new node and number to a tree
    public AvlTreeNode insert(AvlTreeNode t, int x){
        if(t == null){
            t = new AvlTreeNode(x, null, null);
            return t;
        }
        if(x < t.value()){
            t.left = insert(t.left(), x);
        }
        return t;
    }
    //method to remove a node and number from the tree
    public AvlTreeNode remove(AvlTreeNode t, int x){
        return t;
    }
    //Inorder traversal method, should print out numbers in ascending order if correct
    public void inOrder(AvlTreeNode t){
        if(t != null){
            inOrder(t.left());
            System.out.print(t.value() + " ");
            inOrder(t.right());
        }
    }
    //single rotation of nodes to balance tree, rotating leftwards
    public static AvlTreeNode singleRotateWithLeft( AvlTreeNode k1){
        AvlTreeNode k2 = k1.left;
        k1.left = k2.right;
        k2.right = k1;
        return k2;
    }
    //single rotation of nodes to balance tree, rotating rightwards
    public static AvlTreeNode singleRotateWithRight( AvlTreeNode k2){
        AvlTreeNode k1 = k2.right;
        k2.right = k1.left;
        k1.left = k2;
        return k1;
    }
    //double rotation of nodes towards the left
    public static AvlTreeNode doubleRotateWithLeft( AvlTreeNode k3){
        k3.left = doubleRotateWithRight(k3.left);
        return doubleRotateWithLeft(k3);
    }
    //double rotation of nodes towards the right
    public static AvlTreeNode doubleRotateWithRight( AvlTreeNode k2){
        k2.right = doubleRotateWithLeft(k2.right);
        return doubleRotateWithRight(k2);
    }
}
4

1 に答える 1

1

コンストラクターについて: 間違っているのは、コンストラクターの AvlTreeNode を記述するために使用する内部クラスを間違えていることだと思います。ほとんどの場合、明示的なコンストラクターを記述する必要はありません。デフォルト (空の) コンストラクターで十分だからです。

ツリーの構築は、空のツリーへのすべてのノードの挿入と見なすことができます。

高さに関しては、おそらくツリーの高さを各 AvlTreeNode のプロパティとして表示する必要があります (したがって、次に変数numが必要heightです)。次に、正しいローカル変換/回転が使用され、挿入されたノードとその子の高さが適切に増減されるように、挿入と削除を実装します。

編集: コードが 3 つの引数を持つコンストラクターを使用していることがわかります。このコード例のようなコンストラクターを使用できます。

//inner class for the node
public class AvlTreeNode{
    private int num;
    private int height;

    private AvlTreeNode left;
    private AvlTreeNode right;

    //this is the constructor!
    public AvlTreeNode(int value, AvlTreeNode left, AvlTreeNode right){
        this.num = value;
        this.left = left;
        this.right = right;
        this.height = 1;

        if (left != null && left.height() >= height){
            height = left.height() + 1;
        }
        if (right != null && right.height() >= height){
            height = right.height() + 1;
        }
    }

    public AvlTreeNode left(){
        return this.left;
    }

    public AvlTreeNode right(){
        return this.right;
    }

    public int value(){
        return this.num;
    }

    public int height(){
        return height;
    }
}
于 2013-10-20T20:07:58.497 に答える