二叉树的7种遍历算法

先根递归遍历算法思路：代码实现(java版) 中根递归遍历算法思路：代码实现(java版) 后根递归遍历算法思路：代码实现(java版) 先根非递归遍历算法思路：代码实现(java版) 中根非递归遍历算法思路：代码实现(java版) 后根非递归遍历算法思路：代码实现(java版) 层序遍历算法思路：代码实现(java版)

先根递归遍历算法

思路：

        1.若二叉树为空则退出，否则进行以下步骤         2.访问当前的根节点         3.先根顺序遍历访问左子树         4.先根顺序遍历访问右子树         5.退出

代码实现(java版)

public static void proOrder(Node T) { if (T != null) { // 获取当前树的根结点 System.out.println(T); // 先序遍历左子树 proOrder(T.getLeft()); // 先序遍历右子树 proOrder(T.getRight()); } }

中根递归遍历算法

思路：

        1.若二叉树为空则退出，否则进行以下步骤         2.中根顺序遍历访问左子树         3.访问当前的根节点         4.中根顺序遍历访问右子树         5.退出

代码实现(java版)

public static void inOrder(Node T) { if (T != null) { // 中根顺序遍历左子树 inOrder(T.getLeft()); // 访问当前根节点数据 System.out.println(T); // 中根顺序遍历右子树 inOrder(T.getRight()); } }

后根递归遍历算法

思路：

        1.若二叉树为空则退出，否则进行以下步骤         2.后根顺序遍历访问左子树         3.后根顺序遍历访问右子树         4.访问当前的根节点         5.退出

代码实现(java版)

public static void postOrder(Node T) { if (T != null) { // 后根顺序遍历左子树 postOrder(T.getLeft()); // 后根顺序遍历右子树 postOrder(T.getRight()); // 访问当前根结点 System.out.println(T); } } 任何一个递归算法，我们都可以借助栈将其改造成非递归算法！ 这里我们对以上三个递归算法进行非递归改造，*即不会出现自己调用自己的现象*。

先根非递归遍历算法

思路：

        1.当前结点不为null或栈不空时，判断当前结点是否为空           (1)不为空：访问当前结点，然后将其入栈，并且将当前结点置为其左孩子结点           (2)为空：栈顶结点出栈（但不去访问该节点），然后将当前结点置为出栈结点的右孩子结点         2.直到当前结点为null并且栈空时，遍历结束并退出循环

代码实现(java版)

public static void proOrder2(Node T) { Stack<Node> stack = new Stack<>(); Node cur = T; // 当前结点为null并且栈空时，遍历结束退出循环 while (cur != null || !stack.empty()) { if (cur != null) { System.out.println(cur); stack.push(cur); cur = cur.getLeft(); } else { // 出栈 Node stackTop = stack.pop(); cur = stackTop.getRight(); } } }

中根非递归遍历算法

思路：

        1.当前结点不为null或栈不空时，判断当前结点是否为空           (1)不为空：将其入栈，并且将当前结点置为其左孩子结点           (2)为空：栈顶结点出栈，并去访问出栈的结点，然后将当前结点置为出栈结点的右孩子结点         2.直到当前结点为null并且栈空时，遍历结束并退出循环

代码实现(java版)

public static void inOrder2(Node T) { Stack<Node> stack = new Stack<>(); Node cur = T; // 当前结点为null并且栈空时，遍历结束退出循环 while (cur != null || !stack.empty()) { if (cur != null) { stack.push(cur); cur = cur.getLeft(); } else { // 出栈 Node stackTop = stack.pop(); System.out.println(stackTop); cur = stackTop.getRight(); } } }

后根非递归遍历算法

思路：

        1.当前结点不为null或栈不空时，判断当前结点是否为空           (1)不为空：将其入栈，并且将当前结点置为其左孩子结点           (2)为空：当栈顶元素的右孩子结点为null或者右子树已经遍历过时出栈并输出，否则将当前结点置为栈顶结点的右孩子结点         2.直到当前结点为null并且栈空时，遍历结束并退出循环

代码实现(java版)

public static void postOrder2(Node T) { Stack<Node> stack = new Stack<>(); Node cur = T; Node lastPop = null; // 最近一次出栈的结点 // 当前结点为null并且栈空时，遍历结束退出循环 while (cur != null || !stack.empty()) { if (cur != null) { stack.push(cur); cur = cur.getLeft(); } else { // 当栈顶元素的右孩子结点为null或者右子树已经遍历过时出栈并输出，否则将当前结点置为栈顶结点的右孩子结点 Node stackTop = stack.peek(); if (stackTop.getRight() == null || stackTop.getRight() == lastPop) { lastPop = stackTop; stackTop = stack.pop(); System.out.println(stackTop); } else { cur = stackTop.getRight(); } } } }

层序遍历算法

思路：

        1.创建一个队列，并将根节点排队         2.当队列非空时，从队列里取出一个结点并从队列里删除，然后访问该结点，最后若该节点的左孩子结点非空则排队，右孩子结点非空则排队。         3.当队列为空时，退出循环，遍历结束。

代码实现(java版)

public static void layerOrder(Node T) { // LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用 Queue<Node> queue = new LinkedList<>(); Node cur = T; queue.add(cur); // 当队列为空时退出循环 while (!queue.isEmpty()) { // 取出并删除队列头部元素 Node poll = queue.poll(); System.out.println(poll); // 当左孩子结点非空时排队 if (poll.getLeft() != null) { queue.add(poll.getLeft()); } // 当右孩子结点非空时排队 if (poll.getRight() != null) { queue.add(poll.getRight()); } } }

更多算法知识请关注微信公众号：青云学斋