0

我有一个 BST AVL，用 Java 编写，我需要通过打印最后十个节点来证明它是平衡的。我的 hack-y 解决方案是，知道节点的数量，从有序遍历的最后 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) 的调用之间进行。我想如果你解决这个问题，你会没事的。

实际上，您实际上是在最后一个根节点上完成工作，所以我希望它能够打印出来。

于 2012-05-07T17:04:02.260 回答