date: 2016-08-18 9:17:00
title: 二叉树面试题汇总(二)
categories: 数据结构
版权声明：本站采用开放的[知识共享署名-非商业性使用-相同方式共享 许可协议]进行许可
所有文章出现的代码，将会出现在我的github中，名字可以根据类全名来找，我在github中的文件夹也会加目录备注。
二叉树的先序遍历
递归法
思路：
- 二叉树的先序、中序、后序遍历使用递归法实现非常简单，因为树是由递归定义的。
- 不管使用递归还是非递归方法实现对于二叉树的遍历，首先我们需要抓住遍历的关键，即对节点的访问顺序。
- 使用不同的方法，对每个节点的访问顺序不同。
- 先序遍历、中序遍历、后序遍历中，先、中、后是指根节点的访问顺序，一般二叉树分为“DLR”，其中D 代表根节点，L代表左子树，R代表右子树，先序为DLR,中序为LDR,后序为LRD
- 掌握了上面的要领，那么实现对二叉树的先中后序遍历就非常简单了。
代码实现:
public static void preOrderTraverseByRecursion(BinaryTree root) {
// 递归的出口
if (root == null)
return;
// 1、先访问根节点，在这里只是做简单的数据输出
System.out.print(root.getValue() + " ");
// 2、递归访问左子节点，因为左子节点可能还有子节点
preOrderTraverseByRecursion(root.getLeftChild());
// 3、递归访问右子节点，理由同上
preOrderTraverseByRecursion(root.getRightChild());
}
图解：
测试代码:
package com.xinpaninjava.btree;
public class BinaryTreeCountNodesTest {
public static void main(String[] args) {
BinaryTree n1 = new BinaryTree(1);
BinaryTree n2 = new BinaryTree(2);
BinaryTree n3 = new BinaryTree(3);
BinaryTree n4 = new BinaryTree(4);
BinaryTree n5 = new BinaryTree(5);
BinaryTree n6 = new BinaryTree(6);
n1.setLeftChild(n2);
n1.setRightChild(n3);
n2.setLeftChild(n4);
n2.setRightChild(n5);
n3.setRightChild(n6);
BTreeTraverse.preOrderTraverseByRecursion(n1);
}
}
树结构：
运行结果
迭代法
思路：
- 要使用非递归法实现二叉树的先序遍历，可以这样想，既然可以用递归实现，那么就可以用栈实现（为什么？）。
- 即使使用非递归实现二叉树的先序遍历，也要抓住各个节点的访问顺序，在这里，最先访问的是根节点，所以当有节点入栈时，它可以看成是其子节点的根节点，那么可以直接输出该节点的数据
- 然后再判断当前节点有无左右子节点，这里要注意栈的特点，先存右子树，再存左子树
- 如果还不能理解，可以通过自己随意画一棵二叉树，对着进栈出栈的顺序来看代码。或者自己根据先序遍历的顺序来写代码也行，重要的是想法。
代码实现：
/**
* 非递归法 遍历二叉树
*
* @param root
*/
public static void preOrderTraverseByIterative(BinaryTree root) {
// 判断当前节点是否为空，为空就空操作
if (root == null)
return;
// 定义一个栈来存储节点，一个变量来记录当前节点
Stack<BinaryTree> stack = new Stack<BinaryTree>();
BinaryTree currentNode = root;
stack.push(currentNode);
// 进入循环体，条件:栈不为空
while (!stack.isEmpty()) {
// 栈顶节点出栈并赋值给当前节点
currentNode = stack.pop();
// 输出根节点数据
System.out.print(currentNode.getValue() + "：");
// 判断当前节点有无右子树，有入栈
if (currentNode.getRightChild() != null)
stack.push(currentNode.getRightChild());
// 判断当前节点有无左子树，有入栈
if (currentNode.getLeftChild() != null)
stack.push(currentNode.getLeftChild());
}
}
树结构：
运行结果：
二叉树的中序遍历
递归法
思路:
- 抓住访问顺序，中序遍历:LDR,代码实现可以参照先序遍历。
- 首先得到根节点，但是中序遍历要先访问左子节点，所以先递归得到子节点，然后再访问根节点，最后访问右子节点
图解：
代码实现:
/**
* 使用递归中序遍历二叉树
*
* @param root
*/
public static void inOrderTraverseByRecursion(BinaryTree root) {
// 递归出口
if (root == null)
return;
// 递归访问左子树
inOrderTraverseByRecursion(root.getLeftChild());
// 访问根节点
System.out.print(root.getValue() + " ");
// 递归访问右子树
inOrderTraverseByRecursion(root.getRightChild());
}
测试代码:
package com.xinpaninjava.btree;
public class BinaryTreeCountNodesTest {
public static void main(String[] args) {
BinaryTree n1 = new BinaryTree(1);
BinaryTree n2 = new BinaryTree(2);
BinaryTree n3 = new BinaryTree(3);
BinaryTree n4 = new BinaryTree(4);
BinaryTree n5 = new BinaryTree(5);
BinaryTree n6 = new BinaryTree(6);
n1.setLeftChild(n2);
n1.setRightChild(n3);
n2.setLeftChild(n4);
n2.setRightChild(n5);
n3.setRightChild(n6);
BTreeTraverse.inOrderTraverseByRecursion(n1);
}
}
运行结果:
迭代
思路：
- 中序遍历，就先要得到左叶子节点，定义一个栈用来存储左节点（同时也可能是根节点），一个变量来指向当前节点（开始是根节点）
- 得到左叶子节点后，访问该节点，在本文中，访问的意思是：该节点出栈，并输出该节点的数据，
- 该节点出栈之后，意味着现在栈顶节点为刚刚出栈节点的根节点
- 把当前节点指向刚刚出栈节点的右子节点，到这里再返回上面的循环中，如果当前节点（此时指向了右子节点）为空，直接弹出栈顶节点（刚刚出栈节点的根节点），
图解:
实现代码:
public static void inOrderTraverseByIterative(BinaryTree root) {
// 首先判断根节点是否为空，为空空操作
if (root == null)
return;
// 创建一个栈来存储节点，创建一个节点来指向当前节点
Stack<BinaryTree> stack = new Stack<BinaryTree>();
BinaryTree currentNode = root;
// 定义一个循环,循环体为:
while (true) {
// 1、循环把左子节点的所有左节点加入栈，条件是当前节点不为空
while (currentNode != null) {
stack.push(currentNode);
currentNode = currentNode.getLeftChild();
}
// 2、当栈为空时跳出总循环,为什么在这里跳？不在外层直接定义条件？
// 因为刚刚开始栈为空，并且是在循环体内对栈进行压栈操作
if (stack.isEmpty())
break;
// 3、访问节点
currentNode = stack.pop();
System.out.print(currentNode.getValue() + " ");
// 4、把当前节点指向刚刚弹栈的右子节点
currentNode = currentNode.getRightChild();
}
}
测试代码：
情况一:根节点最后一个左子节点是叶子节点
树结构：
package com.xinpaninjava.btree;
public class BinaryTreeCountNodesTest {
public static void main(String[] args) {
BinaryTree n1 = new BinaryTree(1);
BinaryTree n2 = new BinaryTree(2);
BinaryTree n3 = new BinaryTree(3);
BinaryTree n4 = new BinaryTree(4);
BinaryTree n5 = new BinaryTree(5);
BinaryTree n6 = new BinaryTree(6);
// BinaryTree n7 = new BinaryTree(7);
// BinaryTree n8 = new BinaryTree(8);
n1.setLeftChild(n2);
n1.setRightChild(n3);
n2.setLeftChild(n4);
n2.setRightChild(n5);
n3.setRightChild(n6);
// n4.setRightChild(n7);
// n7.setLeftChild(n8);
BTreeTraverse.inOrderTraverseByIterative(n1);
}
}
运行结果：
情况二：左子树最后一个左子节点不是叶子节点
树的结构：
测试代码:
package com.xinpaninjava.btree;
public class BinaryTreeCountNodesTest {
public static void main(String[] args) {
BinaryTree n1 = new BinaryTree(1);
BinaryTree n2 = new BinaryTree(2);
BinaryTree n3 = new BinaryTree(3);
BinaryTree n4 = new BinaryTree(4);
BinaryTree n5 = new BinaryTree(5);
BinaryTree n6 = new BinaryTree(6);
BinaryTree n7 = new BinaryTree(7);
BinaryTree n8 = new BinaryTree(8);
n1.setLeftChild(n2);
n1.setRightChild(n3);
n2.setLeftChild(n4);
n2.setRightChild(n5);
n3.setRightChild(n6);
n4.setRightChild(n7);
n7.setLeftChild(n8);
BTreeTraverse.inOrderTraverseByIterative(n1);
}
}
运行结果:
二叉树的后序遍历
递归法
思路：
后续遍历节点访问顺序： LRD，思路可以参考先序、中序遍历~
代码实现：
public static void postOrderTraverseByRecursion(BinaryTree root) {
// 使用递归方法后序遍历二叉树
// 递归出口
if (root == null)
return;
// 递归访问左子节点
postOrderTraverseByRecursion(root.getLeftChild());
// 递归访问右子节点
postOrderTraverseByRecursion(root.getRightChild());
// 访问根节点
System.out.print(root.getValue() + " ");
}
图解:
测试代码：
package com.xinpaninjava.btree;
public class BinaryTreeCountNodesTest {
public static void main(String[] args) {
BinaryTree n1 = new BinaryTree(1);
BinaryTree n2 = new BinaryTree(2);
BinaryTree n3 = new BinaryTree(3);
BinaryTree n4 = new BinaryTree(4);
BinaryTree n5 = new BinaryTree(5);
BinaryTree n6 = new BinaryTree(6);
n1.setLeftChild(n2);
n1.setRightChild(n3);
n2.setLeftChild(n4);
n2.setRightChild(n5);
n3.setRightChild(n6);
BTreeTraverse.postOrderTraverseByRecursion(n1);
}
}
树结构:
运行结果：
迭代法
思路：
- 后续遍历对节点的访问顺序是LRD，就在我百思不得其解的时候，我看出了一些破绽
- 它就是先序遍历的倒序版，既然上面我们已经解决了先序遍历的迭代方法，那么我们只需要多弄一个栈，把里面的节点倒过来，不就实现了后序遍历吗? 够给力吗？
- 可能有些人会说，先序遍历是DLR啊，后序遍历是LRD，怎么一样？如果你有这样的疑问，那我只能说你不是真的懂先序遍历
- 先序遍历使用迭代方式实现的时候，不是要把输出当前信息的节点的左右子节点存到栈里面吗?只需要调整左右节点进栈的顺序即可！
图解:
代码实现：
// 使用非递归方式实现二叉树的后序遍历
public static void postOrderTraverseByIterative(BinaryTree root) {
// 首先判断传进来的根节点是否为空，为空空操作
if (root == null)
return;
// 定义两个栈，一个用来实现”DRL"的先序遍历，另外一个栈用来颠倒前面栈的顺序
Stack<BinaryTree> stack = new Stack<BinaryTree>();
Stack<BinaryTree> outStack = new Stack<BinaryTree>();
BinaryTree currentNode = root;
stack.push(currentNode);
while (!stack.isEmpty()) {
// 既然要实现先序遍历，当然是先访问根节点，把先出栈的放到另外一个栈
currentNode = stack.pop();
outStack.push(currentNode);
// 再判断左子节点，不为空入栈1
if (currentNode.getLeftChild() != null)
stack.push(currentNode.getLeftChild());
// 判断右子节点，不为空，入栈1
if (currentNode.getRightChild() != null)
stack.push(currentNode.getRightChild());
}
// 输出outStack栈中的节点
while (!outStack.isEmpty()) {
System.out.print(outStack.pop().getValue() + " ");
}
}
测试代码:
package com.xinpaninjava.btree;
public class BinaryTreeCountNodesTest {
public static void main(String[] args) {
BinaryTree n1 = new BinaryTree(1);
BinaryTree n2 = new BinaryTree(2);
BinaryTree n3 = new BinaryTree(3);
BinaryTree n4 = new BinaryTree(4);
BinaryTree n5 = new BinaryTree(5);
BinaryTree n6 = new BinaryTree(6);
n1.setLeftChild(n2);
n1.setRightChild(n3);
n2.setLeftChild(n4);
n2.setRightChild(n5);
n3.setRightChild(n6);
BTreeTraverse.postOrderTraverseByIterative(n1);
}
}
树结构：
运行结果:
层次查询
非递归方式
思路：
- 按层次遍历，讲的也是节点访问的顺序。
- 这时候使用栈就不合适了，应该使用队列，先访问到的可以先输出
- 先把根节点入队， 当队列不为空的时候，队头节点出队，再判断当前出队节点是否有左右子节点，有就入队
代码实现：
// 非递归方式实现层次遍历
public static void levelTraverseByIterative(BinaryTree root) {
if (root == null)
return;
// 定义一个队列来实现
Queue<BinaryTree> queue = new LinkedList<BinaryTree>();
// 首先把根节点入队
queue.add(root);
BinaryTree currentNode = root;
while (!queue.isEmpty()) {
// 入队再出队
currentNode = queue.remove();
System.out.print(currentNode.getValue() + " ");
// 然后把左右子节点入队
if (currentNode.getLeftChild() != null)
queue.add(currentNode.getLeftChild());
if (currentNode.getRightChild() != null)
queue.add(currentNode.getRightChild());
}
}
图解:
测试代码:
package com.xinpaninjava.btree;
public class BinaryTreeCountNodesTest {
public static void main(String[] args) {
BinaryTree n1 = new BinaryTree(1);
BinaryTree n2 = new BinaryTree(2);
BinaryTree n3 = new BinaryTree(3);
BinaryTree n4 = new BinaryTree(4);
BinaryTree n5 = new BinaryTree(5);
BinaryTree n6 = new BinaryTree(6);
n1.setLeftChild(n2);
n1.setRightChild(n3);
n2.setLeftChild(n4);
n2.setRightChild(n5);
n3.setRightChild(n6);
BTreeTraverse.levelTraverseByIterative(n1);
}
}
树结构:
运行结果:
改进
在上面的运行结果中我们可以看到，虽然是按分层形式访问的，可是结果并没有显示哪些节点属于哪一层，很容易让人觉得好像这些节点都是属于同一层节点，那么怎样实现让函数在算完一层之后输出一个换行呢?
思路：
- 可以借助前面求树深度迭代方法实现的思路，在这里定义两个变量，一个用来记住当前层次的节点数，另外一个用来记录下一层的节点数
- 当记录当前层节点数为0时，输出换行，并且在每次把节点出队和入队，都对这两个变量进行修改，这样就可以实现分层输出！
代码实现：
// 非递归方式实现层次遍历
public static void levelTraverseByIterative(BinaryTree root) {
if (root == null)
return;
// 定义一个队列来实现
Queue<BinaryTree> queue = new LinkedList<BinaryTree>();
// 新定义的两个变量！大家可以通过名字来了解其作用
int currentLevelNodes = 1, nextLevelNodes = 0;
// 首先把根节点入队
queue.add(root);
BinaryTree currentNode = root;
while (!queue.isEmpty()) {
// 入队再出队
currentNode = queue.remove();
// 在出队时，对当前层节点数进行修改！
currentLevelNodes--;
System.out.print(currentNode.getValue() + " ");
// 然后把左右子节点入队
if (currentNode.getLeftChild() != null) {
queue.add(currentNode.getLeftChild());
// 在入队时，对下一层节点数进行修改！
nextLevelNodes++;
}
if (currentNode.getRightChild() != null) {
queue.add(currentNode.getRightChild());
// 在入队时，对下一层节点数进行修改！
nextLevelNodes++;
}
// 当前层节点数为0时，输出换行，并且把“这一行移到下一行”
// 其实就是把下一行的节点数赋值给当前行节点数
if (currentLevelNodes == 0) {
System.out.println();
currentLevelNodes = nextLevelNodes;
}
}
}
测试代码还是一样，即树结构一样。
运行结果：
递归
思路：
- 向要分层的遍历二叉树，首先想能不能用什么容器把节点”分层“存储？
- 定义一个二维数组，每一层存放每一层的节点，最后遍历数组即可得到每一层的节点
- 对于每一个传进来的节点，首先判断其是否为空，为空空操作
- 不为空根据上一次的操作结果，加上当前节点，存入指定的层数
图解:
实现代码:
// 递归方式实现层次遍历
public static void levelTraverseByRecursion(BinaryTree root) {
// 判断根节点是否为空，为空空操作
if (root == null)
return;
// 定义一个双层链表
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
// 使用bfs
recursion(root, 0, list);
// 输出链表
System.out.println(list);
}
/**
* 按层次递归遍历二叉树
*
* @param root
* 当前节点
* @param level
* 层数
* @param list
* 要存储到的容器
*/
private static void recursion(BinaryTree root, int level,
ArrayList<ArrayList<Integer>> list) {
// 当前节点为空，空操作
if (root == null)
return;
// 若当前的层数大于等于链表的“层数”，那么为链表“加层”
if (level >= list.size()) {
list.add(new ArrayList<Integer>());
}
// 把当前节点存到指定层数中
list.get(level).add(root.getValue());
// 递归把左子节点对应的树存入链表
recursion(root.getLeftChild(), level + 1, list);
// 递归把右子节点对应的树存入链表
recursion(root.getRightChild(), level + 1, list);
}
测试代码:
package com.xinpaninjava.btree;
public class BinaryTreeCountNodesTest {
public static void main(String[] args) {
BinaryTree n1 = new BinaryTree(1);
BinaryTree n2 = new BinaryTree(2);
BinaryTree n3 = new BinaryTree(3);
BinaryTree n4 = new BinaryTree(4);
BinaryTree n5 = new BinaryTree(5);
BinaryTree n6 = new BinaryTree(6);
n1.setLeftChild(n2);
n1.setRightChild(n3);
n2.setLeftChild(n4);
n2.setRightChild(n5);
n3.setRightChild(n6);
BTreeTraverse.levelTraverseByRecursion(n1);
}
}
树结构:
运行结果
【全文完】
参考资料：
Pre-Order Traversal of Binary Tree (Iterative)
Inorder Binary Tree Traversal (Iteratively)
Print a Binary Tree in Post Order Traversal (Iterative using Stack)
二叉树后序遍历的非递归实现
二叉树前序、中序、后序遍历非递归写法的透彻解析
数据结构（C语言版）（第2版）-5.3.1遍历二叉树
郝斌数据结构-第67-72个视频，提取密码:hvzr