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

下面是測試用例及結果，與預期結果一致（多出的一個行號先忽略了吧….）。

測試結果