二叉树的遍历方式是最基本，也是最重要的一类题目，我们将从「前序」、「中序」、「后序」、「层序」四种遍历方式出发，总结他们的递归和迭代解法。

一、二叉树定义
      二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。简单来说，就是一个包含节点，以及它的左右孩子的一种数据结构

假设二叉树的节点定义如下

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode() {
    }

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

二、层序遍历

层序遍历比较简单，按照从上到下，从左到右的顺序逐次遍历。此处借用队列的先入先出特性来实现，具体代码如下

public static void levelTraverse(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();

        //初始化时把root放入队列
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();

            //打印节点的值
            System.out.print(node.val + " ");

            //队列是先入先出，所以此处先遍历左节点
            if (node.left != null) {
                queue.offer(node.left);
            }

            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

三、前序遍历（根节点，左子树，右子树）

1、递归实现：二叉树遍历的递归形式比较容易实现，直接按照根节点，左子树，右子树的顺序 逐次遍历即可

private static void preOrderTraversal0(TreeNode root) {
        if (root == null) {
            return;
        }

        //打印根节点
        System.out.print(root.val + " ");

        //打印左节点
        preOrderTraversal0(root.left);

        //打印右节点
        preOrderTraversal0(root.right);
    }

2、迭代实现

2.1 迭代解法一

过程如下：

• 初始化栈，并将根节点入栈；

• 当栈不为空时：
  弹出栈顶元素 node，并将值添加到结果中；
  如果 node 的右子树非空，将右子树入栈；
  如果 node 的左子树非空，将左子树入栈；
  由于栈是“先进后出”的顺序，所以入栈时先将右子树入栈，这样使得前序遍历结果为 “根->左->右”的顺序。

经过上面图的讲解，代码就比较简单，代码如下：

private static void preOrderTraversal1(TreeNode root) {
        if (null == root) {
            return;
        }

        //定义一个栈方便后续遍历
        Stack<TreeNode> stack = new Stack<>();

        //初始化
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();

            //每一次出栈都打印节点的值
            System.out.print(node.val + " ");

            //栈是先进后出的，所以先处理右子树入栈，再左子树入栈
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

2.2 迭代解法二

（1）思路稍有不同，先定义一个节点cur指向root节点，先将cur节点和所有的左孩子入栈同时打印出cur节点的值，直至 cur 为空，用一个 while 循环实现。

（2）随后出栈一个节点，定义为node，执行 cur = node.right，随后继续执行 操作（1）

经过上面分析，代码中的（1）和（2）分别对应上述的描述，代码如下：

private static void preOrderTraversal2(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        //定义一个cur指向root
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            //（1）只要cur！=null，则打印值，同时cur入栈，同时设置cur = cur.left
            while (cur != null) {
                System.out.print(cur.val + " ");
                stack.push(cur);
                cur = cur.left;
            }

            //（2）如果cur == null,则出栈一个节点，同时设置cur = node.right,同时继续执行（1）
            TreeNode node = stack.pop();
            cur = node.right;
        }
    }

四、中序遍历（左子树，根节点，右子树）

1、递归实现：二叉树遍历的递归形式比较容易实现，直接按照（左子树，根节点，右子树）的顺序 逐次遍历即可

//中序遍历
    private static void inOrderTraversal0(TreeNode root) {
        if (root == null) {
            return;
        }

        //打印左节点
        inOrderTraversal0(root.left);

        //打印根节点
        System.out.print(root.val + " ");

        //打印右节点
        inOrderTraversal0(root.right);
    }

2、迭代解法：（左子树，根节点，右子树）

（1）与前序遍历的逻辑差不多，前序遍历是入栈的时候打印值，但是中序遍历是先处理左节点，再处理根节点，最后遍历右节点，所以遍历时不打印值，出栈时打印值，先定义一个节点cur指向root节点，先将cur节点和所有的左孩子入栈 直至 cur 为空，用一个 while 循环实现。

（2）随后出栈一个节点，定义为node，打印节点的值，执行 cur = node.right，随后继续执行 操作（1）

经过上面处理后 root 节点的左子树处理完毕，接下来继续处理右子树，也是重复的过程，经过上面分析，代码如下：

private static void inOrderTraversal1(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || cur != null) {
            //（1）如果cur不等于空，一直入栈，同时执行cur = cur.left,目的是找到最左节点
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            //(2)如果cur为空，则出栈一个元素，同时打印值，接下来处理右子树，右子树也是调用（1）同步处理
            TreeNode node = stack.pop();
            System.out.print(node.val + " ");
            cur = node.right;
        }
    }

五、后续遍历（左子树，右子树，根节点）

1、递归实现：二叉树遍历的递归形式比较容易实现，直接按照（左子树，右子树，根节点）的顺序 逐次遍历即可

private static void postOrderTraversal0(TreeNode root) {
        if (root == null) {
            return;
        }

        //打印左节点
        postOrderTraversal0(root.left);

        //打印右节点
        postOrderTraversal0(root.right);

        //打印根节点
        System.out.print(root.val + " ");

    }

2、迭代实现：（二叉树的后续遍历，先左子树，右子树，最后根结点），可以定义两个辅助栈，一个栈用于辅助遍历，一个栈用于存放结果，从root开始遍历时先遍历到跟结点，但是根节点又需要最后输出，所以可以借助栈的（先进后出的）特性实现先进入的节点最后输出

经过上面的图解代码如下：

public static void postOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack1 = new Stack<TreeNode>();

        //起始时root入栈
        stack1.push(root);

        //定义一个result栈
        Stack<TreeNode> result = new Stack<TreeNode>();
        while (!stack1.isEmpty()) {
            TreeNode node = stack1.pop();
            result.push(node);
            //先左节点入栈
            if (node.left != null) {
                stack1.push(node.left);
            }
            //再右节点入栈
            if (node.right != null) {
                stack1.push(node.right);
            }
        }

        //最后result栈中依次出栈即为结果
        while (!result.isEmpty()) {
            System.out.print(result.pop().val + " ");
        }
    }

上面仅记录个人的理解。有错误麻烦指正，感谢。

二叉树遍历共有四种方法，分别是前序遍历、中序遍历、后序遍历和层次遍历。

前序遍历： 父节点——左孩子——右孩子

中序遍历：左孩子——父节点——右孩子

后序遍历：左孩子——右孩子——父节点

层次遍历：利用队列解决，父节点出队，左右孩子进队

#二叉树遍历
#建立二叉树
from collections import deque
class Tree():
    def __init__(self,data):
        self.data=data
        self.lchild=None
        self.rchild=None

a=Tree("A")
b=Tree("B")
c=Tree("C")
d=Tree("D")
e=Tree("E")
f=Tree("F")
g=Tree("G")

e.lchild=a
e.rchild=g
a.rchild=c
c.lchild=b
c.rchild=d
g.rchild=f

#第一种方法：前序遍历
def pre_read(root):
    if root:
        print(root.data,end=' ')
        pre_read(root.lchild)
        pre_read(root.rchild)
print("1.前序遍历")
pre_read(e)
##第二种方法：中序遍历
def mid_read(root):
    if root:
        mid_read(root.lchild)
        print(root.data,end=' ')
        mid_read(root.rchild)
print("\n2.中序遍历")
mid_read(e)
#第三种方法：后序遍历
def back_read(root):
    if root:
        back_read(root.lchild)
        back_read(root.rchild)
        print(root.data,end=' ')
print("\n3.后序遍历")
back_read(e)
##第四种方法：层次遍历
##利用队列解决，父节点出队，左右孩子进队】
def cengci_read(root):
    queue=deque()
    if root:
        queue.append(root)
        while len(queue)>0:
            node=queue.popleft()
            print(node.data,end=' ')
            if node.lchild:
                queue.append(node.lchild)
            if node.rchild:
                queue.append(node.rchild)
print("\n层次遍历")
cengci_read(e)

二叉树遍历

简介：

本文主要涉及二叉树的先中后序列遍历

文章并未涉及代码，仅仅提供思路
reference:
学堂在线-数据结构

引言：

在学习链表和数组这两种线性的数据结构的时候，元素之间的次序是十分容易看出的，毕竟元素的位置就是排着队的，自带次序关系，如果想要遍历整个数据结构，无非就是选择倒着遍历还是正着遍历。

但是在学习二叉树这种半线性结构的时候，也想要遍历整棵树，可是树没有数组、链表这么天然的次序关系，所以需要人为的定义次序关系，即先中后序（VLR，LVR，LRV），这一个过程本质上就是将树的半线性结构转换成线性结构，以方便后继通过选择不同的遍历二叉树的方式设计常用的算法框架。

1. 节点本身记作V
2. 左孩子记作L
3. 右孩子记作R

根据节点V在其中的优先级可得到三种不同访问优先级的遍历方式（左孩子优先级永远高于右孩子）

1. 先序遍历：右孩子 < 左孩子 < 节点本身
2. 中序遍历：右孩子 < 节点本身 < 左孩子
3. 后序遍历：节点本身 < 右孩子 < 左孩子

其实这里可以看出：

1. 如果是先序遍历，那么节点本身的优先级最高
2. 如果是中序遍历，那么节点本身的优先级第二
3. 如果是后序遍历，那么节点本身的优先级最低

这是一棵只有三个节点的二叉树，三种序列如下：

而对于任意一个树节点，选择先中后序中的任意一种遍历方式，就等于将这个树节点和它的左右孩子的顺序给出

下面举例说明，这是一颗二叉树。由整体思维可以将这个二叉树看成三个大的结点。

即蓝红紫结点，按照我们人为规定的次序，先序，中序，后序整体的进行排序

这个时候整体上就将一棵二叉树排好序了。

那么现在需要局部的排序。

局部的排序也需要按照实现人为规定的次序。

由于蓝色结点只有一个元素，所以前中后序都只有他自己一个，就不必排序

所以下面只需要看红色和紫色。

红色子树局部排序：

紫色子树局部排序：

最后将局部排序结果和相同顺序的整体结果组合。

先序遍历：

中序遍历：

后序遍历：

经过我们人为的规定二叉树结点之间的关系后，二叉树就可以从一个半线性结构转化为线性结构，从而可以遍历整棵树。