如何在水平顺序或宽度优先顺序遍历二叉树时跟踪水平?
二叉树中的节点只有左引用和右引用。
我希望能够区分每一行节点。
这是我的水平序遍历方法:
private static Queue<Node> traverseLevelOrder(final Node node)
{
final Queue<Node> temporaryQueue = new LinkedList<Node>(); // Temporary queue is used for traversal.
final Queue<Node> permanentQueue = new LinkedList<Node>(); // Permanent queue is used for node storage.
// Add the root node, as current, to the queue.
Node current = node;
temporaryQueue.add(current);
permanentQueue.add(current);
while (!temporaryQueue.isEmpty())
{
current = temporaryQueue.remove();
System.out.println(String.valueOf(current));
// Check current's children.
if (current != null)
{
final Node left = current.getLeft();
final Node right = current.getRight();
current = left;
if (current != null)
{
temporaryQueue.add(current);
permanentQueue.add(current);
}
current = right;
if (current != null)
{
temporaryQueue.add(current);
permanentQueue.add(current);
}
}
}
return permanentQueue;
}
public void bfs(Node root) {
Queue<Node> q = new LinkedList<Node>();
Node dummy = new Node(null);
q.add(root);
q.add(dummy);
while(!q.isEmpty()) {
Node curr = q.poll();
if(curr != null) {
System.out.print(curr.data + " ");
if(curr.left != null)
q.insert(curr.left);
if(curr.right !== null)
q.insert(curr.right);
} else {
System.out.println();
if(!q.isEmpty())
q.insert(dummy);
}
}
}
此代码不显示中间的null节点
当你知道每个关卡的节点数量翻倍时，就可以跟踪关卡。例如，在级别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;
}
这是我编写的代码，用于查找没有递归的二叉树的左视图。这里我跟踪的是将null作为树本身节点的节点数。在特定级别中null节点的null节点的数量将在下一级别中增加一倍。currNulls和nextNulls跟踪当前和下一层的null
void leftView(Node root){
if(root==null) return;
boolean newL=true;
int level=0,count=0,nextNulls=0,currNulls=0;
Queue<Node> q=new LinkedList<>();
q.add(root);
while(!q.isEmpty()){
Node node=q.remove();
if(newL){
System.out.print(node.data+" ");
newL=false;
}
count++;
if(node.left!=null){
q.add(node.left);
}
else{
nextNulls++;
}
if(node.right!=null){
q.add(node.right);
}
else{
nextNulls++;
}
if(1<<level == count+currNulls){
level++;
newL=true;
count=0;
// System.out.println("Curr -"+currNulls+"tNext - "+nextNulls);
currNulls=nextNulls;
nextNulls=2*nextNulls;
}
}
}
这是我的javascript版本的关卡顺序遍历，它应该指向正确的方向
我在写这篇文章之前看过这个视频
var discovered = [];
var getLevels = function(node) {
if (node == null) { return []}
discovered.push(node)
var levels = levelOrderTraverse(discovered,[])
return levels
}
function levelOrderTraverse(discovered,elms) {
var level = []
for (var i = 0; i < discovered.length; i++) {
level.push(discovered[i].val)
}
elms.push(level);
var newlyDiscovered = [];
for (var i = 0; i < discovered.length; i++) {
if (discovered[i].left != null) {
newlyDiscovered.push(discovered[i].left)
}
if (discovered[i].right != null) {
newlyDiscovered.push(discovered[i].right)
}
}
if (newlyDiscovered.length > 0) {
levelOrderTraverse(newlyDiscovered,elms)
}
return elms
}
也可以在我的github上找到test