聊聊算法 • 二叉树遍历（前序、中序、后序、层次）

vlambda
2021-06-12

聊聊算法 • 二叉树遍历（前序、中序、后序、层次）

今天我们聊聊二叉树的遍历，这篇文章将介绍二叉树的前序遍历、中序遍历、后序遍历、层次遍历。开始之前，先来普及几个基础概念。

什么是二叉树

简单来说，有 0、1、2 个子节点的树，就是二叉树，空树也是一棵有效二叉树。

什么是严格二叉树

二叉树中的节点，要么有两个子节点，要么没有子节点，这就是严格二叉树。

什么是满二叉树

二叉树的每个节点恰好有两个子节点，且叶子节点在同一层，这就是满二叉树。

什么是完全二叉树

若二叉树的高度为h，如果所有叶子节点的深度为h或h-1，且节点编号序列中数字连续，无遗漏，这样的二叉树就是完全二叉树。

高度与深度
高度：从当前节点到最深节点的路径长度
深度：从根节点到当前节点的路径长度

这些概念，理解即可，话不多叙，进入主题，开始遍历二叉树。

什么是前序、中序、后序、层次

用最简单的语言介绍，前序：中 - 左 - 右，中序：左 - 中 - 右，后序：左 - 右 - 中，层次：按层从左至右。

树节点实体类

@Getter@Setterpublic class D_BinaryTree_Node { // 数据存储 private int data; // 左节点 private D_BinaryTree_Node left; // 右节点    private D_BinaryTree_Node right; // 构造函数:参数:data public D_BinaryTree_Node(int data) { this.data = data;    }}

前序遍历

/** * 前序遍历，方式一（递归），时间复杂度 O(n) * @param root : D_BinaryTree_Node : 根节点 */public void preTraversal_01(D_BinaryTree_Node root) { if (root != null) { System.out.printf("%d\t", root.getData()); preTraversal_01(root.getLeft()); preTraversal_01(root.getRight()); }}
/** * 前序遍历，方式二（非递归），时间复杂度 O(n) * @param root : D_BinaryTree_Node : 根节点 */public void preTraversal_02(D_BinaryTree_Node root) { // 跳出函数 if (root == null) return; Stack stack = new Stack(); while (true) { while (root != null) { System.out.printf("%d\t", root.getData()); // 将整个节点压入栈中，记录当前节点 ( 后进先出 ） stack.push(root); root = root.getLeft(); } if (stack.isEmpty()) { break; // 跳出循环 } root = (D_BinaryTree_Node) stack.pop(); root = root.getRight(); } return;}

中序遍历

/** * 中序遍历，方式一（递归），时间复杂度 O(n) * @param root : D_BinaryTree_Node : 根节点 */public void cenTraversal_01(D_BinaryTree_Node root) { if (root != null) { cenTraversal_01(root.getLeft()); System.out.printf("%d\t", root.getData()); cenTraversal_01(root.getRight()); }}
/** * 中序遍历，方式二（非递归），时间复杂度 O(n) * @param root : D_BinaryTree_Node : 根节点 */public void cenTraversal_02(D_BinaryTree_Node root) { // 如果节点为空，跳出函数 if (root == null) { return; } Stack stack = new Stack(); while (true) { while (root != null) { // 当该条件满足时，root为左子树最下边一个节点 stack.push(root); root = root.getLeft(); } // 如果Stack为空，跳出外层循环 if (stack.isEmpty()) { break; } root = (D_BinaryTree_Node) stack.pop(); System.out.printf("%d\t", root.getData()); root = root.getRight(); }}

后序遍历

/** * 后序遍历，方式一（递归），时间复杂度 O(n) * @param root : D_BinaryTree_Node : 根节点 */public void postTraversal_01(D_BinaryTree_Node root) { if (root != null) { postTraversal_01(root.getLeft()); postTraversal_01(root.getRight()); System.out.printf("%d\t", root.getData()); }}
/** * 后序遍历，方式二（非递归），时间复杂度 O(n) * @param root : D_BinaryTree_Node : 根节点 */public void postOrderTraverse(D_BinaryTree_Node root) { D_BinaryTree_Node currNode = null; D_BinaryTree_Node tempNode = null; Stack<D_BinaryTree_Node> stack = new Stack(); stack.push(root); while (true) { if (stack.isEmpty()) { return; } currNode = stack.peek(); if ((currNode.getLeft() == null && currNode.getRight() == null) || (tempNode != null && (tempNode == currNode.getLeft() || tempNode == currNode.getRight()))) { System.out.printf("%d\t", currNode.getData()); stack.pop(); tempNode = currNode; } else { if (currNode.getRight() != null) stack.push(currNode.getRight()); if (currNode.getLeft() != null) stack.push(currNode.getLeft()); } }}

层次遍历

/** * 层次遍历 （时间复杂度为O(N)） * @param root : D_BinaryTree_Node : 根节点 */public void graTraversal(D_BinaryTree_Node root) { if (root == null) { return; } D_BinaryTree_Node currentNode; Queue<D_BinaryTree_Node> queue = new ConcurrentLinkedDeque(); queue.add(root); while (!queue.isEmpty()) { currentNode = queue.remove(); System.out.printf("%d\t", currentNode.getData()); if (currentNode.getLeft() != null) { queue.add(currentNode.getLeft()); } if (currentNode.getRight() != null) { queue.add(currentNode.getRight()); } } queue.clear();}