當知道節點數量增加一倍時,可以跟蹤該級別。 例如,在0級中,只有1個節點;在1級中,有2個節點;在2級中,有4個節點;在3級中,有8個節點;在4級中,有16個節點;等
對於節點中的每一水平分組爲使用水平序遍歷Java中的陣列可以是這樣的碼:
private static Node[][] toArrayLevels(final Node node)
{
final Queue<Node> temporaryQueue = new LinkedList<Node>(); // Temporary queue is used for level-order traversal.
final ArrayList<Node[]> tree = new ArrayList<Node[]>(); // Levels containing their nodes.
ArrayList<Node> nodes = new ArrayList<Node>(); // Current level containing its nodes.
Node[][] treeArray = new Node[][]{};
Node[] nodesArray = new Node[]{};
Node current = node; // Level 0.
int level = 1; // Node's children are level 1.
temporaryQueue.add(current);
nodes.add(current);
tree.add(nodes.toArray(nodesArray));
nodes = new ArrayList<Node>(2);
while (!temporaryQueue.isEmpty())
{
// When the nodes completely fill the maximum spaces (2^level) allowed on the current level, start the next level.
if (nodes.size() >= Math.pow(2, level))
{
tree.add(nodes.toArray(nodesArray));
nodes = new ArrayList<Node>((int) Math.pow(2, level));
level += 1;
}
current = temporaryQueue.remove();
// Check current's children.
if (current != null)
{
final Node left = current.getLeft();
final Node right = current.getRight();
temporaryQueue.add(left);
nodes.add(left);
temporaryQueue.add(right);
nodes.add(right);
}
else
{
// Null nodes fill spaces used to maintain the structural alignment of the tree.
nodes.add(null);
nodes.add(null);
}
}
// Push remaining nodes.
if (nodes.size() > 0)
{
tree.add(nodes.toArray(nodesArray));
}
return (tree.toArray(treeArray));
}
它檢查當前級別節點的數量。當節點填滿當前級別時,它開始一個新的級別。
舉個例子,一個二叉樹可能是這樣的:
Level 0: 60
/ \
Level 1: 50 65
/ \ / \
Level 2: 49 55 -- 66
/ \ / \ / \ / \
Level 3: -- -- -- -- -- -- -- 71
這裏是例子的輸出:
System.out.println(Arrays.deepToString(binaryTree.toArrayLevels()));
[[{60}], [{50}, {65}], [{49}, {55}, null, {66}], [null, null, null, null, null, null, null, {71}], [null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null]]
[
[{60}], // Level 0.
[{50}, {65}], // Level 1.
[{49}, {55}, null, {66}], // Level 2.
[null, null, null, null, null, null, null, {71}], // Level 3.
[null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null] // Level 4.
]
下面是JavaScript版本:
function toArrayLevels(node)
{
var temporary = []; // Temporary is used for level-order traversal.
var tree = []; // Levels containing their nodes.
var nodes = []; // Current level containing its nodes.
var current = node; // Level 0.
var level = 1; // Node's children are level 1.
temporary.push(current);
tree.push([current]);
while (temporary.length > 0)
{
// When the nodes completely fill the maximum spaces (2^level) allowed on the current level, start the next level.
if (nodes.length >= Math.pow(2, level))
{
tree.push(nodes);
nodes = [];
level += 1;
}
current = temporary.shift();
// Check current's children.
if (current !== null)
{
var left = current.left;
var right = current.right;
temporary.push(left);
nodes.push(left);
temporary.push(right);
nodes.push(right);
}
else
{
// Null nodes fill spaces used to maintain the structural alignment of the tree.
nodes.push(null);
nodes.push(null);
}
}
// Push remaining nodes.
if (nodes.length > 0)
{
tree.push(nodes);
}
return tree;
}
在Java中'ALL_CAPS_VARIABLE_NAMES'不被認爲是慣用的。 –