二叉树基本算法二叉树基本算法

二叉树定义：二叉树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。更多解释，详见堆和堆排序。

文章图片

一、递归遍历 1、先序遍历根左右。a，b，d，e，c，f，g

/** * 二叉树：先序遍历。根-左-右 * * 经典递归写法 * * @author Java和算法学习：周一 */ public static void pre(Node head) { if (head == null) { return; } System.out.println(head.value); pre(head.left); pre(head.right); }

2、中序遍历左根右。d，b，e，a，f，c，g

/** * 二叉树：中序遍历。左-根-右 * * 经典递归写法 * * @author Java和算法学习：周一 */ public static void in(Node head) { if (head == null) { return; } in(head.left); System.out.println(head.value); in(head.right); }

3、后序遍历左右根。d，e，b，f，g，c，a

/** * 二叉树：后序遍历。左-右-根 * * 经典递归写法 * * @author Java和算法学习：周一 */ public static void pos(Node head) { if (head == null) { return; } pos(head.left); pos(head.right); System.out.println(head.value); }

经典的递归版先序、中序、后序遍历，我们再熟悉不过了，今天我们说些不同的，递归序。
仔细点的小伙伴似乎已经发现，递归的先序、中序、后序遍历其实是很相似的，就是打印的时机不同。这是因为，它们实际是由递归序改写而来的。啥是递归序，就是每次经过自己的时候，都打印节点的值，最后打印出来的即是递归序。
在递归序的基础上，只打印第一次经过自己时的值，即是先序；只打印第二次经过自己的值，即是中序；只打印第三次经过自己的值，即是后序。
4、递归序

/** * 递归序 * * @author Java和算法学习：周一 */ public static void f(Node head) { if (head == null) { return; } // 1 System.out.println(head.value); f(head.left); // 2 System.out.println(head.value); f(head.right); // 3 System.out.println(head.value); }

一个结论：已知一个二叉树的先序遍历和后序遍历，某个节点X，X先序遍历之前的节点集合为A，X后序遍历之后的节点集合为B，那么 A 和 B 的交集一定是X节点的所有祖先节点。
二、非递归遍历 1、先序遍历（1）准备一个栈，压入当前节点（即头节点）
（2）弹出栈顶元素，打印对应的值
（3）此元素有右孩子往栈压入右孩子，有左孩子往栈压入左孩子（先右再左）
（4）一直执行2、3步，直到栈为空。

/** * 非递归先序遍历 * * @author Java和算法学习：周一 */ public static void pre(Node head) { if (head != null) { Stack stack = new Stack<>(); // 压入当前节点 stack.push(head); while (!stack.isEmpty()) { // 弹出栈顶元素 Node current = stack.pop(); System.out.print(current.value + " "); // 先压入右孩子，再压入左孩子 if (current.right != null) { stack.push(current.right); } if (current.left != null) { stack.push(current.left); } } } }

2、中序遍历（1）准备一个栈
（2）压入以当前节点current为头节点的整个左子树（入栈一个，current就移动到左孩子），直到为空
（3）弹出栈顶元素，打印其值，以当前弹出元素的右孩子为current节点，重复第2步
（4）当栈为空时结束

/** * 非递归中序遍历 * * @author Java和算法学习：周一 */ public static void in(Node head) { if (head != null) { Stack stack = new Stack<>(); Node current = head; while (!stack.isEmpty() || current != null) { if (current != null) { // 将当前节点的整个左子树入栈 stack.push(current); current = current.left; } else { // 左子树入栈完后，弹出栈顶元素 Node pop = stack.pop(); System.out.print(pop.value + " "); // 以当前弹出元素的右孩子为current节点，继续循环 current = pop.right; } } } }

3、后序遍历（1）准备两个栈stackA，stackB；stackA压入当前节点（即头节点）
（2）弹出栈顶元素，压入stackB
（3）此元素有左孩子往stackA栈压入左孩子，有右孩子往stackA栈压入右孩子（先左再右）
（4）一直执行2、3步，直到stackA栈为空。
（5）打印所有stackB栈的元素
相当于stackA出栈顺序是根右左，最后stackB出栈顺序是左右根。

/** * 非递归后序遍历 * * @author Java和算法学习：周一 */ public static void pos(Node head) { if (head != null) { Stack stackA = new Stack<>(); Stack stackB = new Stack<>(); stackA.push(head); while (!stackA.isEmpty()) { // stackA出栈顺序是根右左 Node current = stackA.pop(); // stackB入栈顺序是根右左 stackB.push(current); // stackA先左孩子入栈，再右孩子入栈 if (current.left != null) { stackA.push(current.left); } if (current.right != null) { stackA.push(current.right); } }// stackB出栈顺序是左右根 while (!stackB.isEmpty()) { System.out.print(stackB.pop().value + " "); } } }

三、二叉树按层遍历（1）准备一个队列，头节点入队
（2）出队一个节点，打印其值；出队节点有左孩子则左孩子入队，有右孩子则右孩子入队
（3）循环执行第2步，直到队列为空

/** * 二叉树按层遍历 * * @author Java和算法学习：周一 */ public static void levelTraversal(Node head) { if (head == null) { return; } // 准备一个队列 Queue queue = new LinkedList<>(); // 头节点入队 queue.offer(head); while (!queue.isEmpty()) { // 从队列中弹出一个节点 Node current = queue.poll(); // 打印 System.out.print(current.value + " "); // 有左孩子则左孩子入队 if (current.left != null) { queue.offer(current.left); } // 有右孩子则右孩子入队 if (current.right != null) { queue.offer(current.right); } } }

本文主要介绍了，二叉树的先序、中序、后序的递归遍历（以及曾经不知道的递归序）、非递归遍历，二叉树的层序遍历。
【二叉树基本算法】本文全部代码：https://github.com/monday-pro/algorithm-study/tree/master/src/basic/binarytree