写在前面的话：
- 参考资料：《漫画算法》83页详解二叉树的非递归遍历_z_ryan的博客-CSDN博客_非递归遍历二叉树
- 本章内容：非递归遍历与层次遍历
- IDE：IntelliJ IDEA 2021.2.1
- JDK：Java8?
目录
?项目结构：
?代码构建的二叉树：
?1.栈
二叉树的非递归需要用到栈
ArrayStack.java?
package ex03;
/*
栈
*/
import java.util.NoSuchElementException;
public class ArrayStack<E> {
private BinaryTree.TreeNode[] array;
private int top;//栈顶
/**
* 创建数组栈
*/
public ArrayStack(){
this(10);
}
/**
* 创建数组栈,并指定栈的大小
* @param capacity 栈的容量
*/
public ArrayStack(int capacity){
if(capacity > 0){
array = new BinaryTree.TreeNode[capacity];
}else {
throw new IllegalArgumentException("参数capacity错误！capacity的值("+capacity+")小于或等于0");
}
}
/**
* 入栈
* @param node 入栈节点
*/
public void push(BinaryTree.TreeNode node){
//判断栈是否满了
if(top >= array.length){
expandCapacity();
}
//入栈
array[top] = node;
//栈顶加一
top++;
}
/**
* 出栈
*/
public BinaryTree.TreeNode pop(){
if(top == 0){
//栈为空
throw new NoSuchElementException("栈中没有元素,获取失败！");
}
return array[--top];//弹出栈顶数据
}
/**
* 判断栈是否为空
* @return true:栈空 false:栈不为空
*/
public boolean isEmpty(){
if(top == 0){
return true;
}
return false;
}
/**
* 数组栈扩容
*/
private void expandCapacity(){
BinaryTree.TreeNode[] newArray = new BinaryTree.TreeNode[array.length * 2];
if(newArray.length > 100){
throw new IllegalArgumentException("不准栈的深度超过100");
}
System.arraycopy(array,0,newArray,0,top);
array = newArray;
}
}
2.队列?
?二叉树的层次遍历需要用到队列
?Queue.java
package ex03;
import java.util.NoSuchElementException;
/*
队列(层次遍历需要)
*/
public class Queue<E> {
private BinaryTree.TreeNode[] array;
private int font;//队头
private int rear;//队尾
public Queue(){
this(10);
}
public Queue(int capacity){
array = new BinaryTree.TreeNode[capacity];
}
//判断是否为空
public boolean isEmpty(){
if(font == rear){
return true;//队列为空
}
return false;
}
//入队
public void enQueue(BinaryTree.TreeNode node){
//判断队列是否队满
if((rear + 1) % array.length == font){
expandCapacity();
}
array[rear] = node;//在队尾加上节点
rear = (rear + 1)%array.length;//添加完数据,队尾往后移
}
//出队
public BinaryTree.TreeNode outQueue(){
//判断队列是否为空
if(font == rear){
throw new NoSuchElementException("队列为空！无法获取数据！");
}
BinaryTree.TreeNode outElement = array[font];
font = (font + 1)%array.length;
return outElement;
}
public void expandCapacity(){
BinaryTree.TreeNode[] newArray = new BinaryTree.TreeNode[array.length * 2];
if(newArray.length > 100){
throw new IllegalArgumentException("不准栈的深度超过100");
}
//将原数组复制到新数组里
for(int i = 0,n = 0;i < array.length;i++){//队尾可能在数组的中间
if(i == rear){//因为队尾要留一空
continue;
}
newArray[n++] = array[i];
}
array = newArray;
}
}
3.二叉树的构建
BinaryTree.java
package ex03;
import java.util.LinkedList;
/*
二叉树的遍历(非递归)
采用栈来实现遍历
*/
public class BinaryTree<E> {
/*
二叉树节点
*/
public static class TreeNode<E> {
E data;//节点保存的数据
TreeNode leftChild;//左孩子
TreeNode rightChild;//右孩子
TreeNode(E data) {
this.data = data;
}
}
/**
* 创建一颗二叉树
*
* @param list 输入序列
* @return 返回一棵树
*/
public <E> TreeNode createBinaryTree(LinkedList<E> list) {
//创建节点
TreeNode<E> treeNode = null;
//判断输入序列list是否等于null,或者输入序列list为空
if (list == null || list.isEmpty()) {
return null;
}
//获取list第一个数据
E data = list.removeFirst();
//当获取到的是null时,跳过下面语句
if (data != null) {
//创建一颗二叉树有很多种方式
// 1.前序遍历创建二叉树
// 2.中序遍历创建二叉树
// 3.后序遍历创建二叉树
// ...
//这里采用前序遍历的方式创建二叉树
treeNode = new TreeNode<>(data);
treeNode.leftChild = createBinaryTree(list);
treeNode.rightChild = createBinaryTree(list);
}
return treeNode;
}
/**
* 非递归前序遍历
*
* @param root 根节点
*/
public void formerSequenceTraversal(TreeNode<E> root) {
//创建一个栈
ArrayStack<E> stack = new ArrayStack<>(20);
TreeNode<E> treeNode = root;
//栈不为空 ==> 没有遍历完
while (!stack.isEmpty() || treeNode != null) {
//一直判断左孩子
while (treeNode != null) {
//打印输出节点
System.out.print(treeNode.data + " ");
//将节点入栈
stack.push(treeNode);
//遍历左孩子
treeNode = treeNode.leftChild;
}
//当左孩子为null时,弹出数据,并插入右孩子
if (!stack.isEmpty()) {
//当栈不为空时
treeNode = stack.pop();//将没有左孩子的节点弹出去
//找右孩子
treeNode = treeNode.rightChild;
}
}
}
/**
* 中序遍历:左根右
*
* @param root 根节点
*/
public void inTheSequenceTraversal(TreeNode<E> root) {
ArrayStack<E> stack = new ArrayStack<>(20);
TreeNode<E> treeNode = root;
//判断栈是否为空,节点是否为null
while (!stack.isEmpty() || treeNode != null) {
//一直遍历左孩子,直至到叶子节点
while (treeNode != null) {
//将节点入栈
stack.push(treeNode);
//遍历左孩子
treeNode = treeNode.leftChild;
}
if (!stack.isEmpty()) {
//当栈不为空
treeNode = stack.pop();//弹出栈顶
System.out.print(treeNode.data + " ");//打印输出数值
treeNode = treeNode.rightChild;//遍历右节点
}
}
}
/**
* 后序遍历:左右根
*
* @param root 根节点
*/
public void afterTheSequenceTraversal(TreeNode<E> root) {
/*
思路：
1.左子树跳过根节点,最后再进行访问
2.右子树无需跳过根节点
*/
//如果root等于null,直接返回
if (root == null) {
return;
}
ArrayStack<E> stack = new ArrayStack<>(20);
TreeNode<E> lastVisit = null;//最近访问
TreeNode<E> treeNode = root;//从根节点开始遍历
//一直判断左孩子
while (treeNode != null) {
stack.push(treeNode);
treeNode = treeNode.leftChild;
}
//栈不为空
while (!stack.isEmpty()) {
treeNode = stack.pop();//返回上一次节点
//判断根节点是否被访问过
if (treeNode.rightChild == null || treeNode.rightChild == lastVisit) {
//根节点无右孩子,或者右孩子已经被访问过,直接输出根节点
System.out.print(treeNode.data + " ");//打印输出根节点
lastVisit = treeNode;//访问过的节点,记录下来
} else {
stack.push(treeNode);//压入栈中,稍后访问
treeNode = treeNode.rightChild;//遍历右孩子【一定有右孩子,否则将进入上面的if判断中】
//一直判断左孩子【这里的循环与上面一样】
while (treeNode != null) {
stack.push(treeNode);
treeNode = treeNode.leftChild;
}
}
}
}
/**
* 层次遍历
* @param root 根节点
*/
public void levelTraversal(TreeNode<E> root) {
if (root == null) {
return;
}
//创建队列
Queue<E> queue = new Queue<>(20);
//创建一个节点
TreeNode<E> treeNode = root;
queue.enQueue(treeNode);
while (!queue.isEmpty()) {
//出队
treeNode = queue.outQueue();
System.out.print(treeNode.data + " ");
//判断左孩子是否为空
if (treeNode.leftChild != null) {
//左孩子入队
queue.enQueue(treeNode.leftChild);
}
//判断右孩子是否为空
if (treeNode.rightChild != null) {
//右孩子入队
queue.enQueue(treeNode.rightChild);
}
}
}
}
4.测试类?
?Test.java
package ex03;
import java.util.Arrays;
import java.util.LinkedList;
public class Test {
public static void main(String[] args) {
//按照前序遍历,填充内容
Integer[] array = new Integer[]{1,2,4,null,null,5,null,null,3,null,6};//这是完全二叉树的线性结构,顺序按照前序遍历来
//将数据添加进list当中
LinkedList<Integer> list = new LinkedList<>(Arrays.asList(array));
BinaryTree<Integer> binaryTree = new BinaryTree<>();
//创建二叉树
BinaryTree.TreeNode root = binaryTree.createBinaryTree(list);
//前序遍历
System.out.println("前序遍历：");
binaryTree.formerSequenceTraversal(root);
//中序遍历
System.out.println("\n中序遍历：");
binaryTree.inTheSequenceTraversal(root);
//后序遍历
System.out.println("\n后序遍历：");
binaryTree.afterTheSequenceTraversal(root);
//层次遍历
System.out.println("\n层次遍历：");
binaryTree.levelTraversal(root);
}
}
测试截图：
5.画图讲解?
代码太多，不好理解？！看下面的图吧！
5.1 前序遍历：
先访问打印输出1，将第一个元素压入栈中，
访问左孩子，打印输出2 ，压入栈中
?访问左孩子，打印输出4，压入栈中。
?
?访问左孩子，判断该节点为空，弹出栈顶元素4
?此时获取弹出的栈顶元素4，访问它的右孩子，也是空，继续弹出栈。
?
?此时获取弹出的栈顶元素2，访问它的右孩子，是5。
打印输出5，并将它压入栈中。
?访问它的左孩子，为空，弹出栈顶元素。
??此时获取弹出的栈顶元素5，访问它的右孩子，是空，弹出栈顶元素。
?此时获取弹出的栈顶元素1，访问它的右孩子，是3。
打印输出3，并将它压入栈中。
??访问它的左孩子，为空，弹出栈顶元素。
??此时获取弹出的栈顶元素3，访问它的右孩子，是6。
打印输出6，并将它压入栈中。
???访问它的左孩子，为空，弹出栈顶元素。
?此时获取弹出的栈顶元素6，访问它的右孩子，是空，此时栈为空，遍历完毕。
根据以上情况，可以判断黄色高亮字 为1 2 4 5 3 6 结果正确！
5.2 中序遍历?
先访问根节点1，压入栈中。
接着访问左孩子，是2，压入栈中。
?接着访问左孩子，是4，压入栈中。
?接着访问左孩子，是空（NULL），弹出栈顶元素4
获取栈顶元素4，打印输出4 ，并访问它的右孩子，为空，继续弹出栈顶元素2。
?获取栈顶元素2 ，打印输出2，访问它的右孩子是5，压入栈中。
?接着访问节点5的左孩子，为空，弹出栈顶元素5
?获取栈顶元素5，打印输出5，并访问它的右孩子为空，弹出栈顶元素1
?获取栈顶元素，打印输出1，并访问它的右孩子为3，压入栈中。
?接着访问节点3的左孩子，为空，弹出栈顶元素3.
?获取栈顶元素3，打印输出3，并访问它的右孩子，是6，压入栈中。
?接着访问节点6的左孩子，为空，弹出栈顶元素6.
获取弹出的栈顶元素6，打印输出6，并访问它的右孩子，为空，遍历完毕！?
根据以上情况，可以判断黄色高亮字 为4 2 5 1 3 6?结果正确！
5.3 后序遍历?
后序遍历，相比较前两种而言，它需要判断访问的上一个节点是左子树还是右子树的，故相对而言比较难。根据代码可以知道我们把TreeNode<E> lastVisit = null;//最近访问 添加这句代码。
?首先访问根节点1，压入栈中。
?接着访问节点1的左孩子，为2，压入栈中。
?接着访问节点2的左孩子，为4，压入栈中。
?接着访问节点4的左孩子，为空，弹出栈顶元素4.
?获取出栈元素4，并判断右孩子是否为空，为空！打印输出4，并将此节点（元素4）设定为lastVisit(已经被访问过的节点)
继续弹出栈顶元素2
?
?这时，判断其节点有右孩子，且右孩子并没有被访问过，这时重新将元素2入栈，并访问元素2的右孩子，为5，将它压入栈中。（与上面两种遍历方式不同，需格外注意！）
?访问节点5的左孩子，为空，弹出栈顶元素5.
?获取出栈元素5，并判断右孩子是否为空，为空！打印输出5，并将此节点（元素5）设定为lastVisit(已经被访问过的节点)
继续弹出栈顶元素2
?这时，判断其节点有右孩子，且右孩子（元素5）已经被访问过，打印输出2，并将此节点（元素2）设定为lastVisit(已经被访问过的节点)
继续弹出栈顶元素1
??这时，判断其节点有右孩子，且右孩子并没有被访问过，这时重新将元素1入栈，并访问元素1的右孩子，为3，将它压入栈中。
??访问节点3的左孩子，为空，弹出栈顶元素3.
?这时，判断其节点有右孩子，且右孩子并没有被访问过，这时重新将元素3入栈，并访问元素3的右孩子，为6，将它压入栈中。
??访问节点6的左孩子，为空，弹出栈顶元素6?
??获取出栈元素6，并判断右孩子是否为空，为空！打印输出6，并将此节点（元素6）设定为lastVisit(已经被访问过的节点)
继续弹出栈顶元素3
??这时，判断其节点有右孩子，且右孩子（元素6）已经被访问过，打印输出3，并将此节点（元素3）设定为lastVisit(已经被访问过的节点)
继续弹出栈顶元素1
?这时，判断其节点有右孩子，且右孩子（元素3）已经被访问过，打印输出1，并将此节点（元素1）设定为lastVisit(已经被访问过的节点)
此时栈为空，退出循环，遍历结束！
根据以上情况，可以判断黄色高亮字 为4 5 2 6 3 1?结果正确！
5.4 层次遍历
?层次遍历，不同于前序、中序、后序遍历，它将用到另外一个工具——队列！
?首先，将根节点1入队。
将队头（节点1）出队，打印输出1。
?并访问节点1的左孩子，为2，将它入队。
?接着访问节点1的右孩子，为3，入队。
?节点1的左右孩子都访问完了，进行出队，将队头（节点2）出队。
?获取出队元素2，打印输出2。并访问节点2的左孩子（要存在），是4，入队。
访问节点2的左孩子后，再访问节点2的右孩子（要存在），是5，入队。
?
?对节点2的左右孩子，都访问完后，接着进行出队，对队头（节点3）进行出队。
??获取出队元素3，打印输出3。并访问节点3的左孩子（要存在），为空，左孩子不存在！
访问节点3的右孩子（要存在），为6，入队。
?节点3的左右孩子都访问完，进行出队，将队头（节点4）出队。
因为节点4、节点5、节点6都没有左右孩子，在这里直接将一个个地出队。
???获取出队元素4，打印输出4。
????获取出队元素5，打印输出5。
获取出队元素5，打印输出5。
此时队列为空，遍历完毕！
根据以上情况，可以判断黄色高亮字 为1 2 3 4 5 6?结果正确！
完?
