Java 以特定格式使用 Level-Order 打印二叉树

Java Printing a Binary Tree using Level-Order in a Specific Format

提问by JavaFail

Okay, I have read through all the other related questions and cannot find one that helps with java. I get the general idea from deciphering what i can in other languages; but i am yet to figure it out.

好的，我已经通读了所有其他相关问题，但找不到对 java 有帮助的问题。我从破译其他语言的内容中得到了大致的想法；但我还没有弄清楚。

Problem: I would like to level sort (which i have working using recursion) and print it out in the general shape of a tree.

问题：我想对排序（我使用递归进行排序）并以树的一般形状打印出来。

So say i have this:

所以说我有这个：

    1 
   / \
  2   3
 /   / \
4   5   6

My code prints out the level order like this:

我的代码打印出这样的级别顺序：

1 2 3 4 5 6

I want to print it out like this:

我想像这样打印出来：

1
2 3
4 5 6

Now before you give me a moral speech about doing my work... I have already finished my AP Comp Sci project and got curious about this when my teacher mentioned the Breadth First Search thing.

现在，在你给我做关于做我的工作的道德演讲之前......我已经完成了我的 AP Comp Sci 项目，当我的老师提到广度优先搜索这件事时，我对此感到好奇。

I don't know if it will help, but here is my code so far:

我不知道它是否会有所帮助，但这是我目前的代码：

/**
  * Calls the levelOrder helper method and prints out in levelOrder.
  */
 public void levelOrder()
 {
  q = new QueueList();
  treeHeight = height();
  levelOrder(myRoot, q, myLevel);
 }

 /**
  * Helper method that uses recursion to print out the tree in 
  * levelOrder
  */
 private void levelOrder(TreeNode root, QueueList q, int curLev)
 {
  System.out.print(curLev);
  if(root == null)
  {
   return;
  }

  if(q.isEmpty())
  {
   System.out.println(root.getValue());
  }
  else
  {
   System.out.print((String)q.dequeue()+", ");
  }

  if(root.getLeft() != null)
  {
   q.enqueue(root.getLeft().getValue());
   System.out.println();
  }
  if(root.getRight() != null)
  {
   q.enqueue(root.getRight().getValue());
   System.out.println();
   curLev++;
  }

  levelOrder(root.getLeft(),q, curLev);
  levelOrder(root.getRight(),q, curLev);
 }

From what i can figure out, i will need to use the total height of the tree, and use a level counter... Only problem is my level counter keeps counting when my levelOrder uses recursion to go back through the tree.

据我所知，我需要使用树的总高度，并使用级别计数器......唯一的问题是我的级别计数器在我的 levelOrder 使用递归返回树时一直在计数。

Sorry if this is to much, but some tips would be nice. :)

对不起，如果这太多了，但一些提示会很好。:)

回答by Anon.

Here is how I would do it:

这是我将如何做到的：

levelOrder(List<TreeNode> n) {
    List<TreeNode> next = new List<TreeNode>();
    foreach(TreeNode t : n) {
        print(t);
        next.Add(t.left);
        next.Add(t.right);
    }
    println();
    levelOrder(next);
}

(Was originally going to be real code - got bored partway through, so it's psueodocodey)

（最初是真正的代码 - 中途感到无聊，所以它是伪代码）

回答by Rob

The answer is close....the only issue I could see with it is that if a tree doesn't have a node in a particular position, you would set that pointer to null. What happens when you try to put a null pointer into the list?

答案很接近......我能看到的唯一问题是，如果一棵树在特定位置没有节点，您可以将该指针设置为空。当您尝试将空指针放入列表时会发生什么？

Here is something I did for a recent assignment. It works flawlessly. You can use it starting from any root.

这是我为最近的任务所做的事情。它完美无缺。您可以从任何根开始使用它。

  //Prints the tree in level order
  public void printTree(){
    printTree(root);
  }

 public void printTree(TreeNode tmpRoot){

    //If the first node isn't null....continue on
    if(tmpRoot != null){

        Queue<TreeNode> currentLevel = new LinkedList<TreeNode>(); //Queue that holds the nodes on the current level
        Queue<TreeNode> nextLevel = new LinkedList<TreeNode>();     //Queue the stores the nodes for the next level

        int treeHeight = height(tmpRoot);     //Stores the height of the current tree
        int levelTotal = 0;  //keeps track of the total levels printed so we don't  pass the height and print a billion "null"s

        //put the root on the currnt level's queue
        currentLevel.add(tmpRoot);

        //while there is still another level to print and we haven't gone past the tree's height
        while(!currentLevel.isEmpty()&& (levelTotal< treeHeight)){

            //Print the next node on the level, add its childen to the next level's queue, and dequeue the node...do this until the current level has been printed
            while(!currentLevel.isEmpty()){

                //Print the current value
                System.out.print(currentLevel.peek().getValue()+" ");

                //If there is a left pointer, put the node on the nextLevel's stack. If there is no ponter, add a node with a null value to the next level's stack
                tmpRoot = currentLevel.peek().getLeft();
                if(tmpRoot != null)
                    nextLevel.add(tmpRoot);
                else
                    nextLevel.add(new TreeNode(null));

                //If there is a right pointer, put the node on the nextLevel's stack. If there is no ponter, add a node with a null value to the next level's stack
                tmpRoot = currentLevel.remove().getRight();
                if(tmpRoot != null)
                    nextLevel.add(tmpRoot);
                else
                    nextLevel.add(new TreeNode(null));

            }//end while(!currentLevel.isEmpty())

            //populate the currentLevel queue with items from the next level
            while(!nextLevel.isEmpty()){
                currentLevel.add(nextLevel.remove());
            }

            //Print a blank line to show height
            System.out.println("");

            //flag that we are working on the next level
            levelTotal++;

        }//end while(!currentLevel.isEmpty())

    }//end if(tmpRoot != null)

}//end method printTree

public int height(){
    return height(getRoot());
}

public int height(TreeNode tmpRoot){

    if (tmpRoot == null)
        return 0;
    int leftHeight = height(tmpRoot.getLeft());
    int rightHeight = height(tmpRoot.getRight());

    if(leftHeight >= rightHeight)
        return leftHeight + 1;
    else
        return rightHeight + 1;
 }

回答by Salman Paracha

I really like the simplicity of Anon's code; its elegant. But, sometimeselegant code doesn't always translate into code that is intuitively easy to grasp. So, here's my attempt to show a similar approach that requires Log(n) more space, but should read more naturally to those who are most familiar with depth first search (going down the length of a tree)

我真的很喜欢 Anon 代码的简单性；它的优雅。但是，有时优雅的代码并不总能转化为直观易懂的代码。所以，这是我试图展示一种需要 Log(n) 更多空间的类似方法，但对于那些最熟悉深度优先搜索（沿着树的长度向下）的人来说，应该更自然地阅读

The following snippet of code sets nodes belonging to a particular level in a list, and arranges that list in a list that holds all the levels of the tree. Hence the List<List<BinaryNode<T>>>that you will see below. The rest should be fairly self explanatory.

以下代码片段设置属于列表中特定级别的节点，并将该列表排列在包含树的所有级别的列表中。因此List<List<BinaryNode<T>>>，您将在下面看到。其余的应该是不言自明的。

public static final <T extends Comparable<T>> void printTreeInLevelOrder(
        BinaryTree<T> tree) {
    BinaryNode<T> root = tree.getRoot();
    List<List<BinaryNode<T>>> levels = new ArrayList<List<BinaryNode<T>>>();
    addNodesToLevels(root, levels, 0);
    for(List<BinaryNode<T>> level: levels){
        for(BinaryNode<T> node: level){
            System.out.print(node+ " ");
        }
        System.out.println();
    }
}

private static final <T extends Comparable<T>> void addNodesToLevels(
        BinaryNode<T> node, List<List<BinaryNode<T>>> levels, int level) {
    if(null == node){
        return;
    }

    List<BinaryNode<T>> levelNodes;
    if(levels.size() == level){
        levelNodes = new ArrayList<BinaryNode<T>>();
        levels.add(level, levelNodes);
    }
    else{
        levelNodes = levels.get(level);
    }

    levelNodes.add(node);
    addNodesToLevels(node.getLeftChild(), levels, level+1);
    addNodesToLevels(node.getRightChild(), levels, level+1);
}

回答by Luis Herrera

Just thought of sharing Anon's suggestion in real java code and fixing a couple of KEY issues (like there is not an end condition for the recursion so it never stops adding to the stack, and not checking for null in the received array gets you a null pointer exception).

只是想在真正的 Java 代码中分享 Anon 的建议并修复几个关键问题（比如递归没有结束条件，所以它永远不会停止添加到堆栈中，并且不检查接收到的数组中的 null 会让你得到一个 null指针异常）。

Also there is no exception as Eric Hauser suggests, because it is not modifying the collection its looping through, it's modifying a new one.

也不例外，正如 Eric Hauser 所建议的那样，因为它没有修改它循环的集合，而是修改一个新的集合。

Here it goes:

它是这样的：

public void levelOrder(List<TreeNode> n) {
    List<TreeNode> next = new ArrayList<TreeNode>();
    for (TreeNode t : n) {
        if (t != null) {
            System.out.print(t.getValue());
            next.add(t.getLeftChild());
            next.add(t.getRightChild());
        }
    }
    System.out.println();
    if(next.size() > 0)levelOrder(next);
}

回答by Naveen

public void printAllLevels(BNode node, int h){
    int i;
    for(i=1;i<=h;i++){
        printLevel(node,i);
        System.out.println();
    }
}

public void printLevel(BNode node, int level){
    if (node==null)
        return;
    if (level==1)
        System.out.print(node.value + " ");
        else if (level>1){
            printLevel(node.left, level-1);
            printLevel(node.right, level-1);
        }
}

public int height(BNode node) {
    if (node == null) {
        return 0;
    } else {
        return 1 + Math.max(height(node.left),
                height(node.right));
    }
}

First of all, I do not like to take credit for this solution. It's a modification of somebody's function and I tailored it to provide the solution.

首先，我不喜欢将此解决方案归功于自己。这是对某人功能的修改，我对其进行了定制以提供解决方案。

I am using 3 functions here.

我在这里使用了 3 个函数。

1. First I calculate the height of the tree.
2. I then have a function to print a particular level of the tree.
3. Using the height of the tree and the function to print the level of a tree, I traverse the tree and iterate and print all levels of the tree using my third function.

1. 首先我计算树的高度。
2. 然后我有一个函数来打印树的特定级别。
3. 使用树的高度和打印树级别的函数，我遍历树并使用我的第三个函数迭代和打印树的所有级别。

I hope this helps.

我希望这有帮助。

EDIT: The time complexity on this solution for printing all node in level order traversal will not be O(n). The reason being, each time you go down a level, you will visit the same nodes again and again.

编辑：此解决方案在级别顺序遍历中打印所有节点的时间复杂度不会是 O(n)。原因是，每次下降一个级别，您都会一次又一次地访问相同的节点。

If you are looking for a O(n) solution, i think using Queues would be a better option.

如果您正在寻找 O(n) 解决方案，我认为使用队列将是更好的选择。

回答by Reddy

Here is the code, this question was asked to me in one of the interviews...

这是代码，在一次采访中向我提出了这个问题......

public void printTree(TreeNode tmpRoot) {

        Queue<TreeNode> currentLevel = new LinkedList<TreeNode>();
        Queue<TreeNode> nextLevel = new LinkedList<TreeNode>();

        currentLevel.add(tmpRoot);

        while (!currentLevel.isEmpty()) {
            Iterator<TreeNode> iter = currentLevel.iterator();
            while (iter.hasNext()) {
                TreeNode currentNode = iter.next();
                if (currentNode.left != null) {
                    nextLevel.add(currentNode.left);
                }
                if (currentNode.right != null) {
                    nextLevel.add(currentNode.right);
                }
                System.out.print(currentNode.value + " ");
            }
            System.out.println();
            currentLevel = nextLevel;
            nextLevel = new LinkedList<TreeNode>();

        }

    }

回答by Gautam

Following implementation uses 2 queues. Using ListBlokcingQueuehere but any queue would work.

以下实现使用 2 个队列。在这里使用ListBlokcingQueue但任何队列都可以使用。

import java.util.concurrent.*;

public class Test5 {

    public class Tree {
        private String value;
        private Tree left;
        private Tree right;

        public Tree(String value) {
            this.value = value;
        }

        public void setLeft(Tree t) {
            this.left = t;
        }

        public void setRight(Tree t) {
            this.right = t;
        }

        public Tree getLeft() {
            return this.left;
        }

        public Tree getRight() {
            return this.right;
        }

        public String getValue() {
            return this.value;
        }
    }

    Tree tree = null;

    public void setTree(Tree t) {
        this.tree = t;
    }

    public void printTree() {
        LinkedBlockingQueue<Tree> q = new LinkedBlockingQueue<Tree>();
        q.add(this.tree);
        while (true) {
            LinkedBlockingQueue<Tree> subQueue = new LinkedBlockingQueue<Tree>();
            while (!q.isEmpty()) {
                Tree aTree = q.remove();
                System.out.print(aTree.getValue() + ", ");
                if (aTree.getLeft() != null) {
                    subQueue.add(aTree.getLeft());
                }
                if (aTree.getRight() != null) {
                    subQueue.add(aTree.getRight());
                }
            }
            System.out.println("");
            if (subQueue.isEmpty()) {
                return;
            } else {
                q = subQueue;
            }
        }
    }

    public void testPrint() {
        Tree a = new Tree("A");
        a.setLeft(new Tree("B"));
        a.setRight(new Tree("C"));
        a.getLeft().setLeft(new Tree("D"));
        a.getLeft().setRight(new Tree("E"));
        a.getRight().setLeft(new Tree("F"));
        a.getRight().setRight(new Tree("G"));
        setTree(a);
        printTree();
    }

    public static void main(String args[]) {
        Test5 test5 = new Test5();
        test5.testPrint();
    }
}

回答by Raja Krishnan

I think we can achieve this by using one queue itself. This is a java implementation using one queue only. Based on BFS...

我认为我们可以通过使用一个队列本身来实现这一点。这是仅使用一个队列的 Java 实现。基于 BFS...

public void BFSPrint()
{
    Queue<Node> q = new LinkedList<Node>();
    q.offer(root);
    BFSPrint(q);
}

private void BFSPrint(Queue<Node> q)
{
    if(q.isEmpty())
        return;
    int qLen = q.size(),i=0;
     /*limiting it to q size when it is passed, 
       this will make it print in next lines. if we use iterator instead, 
       we will again have same output as question, because iterator 
       will end only q empties*/
    while(i<qLen) 
        {
        Node current = q.remove();
        System.out.print(current.data+" ");
        if(current.left!=null)
            q.offer(current.left);
        if(current.right!=null)
            q.offer(current.right);
        i++;
    }
    System.out.println();
    BFSPrint(q);

}

回答by Luca

This is the easiest solution

这是最简单的解决方案

public void byLevel(Node root){
     Queue<Node> level  = new LinkedList<>();
     level.add(root);
     while(!level.isEmpty()){
         Node node = level.poll();
         System.out.print(node.item + " ");
         if(node.leftChild!= null)
         level.add(node.leftChild);
         if(node.rightChild!= null)
         level.add(node.rightChild);
     }
}

https://github.com/camluca/Samples/blob/master/Tree.javain my github you can find other helpful functions in the class Tree like:

https://github.com/camluca/Samples/blob/master/Tree.java在我的 github 中，您可以在 Tree 类中找到其他有用的功能，例如：

Displaying the tree

显示树

****......................................................****
                            42
            25                              65                              
    12              37              43              87              
9      13      30      --      --      --      --      99      
****......................................................****
Inorder traversal
9 12 13 25 30 37 42 43 65 87 99  
Preorder traversal
42 25 12 9 13 37 30 65 43 87 99  
Postorder traversal
9 13 12 30 37 25 43 99 87 65 42  
By Level
42 25 65 12 37 43 87 9 13 30 99  

回答by mvogiatzis

the top solutions only print the children of each node together. This is wrong according to the description.

顶级解决方案仅将每个节点的子节点打印在一起。根据描述，这是错误的。

What we need is all the nodes of the same level together in the same line.

我们需要的是同一级别的所有节点一起在同一行中。

1) Apply BFS

1) 申请 BFS

2) Store heights of nodes to a map that will hold level - list of nodes.

2）将节点的高度存储到将保持级别的地图 - 节点列表。

3) Iterate over the map and print out the results.

3) 遍历地图并打印出结果。

See Java code below:

请参阅下面的 Java 代码：

public void printByLevel(Node root){
    Queue<Node> q = new LinkedBlockingQueue<Node>();
    root.visited = true;
    root.height=1;
    q.add(root);
    //Node height - list of nodes with same level
    Map<Integer, List<Node>> buckets = new HashMap<Integer, List<Node>>();
    addToBuckets(buckets, root);
    while (!q.isEmpty()){
        Node r = q.poll();

        if (r.adjacent!=null)
        for (Node n : r.adjacent){
            if (!n.visited){
                n.height = r.height+1; //adjust new height
                addToBuckets(buckets, n);
                n.visited = true;
                q.add(n);
            }
        }
    }

    //iterate over buckets and print each list
    printMap(buckets);

}

//helper method that adds to Buckets list
private void addToBuckets(Map<Integer, List<Node>> buckets, Node n){
        List<Node> currlist = buckets.get(n.height);
    if (currlist==null)
    {
        List<Node> list = new ArrayList<Node>();
        list.add(n);
        buckets.put(n.height, list);
    }
    else{
        currlist.add(n);
    }

}

//prints the Map
private void printMap(Map<Integer, List<Node>> buckets){
    for (Entry<Integer, List<Node>> e : buckets.entrySet()){
        for (Node n : e.getValue()){
            System.out.print(n.value + " ");
        }
    System.out.println();
}