0
我有一個BST AVL,在Java中,我需要通過打印最後十個節點來證明它是平衡的。我的hack-y解決方案是知道節點的數量,從有序遍歷的最後10個節點獲取值。它沒有按照預期工作。記錄與姓氏鍵一起存儲(不保存重複的記錄),每個節點尺寸的打印結果爲0。 我的打印輸出大多是'Z'的名字......正如所料,然後它還包含打印出來的第一條記錄(26000)。我猜(希望)這是我設計打印輸出的問題,而不是樹中的故障?有沒有一種更優雅的方式來打印最後10個節點,不會有我現在的錯誤,還是可能在我的樹輪中存在缺陷?AVL平衡樹 - 打印最後10個節點
序遍歷和輸出:(輸出通過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;
}
(通過傳遞根節點,鍵和值的方法調用)