2

如何在以级别顺序或广度优先顺序遍历二叉树时跟踪级别？

二叉树中的节点只有左右引用。

我希望能够区分每一行节点。

这是我的级别顺序遍历方法：

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;
}
4

4 回答 4

3 
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节点。

于 2011-12-05T14:51:18.903 回答
2

当您知道每个级别的节点数加倍时，可以跟踪级别。例如，在级别 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;
}
于 2012-03-07T19:29:45.057 回答
1

这是我编写的代码，用于在没有递归的情况下查找二叉树的左视图。在这里，我正在跟踪将 null 视为树本身中的节点的节点数。特定级别中空节点的空节点数量将在下一级增加一倍。currNulls和nextNulls跟踪当前和下一个级别的空值

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;
           }
        }
    }
于 2020-06-04T10:15:08.890 回答
0

这是我的级别顺序遍历的 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上通过测试找到

于 2018-10-19T20:29:00.507 回答