Java实现二叉树带行号的层序遍历

2019-11-06 09:27:38

字体：大中小

来源：转载

供稿：网友

　　最近在看面试题的时候发现，一些基础的算法都记不住了，只是能大概说出个原理….为了加深记忆，这里对一些简单的算法题进行一个归纳。

　　下面的代码主要解决的问题是：给定一颗二叉树，要求输出它的层序遍历，并在每行开始时输出行号。

测试用例样例：　　输入：节点值为1-7的满二叉树。　　预期结果：　　　　　　1 : 1 　　　　　　2 : 2 3 　　　　　　3 : 4 5 6 7

　　下面是java实现：

import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;import java.util.Stack;/* Created by Flynnon on 17-2-26. 对二叉树带行号的层序遍历的归纳 *//** * 定义节点类 * 为了简单就不定义getter/setter方法了 */class Node { public int value; public Node left; public Node right; public Node() { this(0); } public Node(int v) { this.value = v; this.left = null; this.right = null; }}/** * 对二叉树进行操作的工具类 */class PRintBinaryTree { //私有化构造函数 private PrintBinaryTree() { throw new RuntimeException("该工具类不应该被实例化"); } /** * 层序遍历二叉树（每一行从左到右，整体上从上到下） * 主要思路：利用队列先进先出的性质保存顺序 * * @param root 要遍历的二叉树的根节点 */ public static void levelTraversal(Node root) { Queue<Node> q = new LinkedList<>(); q.add(root); while (!q.isEmpty()) { Node temp = q.poll(); if (temp != null) { System.out.print(temp.value + " "); q.add(temp.left); q.add(temp.right); } } } /** * 层序遍历二叉树（每一行从左到右，整体上从上到下）,并附带行号 * 主要思路：利用队列先进先出的性质保存顺序来层序遍历二叉树。 * 使用curLineLast与nextLineLast两个节点标志来标识遍历过程中当前行结尾节点与下一行结尾节点， * 再使用一个lineNo整形量来记录当前行号（初始设为1），并在curLineLast节点更替时，更新lineNo的值并按格式打印即可。 * 注：nextLineLast始终指向最新遍历到的节点 * @param root 要遍历的二叉树的根节点 */ public static void levelTraversalWithLineNo(Node root) { // 加入断言，保证root不为null assert root != null; // curLineLast : 当前行结尾节点 // nextLineLast : 下一行结尾节点 // 刚开始时，curLineLast与nextLineLast均指向根节点 Node curLineLast = root, nextLineLast = root; // 设根节点所在的行为第1行 int lineNo = 1; System.out.print(lineNo + " : "); Queue<Node> q = new LinkedList<>(); q.add(root); while (!q.isEmpty()) { Node temp = q.poll(); // 只有当前节点的子节点不为空时，nextLineLast才需要更改指向的目标 if (temp.left != null) { q.add(temp.left); nextLineLast = temp.left; } if (temp.right != null) { q.add(temp.right); nextLineLast = temp.right; } System.out.print(temp.value + " "); // 当出栈节点为当前行尾节点时，说明该换行了 if (curLineLast == temp) { // 将当前行尾节点指向下一行尾节点 curLineLast = nextLineLast; System.out.print(System.lineSeparator() + ++lineNo + " : "); } } }}/** * 测试类 */public class BinaryTree { // 以1 2 4 -1 -1 5 -1 -1 3 6 -1 -1 7 -1 -1为例 public static void main(String[] args) { Scanner sc = new Scanner(System.in); Node root = PrintBinaryTree.createTreeNode(sc); sc.close(); System.out.print("层序遍历:"); PrintBinaryTree.levelTraversal(root); System.out.println("带行号的层序遍历:"); PrintBinaryTree.levelTraversalWithLineNo(root); }}

下面是测试用例及结果，与预期结果一致（多出的一个行号先忽略了吧….）。

测试结果