当您知道每个级别的节点数加倍时,可以跟踪级别。例如,在级别 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;
}