二叉树的遍历（前序、中序、后序、层次）

概述

二叉树的遍历主要有前序遍历、中序遍历、后序遍历、层次遍历
前三种遍历常见考察点是递归遍历、非递归遍历、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);}}

总结

以上是生活随笔为你收集整理的二叉树的遍历（前序、中序、后序、层次）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。