0

JavaでBSTAVLを取得しました。これは、最後の10ノードを印刷することでバランスが取れていることを証明する必要があります。私のハックの解決策は、ノードの数を知って、順序どおりのトラバーサルの最後の10ノードから値を取得することでした。意図したとおりに機能していません。レコードは姓キーで保存され（重複レコードは保持されません）、各ノードのサイズのプリントアウトは0になります。私のプリントアウトには、ほとんどの場合「Z」の名前が付いています...予想どおり、最初のレコード（26000）のプリントアウトも含まれています。ツリーの障害ではなく、プリントアウトをどのように考案したかという問題だと思います（期待しています）。最後の10ノードを印刷するためのより洗練された方法はありますか？それは私が今持っているエラーを持っていないでしょう、または私の木の回転に欠陥がある可能性がありますか？

InOrderトラバースと出力: (get関数を介してアクセスされる出力）

public void inOrder(Node x)
{
    if (x == null)
        return; //stops recursion when there is no Node
    inOrder(x.left); //always traverse left first
    inOrder(x.right); //traverse right

    inOrderTraversalOutput += Integer.toString((size(x.left))  + 
(size(x.right))) + "\n"; 

    bstNodes++;
    //total nodes - 17151
    if (bstNodes > 17145)
        lastnodes += x.val.toString() + "Node left size: " + 
size(x.left) + "\n" + "Node right size: " + size(x.right) + 
"\n" + "----------------------------------------------------\n";

}
//modified to print total number of nodes
public String getTraversal()
{
    inOrderTraversalOutput += Integer.toString(bstNodes) + "\n";
    return inOrderTraversalOutput;
}

putメソッド:(ルートノード、キー、および値を渡すメソッドを介して呼び出されます）

private Node put(Node x, Key key, Value val)
{
    if (x == null)
    {
        return new Node(key, val, 0);
    }

    int cmp = key.compareTo(x.key);

    if (cmp < 0)
    {
        x.left = put(x.left, key, val);

        //AVL Balance
        if ((size(x.left) - size(x.right)) >= 2)
            {
                if (x.key.compareTo(x.left.key) < 0)
                {
                    x = rotateWithLeftsapling(x);
                } else
                {
                    x = doubleWithLeftsapling(x);
                }
        }

    } else if (cmp > 0)
    {
        x.right = put(x.right, key, val);

        //AVL Balance
        if ((size(x.right) - size(x.left)) >= 2)
        {
            if (x.key.compareTo(x.right.key) > 0)
            {
                x = rotateWithRightsapling(x);
            } else
            {
                x = doubleWithRightsapling(x);
            }
        }
    } else
    {
        x.val = val;
    }

    x.N = size(x.left) + size(x.right);
    return x;
}
4

1 に答える 1

1

注文後のトラバーサルを行っているようです。順番に実行するには、inorder(left) と inorder(right) の呼び出しの間にすべての「作業」が発生する必要があります。これを直せばOKだと思います。

そのままで、実際にはルートノードの作業を最後に行っているので、出力されると思います。

于 2012-05-07T17:04:02.260 に答える