Java使用特定格式的级别顺序打印二叉树

好的，我已经阅读了所有其他相关问题，但找不到有助于java的问题。 我从破译其他语言的内容中得到了一般性的想法; 但我还没搞清楚。

问题：我想进行排序（我使用递归工作）并将其打印出树的一般形状。

所以说我有这个：

1 / \ 2 3 / / \ 4 5 6 

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

 1 2 3 4 5 6 

我想像这样打印出来：

 1 2 3 4 5 6 

在你给我一个关于做我的工作的道德讲话之前……我已经完成了我的AP Comp Sci项目并且当我的老师提到了广度优先搜索的东西时对此感到好奇。

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

 /** * 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); } 

从我可以弄清楚，我将需要使用树的总高度，并使用一个水平计数器…只有问题是我的水平计数器在我的levelOrder使用递归返回树时保持计数。

对不起，如果这是很多，但一些提示会很好。 🙂

Answer 1

这是代码，在一次采访中我问过这个问题……

 public void printTree(TreeNode tmpRoot) { Queue currentLevel = new LinkedList(); Queue nextLevel = new LinkedList(); currentLevel.add(tmpRoot); while (!currentLevel.isEmpty()) { Iterator 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(); } } 

Answer 2

这是最简单的解决方案

 public void byLevel(Node root){ Queue 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.java在我的github中你可以在类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 

Answer 3

我是这样做的：

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

（最初将成为真正的代码 – 中途变得无聊，所以它是psueodocodey）

Answer 4

只是想在真正的java代码中共享Anon的建议并修复一些KEY问题（比如没有递归的结束条件，所以它永远不会停止添加到堆栈，而不是在接收到的数组中检查null会得到null指针exception）。

Eric Hauser建议也不例外，因为它不会修改集合的循环，它正在修改一个新集合。

它来了：

 public void levelOrder(List n) { List next = new ArrayList(); 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); } 

Answer 5

下面的方法返回包含所有节点的ArrayList的ArrayList： –

  public ArrayList> levelOrder(TreeNode root) { ArrayList> result = new ArrayList>(); if(root == null) return result; Queue q1 = new LinkedList(); Queue q2 = new LinkedList(); ArrayList list = new ArrayList(); q1.add(root); while(!q1.isEmpty() || !q2.isEmpty()){ while(!q1.isEmpty()){ TreeNode temp = (TreeNode)q1.poll(); list.add(temp.val); if(temp.left != null) q2.add(temp.left); if(temp.right != null) q2.add(temp.right); } if(list.size() > 0)result.add(new ArrayList(list)); list.clear(); while(!q2.isEmpty()){ TreeNode temp = (TreeNode)q2.poll(); list.add(temp.val); if(temp.left != null) q1.add(temp.left); if(temp.right != null) q1.add(temp.right); } if(list.size() > 0)result.add(new ArrayList(list)); list.clear(); } return result; } 

Answer 6

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

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

  //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 currentLevel = new LinkedList(); //Queue that holds the nodes on the current level Queue nextLevel = new LinkedList(); //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; } 

Answer 7

我非常喜欢Anon代码的简单性; 它的优雅。 但是， 有时优雅的代码并不总是转化为直观易于掌握的代码。 所以，这是我试图展示一个类似的方法，需要Log（n）更多的空间，但应该更自然地阅读那些最熟悉深度优先搜索（沿着树的长度）的人

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

 public static final > void printTreeInLevelOrder( BinaryTree tree) { BinaryNode root = tree.getRoot(); List>> levels = new ArrayList>>(); addNodesToLevels(root, levels, 0); for(List> level: levels){ for(BinaryNode node: level){ System.out.print(node+ " "); } System.out.println(); } } private static final > void addNodesToLevels( BinaryNode node, List>> levels, int level) { if(null == node){ return; } List> levelNodes; if(levels.size() == level){ levelNodes = new ArrayList>(); levels.add(level, levelNodes); } else{ levelNodes = levels.get(level); } levelNodes.add(node); addNodesToLevels(node.getLeftChild(), levels, level+1); addNodesToLevels(node.getRightChild(), levels, level+1); } 

Answer 8

以下实现使用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 q = new LinkedBlockingQueue(); q.add(this.tree); while (true) { LinkedBlockingQueue subQueue = new LinkedBlockingQueue(); 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(); } } 

Answer 9

 public class PrintATreeLevelByLevel { public static class Node{ int data; public Node left; public Node right; public Node(int data){ this.data = data; this.left = null; this.right = null; } } public void printATreeLevelByLevel(Node n){ Queue queue = new LinkedList(); queue.add(n); int node = 1; //because at root int child = 0; //initialize it with 0 while(queue.size() != 0){ Node n1 = queue.remove(); node--; System.err.print(n1.data +" "); if(n1.left !=null){ queue.add(n1.left); child ++; } if(n1.right != null){ queue.add(n1.right); child ++; } if( node == 0){ System.err.println(); node = child ; child = 0; } } } public static void main(String[]args){ PrintATreeLevelByLevel obj = new PrintATreeLevelByLevel(); Node node1 = new Node(1); Node node2 = new Node(2); Node node3 = new Node(3); Node node4 = new Node(4); Node node5 = new Node(5); Node node6 = new Node(6); Node node7 = new Node(7); Node node8 = new Node(8); node4.left = node2; node4.right = node6; node2.left = node1; // node2.right = node3; node6.left = node5; node6.right = node7; node1.left = node8; obj.printATreeLevelByLevel(node4); } 

}

Answer 10

试试这个，使用2个队列来跟踪关卡。

 public static void printByLevel(Node root){ LinkedList curLevel = new LinkedList(); LinkedList nextLevel = curLevel; StringBuilder sb = new StringBuilder(); curLevel.add(root); sb.append(root.data + "\n"); while(nextLevel.size() > 0){ nextLevel = new LinkedList(); for (int i = 0; i < curLevel.size(); i++){ Node cur = curLevel.get(i); if (cur.left != null) { nextLevel.add(cur.left); sb.append(cur.left.data + " "); } if (cur.right != null) { nextLevel.add(cur.right); sb.append(cur.right.data + " "); } } if (nextLevel.size() > 0) { sb.append("\n"); curLevel = nextLevel; } } System.out.println(sb.toString()); } 

Answer 11

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

首先，我不赞成这个解决方案。 这是对某人function的修改，我量身定制它以提供解决方案。

我在这里使用3个function。

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

我希望这有帮助。

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

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

Answer 12

我想我们可以通过使用一个队列来实现这一点。 这是一个仅使用一个队列的java实现。 基于BFS ……

 public void BFSPrint() { Queue q = new LinkedList(); q.offer(root); BFSPrint(q); } private void BFSPrint(Queue 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 

Answer 13

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

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

1）申请BFS

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

3）迭代地图并打印出结果。

请参阅下面的Java代码：

 public void printByLevel(Node root){ Queue q = new LinkedBlockingQueue(); root.visited = true; root.height=1; q.add(root); //Node height - list of nodes with same level Map> buckets = new HashMap>(); 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> buckets, Node n){ List currlist = buckets.get(n.height); if (currlist==null) { List list = new ArrayList(); list.add(n); buckets.put(n.height, list); } else{ currlist.add(n); } } //prints the Map private void printMap(Map> buckets){ for (Entry> e : buckets.entrySet()){ for (Node n : e.getValue()){ System.out.print(n.value + " "); } System.out.println(); } 

Answer 14

最简单的方法是在不使用隐式假设在每个节点中的任何级别信息的情况下执行此操作。 只需在每个级别后附加一个’null’节点。 检查此空节点以了解何时打印新行：

 public class BST{ private Node head; BST(){} public void setHead(Node val){head = val;} public static void printBinaryTreebyLevels(Node head){ if(head == null) return; Queue> q = new LinkedList<>();//assuming you have type inference (JDK 7) q.add(head); q.add(null); while(q.size() > 0){ Node n = q.poll(); if(n == null){ System.out.println(); q.add(null); n = q.poll(); } System.out.print(n.value+" "); if(n.left != null) q.add(n.left); if(n.right != null) q.add(n.right); } } public static void main(String[] args){ BST b = new BST(); c = buildListedList().getHead();//assume we have access to this for the sake of the example b.setHead(c); printBinaryTreeByLevels(); return; } } class Node{ public Node left, right; public T value; Node(T val){value = val;} } 

Answer 15

这对我有用。 调用printLevel时，使用rootnode传递数组列表。

 void printLevel(ArrayList n){ ArrayList next = new ArrayList(); for (Node t: n) { System.out.print(t.value+" "); if (t.left!= null) next.add(t.left); if (t.right!=null) next.add(t.right); } System.out.println(); if (next.size()!=0) printLevel(next); } 

Answer 16

使用单个队列按级别顺序打印二叉树：

 public void printBFSWithQueue() { java.util.LinkedList ll = new LinkedList<>(); ll.addLast(root); ll.addLast(null); Node in = null; StringBuilder sb = new StringBuilder(); while(!ll.isEmpty()) { if(ll.peekFirst() == null) { if(ll.size() == 1) { break; } ll.removeFirst(); System.out.println(sb); sb = new StringBuilder(); ll.addLast(null); continue; } in = ll.pollFirst(); sb.append(in.v).append(" "); if(in.left != null) { ll.addLast(in.left); } if(in.right != null) { ll.addLast(in.right); } } } 

Answer 17

 void printTreePerLevel(Node root) { Queue q= new LinkedList(); q.add(root); int currentlevel=1; int nextlevel=0; List values= new ArrayList(); while(!q.isEmpty()) { Node node = q.remove(); currentlevel--; values.add(node.value); if(node.left != null) { q.add(node.left); nextlevel++; } if(node.right != null) { q.add(node.right); nextlevel++; } if(currentlevel==0) { for(Integer i:values) { System.out.print(i + ","); } System.out.println(); values.clear(); currentlevel=nextlevel; nextlevel=0; } } } 

Answer 18

一个办法

我在这里写了直接解决方案。 如果您需要详细的答案，演示代码和说明，您可以跳过并检查答案的其余标题;

 public static  void printLevelOrder(TreeNode root) { System.out.println("Tree;"); System.out.println("*****"); // null check if(root == null) { System.out.printf(" Empty\n"); return; } MyQueue> queue = new MyQueue<>(); queue.enqueue(root); while(!queue.isEmpty()) { handleLevel(queue); } } // process each level private static  void handleLevel(MyQueue> queue) { int size = queue.size(); for(int i = 0; i < size; i++) { TreeNode temp = queue.dequeue(); System.out.printf("%s ", temp.data); queue.enqueue(temp.left); queue.enqueue(temp.right); } System.out.printf("\n"); } 

B – 解释

要按级别顺序打印树，您应该使用简单的队列实现来处理每个级别。 在我的演示中，我编写了一个非常极简的简单队列类，称为MyQueue 。

公共方法printLevelOrder将TreeNode对象实例root作为代表树根的参数。 私有方法MyQueue将MyQueue实例作为参数。

在每个级别上， handleLevel方法将队列与队列的大小一样多。 控制级别限制，因为此过程仅使用与该级别的元素完全相等的队列大小执行，然后将新行字符放入输出。

C – TreeNode类

 public class TreeNode { T data; TreeNode left; TreeNode right; public TreeNode(T data) { this.data = data;; } } 

D – MyQueue类：一个简单的队列实现

 public class MyQueue { private static class Node { T data; Node next; public Node(T data) { this(data, null); } public Node(T data, Node next) { this.data = data; this.next = next; } } private Node head; private Node tail; private int size; public MyQueue() { head = null; tail = null; } public int size() { return size; } public void enqueue(T data) { if(data == null) return; if(head == null) head = tail = new Node(data); else { tail.next = new Node(data); tail = tail.next; } size++; } public T dequeue() { if(tail != null) { T temp = (T) head.data; head = head.next; size--; return temp; } return null; } public boolean isEmpty() { return size == 0; } public void printQueue() { System.out.println("Queue: "); if(head == null) return; else { Node temp = head; while(temp != null) { System.out.printf("%s ", temp.data); temp = temp.next; } } System.out.printf("%n"); } } 

E – DEMO：按级别顺序打印树

 public class LevelOrderPrintDemo { public static void main(String[] args) { // root level TreeNode root = new TreeNode<>(1); // level 1 root.left = new TreeNode<>(2); root.right = new TreeNode<>(3); // level 2 root.left.left = new TreeNode<>(4); root.right.left = new TreeNode<>(5); root.right.right = new TreeNode<>(6); /* * 1 root * / \ * 2 3 level-1 * / / \ * 4 5 6 level-2 */ printLevelOrder(root); } public static  void printLevelOrder(TreeNode root) { System.out.println("Tree;"); System.out.println("*****"); // null check if(root == null) { System.out.printf(" Empty\n"); return; } MyQueue> queue = new MyQueue<>(); queue.enqueue(root); while(!queue.isEmpty()) { handleLevel(queue); } } // process each level private static  void handleLevel(MyQueue> queue) { int size = queue.size(); for(int i = 0; i < size; i++) { TreeNode temp = queue.dequeue(); System.out.printf("%s ", temp.data); queue.enqueue(temp.left); queue.enqueue(temp.right); } System.out.printf("\n"); } } 

F – 样本输入

  1 // root / \ 2 3 // level-1 / / \ 4 5 6 // level-2 

G – 样本输出

 Tree; ***** 1 2 3 4 5 6 

Answer 19

Python实现

 # Function to print level order traversal of tree def printLevelOrder(root): h = height(root) for i in range(1, h+1): printGivenLevel(root, i) # Print nodes at a given level def printGivenLevel(root , level): if root is None: return if level == 1: print "%d" %(root.data), elif level > 1 : printGivenLevel(root.left , level-1) printGivenLevel(root.right , level-1) """ Compute the height of a tree--the number of nodes along the longest path from the root node down to the farthest leaf node """ def height(node): if node is None: return 0 else : # Compute the height of each subtree lheight = height(node.left) rheight = height(node.right) #Use the larger one if lheight > rheight : return lheight+1 else: return rheight+1 

Answer 20

  Queue queue = new LinkedList<>(); queue.add(root); Node leftMost = null; while (!queue.isEmpty()) { Node node = queue.poll(); if (leftMost == node) { System.out.println(); leftMost = null; } System.out.print(node.getData() + " "); Node left = node.getLeft(); if (left != null) { queue.add(left); if (leftMost == null) { leftMost = left; } } Node right = node.getRight(); if (right != null) { queue.add(right); if (leftMost == null) { leftMost = right; } } } 

Answer 21

哇。 这么多答案。 对于它的价值，我的解决方案是这样的：

我们知道级别顺序遍历的常规方法：对于每个节点，首先访问节点，然后将其子节点放入FIFO队列。 我们需要做的是跟踪每个级别，以便该级别的所有节点都打印在一行中，而不需要换行。

所以我自然而然地认为它是一个排队的队列。 主队列包含每个级别的内部队列。 每个内部队列按FIFO顺序包含一个级别中的所有节点。 当我们将内部队列出列时，我们遍历它，将其所有子节点添加到新队列，并将此队列添加到主队列。

 public static void printByLevel(Node root) { Queue firstQ = new LinkedList<>(); firstQ.add(root); Queue> mainQ = new LinkedList<>(); mainQ.add(firstQ); while (!mainQ.isEmpty()) { Queue levelQ = mainQ.remove(); Queue nextLevelQ = new LinkedList<>(); for (Node x : levelQ) { System.out.print(x.key + " "); if (x.left != null) nextLevelQ.add(x.left); if (x.right != null) nextLevelQ.add(x.right); } if (!nextLevelQ.isEmpty()) mainQ.add(nextLevelQ); System.out.println(); } } 

Answer 22

 public void printAtLevel(int i){ printAtLevel(root,i); } private void printAtLevel(BTNode n,int i){ if(n != null){ sop(n.data); } else { printAtLevel(n.left,i-1); printAtLevel(n.right,i-1); } } private void printAtLevel(BTNode n,int i){ if(n != null){ sop(n.data); printAtLevel(n.left,i-1); printAtLevel(n.right,i-1); } }