概述

二叉樹的遍歷主要有前序遍歷、中序遍歷、后序遍歷、層次遍歷
前三種遍歷常見考察點是遞歸遍歷、非遞歸遍歷、moriss遍歷，層次遍歷的考察點是：是否分層打印。

代碼

遞歸遍歷（前序、中序、后序），包含***由數組構造二叉樹***：

package 二叉樹的遍歷;//二叉樹遍歷的遞歸實現 import java.util.LinkedList; import java.util.List;public class SearchTree {private int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };private static List<TreeNode> TreeNodeList = null;/*** 內部類：節點*/private static class TreeNode {TreeNode leftChild;TreeNode rightChild;int data;TreeNode(int newData) {leftChild = null;rightChild = null;data = newData;}}public void createBinTree() {TreeNodeList = new LinkedList<TreeNode>(); //多個TreeNode組成的鏈表容器// 將一個數組的值依次轉換為TreeNode節點for (int TreeNodeIndex = 0; TreeNodeIndex < array.length; TreeNodeIndex++) {TreeNodeList.add(new TreeNode(array[TreeNodeIndex]));}// 對前lastParentIndex-1個父節點按照父節點與孩子節點的數字關系建立二叉樹for (int parentIndex = 0; parentIndex < array.length / 2 - 1; parentIndex++) {// 左孩子TreeNodeList.get(parentIndex).leftChild = TreeNodeList.get(parentIndex * 2 + 1);// 右孩子TreeNodeList.get(parentIndex).rightChild = TreeNodeList.get(parentIndex * 2 + 2);}// 最后一個父節點:因為最后一個父節點可能沒有右孩子，所以單獨拿出來處理int lastParentIndex = array.length / 2 - 1;// 左孩子TreeNodeList.get(lastParentIndex).leftChild = TreeNodeList.get(lastParentIndex * 2 + 1);// 右孩子,如果數組的長度為奇數才建立右孩子if (array.length % 2 == 1) {TreeNodeList.get(lastParentIndex).rightChild = TreeNodeList.get(lastParentIndex * 2 + 2);}}/*** 先序遍歷** 這三種不同的遍歷結構都是一樣的，只是先后順序不一樣而已** @param TreeNode* 遍歷的節點*/public static void preOrderTraverse(TreeNode TreeNode) {if (TreeNode == null)return;System.out.print(TreeNode.data + " ");preOrderTraverse(TreeNode.leftChild);preOrderTraverse(TreeNode.rightChild);}/*** 中序遍歷** 這三種不同的遍歷結構都是一樣的，只是先后順序不一樣而已** @param TreeNode* 遍歷的節點*/public static void inOrderTraverse(TreeNode TreeNode) {if (TreeNode == null)return;inOrderTraverse(TreeNode.leftChild);System.out.print(TreeNode.data + " ");inOrderTraverse(TreeNode.rightChild);}/*** 后序遍歷** 這三種不同的遍歷結構都是一樣的，只是先后順序不一樣而已** @param TreeNode* 遍歷的節點*/public static void postOrderTraverse(TreeNode TreeNode) {if (TreeNode == null)return;postOrderTraverse(TreeNode.leftChild);postOrderTraverse(TreeNode.rightChild);System.out.print(TreeNode.data + " ");}public static void main(String[] args) {SearchTree binTree = new SearchTree();binTree.createBinTree();// TreeNodeList中第0個索引處的值即為根節點TreeNode root = TreeNodeList.get(0);System.out.println("先序遍歷：");preOrderTraverse(root);System.out.println();System.out.println("中序遍歷：");inOrderTraverse(root);System.out.println();System.out.println("后序遍歷：");postOrderTraverse(root);}}

層次遍歷

package 二叉樹的遍歷;import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue;public class 層次遍歷 {public static void main(String[] args) {TreeNode head = new TreeNode(3);head.left = new TreeNode(9);head.right = new TreeNode(20);head.right.left = new TreeNode(15);head.right.right = new TreeNode(7);levelIterator(head);}public static void levelIterator(TreeNode root) {if (root == null) {return;}LinkedList<TreeNode> queue = new LinkedList<TreeNode>();TreeNode current = null;queue.offer(root);//將根節點入隊while (!queue.isEmpty()) {current = queue.poll();//出隊隊頭元素并訪問System.out.print(current.val + "-->");if (current.left != null)//如果當前節點的左節點不為空入隊{queue.offer(current.left);}if (current.right != null)//如果當前節點的右節點不為空，把右節點入隊{queue.offer(current.right);}}} }

非遞歸遍歷

List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<Integer>();if (root == null)return result;Stack<TreeNode> stack = new Stack<TreeNode>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();result.add(node.val);if (node.right != null)stack.push(node.right);if (node.left != null)stack.push(node.left);}return result; }List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<Integer>();if (root == null)return result;Stack<TreeNode> stack = new Stack<TreeNode>();TreeNode p = root;while (p != null || !stack.isEmpty()) {if (p != null) {stack.push(p);p = p.left;} else {p = stack.pop();result.add(p.val);p = p.right;}}return result; }List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<Integer>();if (root == null)return result;Stack<TreeNode> stack = new Stack<TreeNode>();TreeNode p = root;TreeNode last = null;while (p != null || !stack.isEmpty()) {if (p != null) {stack.push(p);p = p.left;} else {TreeNode peek = stack.peek();if (peek.right != null && last != peek.right) {p = peek.right;} else {peek = stack.pop();result.add(peek.val);last = peek;}}}return result; }

MORISS遍歷

public class Code_01_MorrisTraversal {public static class Node {public int value;Node left;Node right;public Node(int data) {this.value = data;}}public static void morrisIn(Node head) {if (head == null) {return;}Node cur1 = head;Node cur2 = null;while (cur1 != null) {cur2 = cur1.left;if (cur2 != null) {while (cur2.right != null && cur2.right != cur1) {cur2 = cur2.right;}if (cur2.right == null) {cur2.right = cur1;cur1 = cur1.left;continue;} else {cur2.right = null;}}System.out.print(cur1.value + " ");cur1 = cur1.right;}System.out.println();}public static void morrisPre(Node head) {if (head == null) {return;}Node cur1 = head; // 當前節點Node cur2 = null; // 當前節點的最右節點while (cur1 != null) {cur2 = cur1.left;if (cur2 != null) {while (cur2.right != null && cur2.right != cur1) {cur2 = cur2.right; //找到最右}if (cur2.right == null) {cur2.right = cur1;System.out.print(cur1.value + " ");cur1 = cur1.left;continue;} else {cur2.right = null;}} else {System.out.print(cur1.value + " ");}cur1 = cur1.right;}System.out.println();}public static void morrisPos(Node head) {if (head == null) {return;}Node cur1 = head;Node cur2 = null;while (cur1 != null) {cur2 = cur1.left;if (cur2 != null) {while (cur2.right != null && cur2.right != cur1) {cur2 = cur2.right;}if (cur2.right == null) {cur2.right = cur1;cur1 = cur1.left;continue;} else {cur2.right = null;printEdge(cur1.left);}}cur1 = cur1.right;}printEdge(head);System.out.println();}public static void printEdge(Node head) {Node tail = reverseEdge(head);Node cur = tail;while (cur != null) {System.out.print(cur.value + " ");cur = cur.right;}reverseEdge(tail);}public static Node reverseEdge(Node from) {Node pre = null;Node next = null;while (from != null) {next = from.right;from.right = pre;pre = from;from = next;}return pre;}// for test -- print treepublic static void printTree(Node head) {System.out.println("Binary Tree:");printInOrder(head, 0, "H", 17);System.out.println();}public static void printInOrder(Node head, int height, String to, int len) {if (head == null) {return;}printInOrder(head.right, height + 1, "v", len);String val = to + head.value + to;int lenM = val.length();int lenL = (len - lenM) / 2;int lenR = len - lenM - lenL;val = getSpace(lenL) + val + getSpace(lenR);System.out.println(getSpace(height * len) + val);printInOrder(head.left, height + 1, "^", len);}public static String getSpace(int num) {String space = " ";StringBuffer buf = new StringBuffer("");for (int i = 0; i < num; i++) {buf.append(space);}return buf.toString();}public static void main(String[] args) {Node head = new Node(4);head.left = new Node(2);head.right = new Node(6);head.left.left = new Node(1);head.left.right = new Node(3);head.right.left = new Node(5);head.right.right = new Node(7);printTree(head);morrisIn(head);morrisPre(head);morrisPos(head);printTree(head);}}

總結

以上是生活随笔為你收集整理的二叉树的遍历（前序、中序、后序、层次）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。