AVL平衡树-打印最后10个节点

2019年4月5日 34点热度 0条评论

我有一个用Java编写的BST AVL,我需要通过打印最后十个节点来证明它是平衡的。我的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;
}

解决方案如下:

看起来您正在执行订单遍历。为了做一个命令,所有的“工作”都应该发生在对inorder(left)和inorder(right)的调用之间。我认为,如果您解决此问题,那么您会好的。

实际上,您实际上是在最后处理根节点,所以我希望它可以打印出来。