二叉树之使用栈实现深度优先遍历

╰+攻爆jí腚メ 2022-10-28 15:29 32阅读 0赞

# 数据结构之使用栈实现深度优先遍历 #

# 简介 #

在读书的时候，在看到需要使用递归来处理树或者图的时候，自己的理解力就不够了，总是无法透澈的理解。三年的程序员生活让自己对于编码熟悉了很多，通过在工作中简单的使用了递归来解决一些问题之后，递归渐渐的有了理解，但通过栈来代替递归的使用还是无法理解的很到位，这次也是借着漫画算法这本书，总结一下，希望能加深理解。

昨天刘张宋畅游西湖，天气晴朗，把西湖搬进心理，还在植物园看到了**洗心**的字眼，昨天的经历大抵也是在洗心吧。

不多说其他的事情了，树这种数据结构非常的重要，但也是一种挑战，因为我们都擅长于线性的思维，对于这种树的层次性思维无法很熟练的掌握。但这种结构又非常的重要，没有办法，就只能一点一点的推敲，改造自己的大脑结构来学习树的存储方式、特性和使用。

关于树，尤其是**二叉树**的深度优先遍历已经在之前的博客中阐述过，不再赘述，[传送门][Link 1]，本章主要是阐述一下关于通过栈来取代递归的实现。关于栈的基础知识的理解，可以参考博客，[漫画算法之基础数据结构][Link 2]

# 原理 #

绝大多数可以用递归解决的问题，其实都可以用栈来解决。因为**递归和栈都有回溯的特性**。

以先根遍历为阐述的基础。我们在用先序遍历遍历一棵二叉树的时候，

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70][]

在遍历上述的二叉树时，由于先序遍历，首先我们要jiujiujiujiu 遍历根节点，我们**知道通过根节点可以借助左右孩子查到节点**2和节点3.遍历完节点1，之后就要遍历节点2，但**节点3什么时候遍历，并不知道，当把节点1的左子树全部遍历完场之后，我们就遍历节点1的右子树**，此时**才是节点3被遍历到的时机**。因此，我们要把节点1存储起来，以供后用。以这种方式，把节点1、节点2遍历之后，存储起来，遍历节点4，一样的道理，先存储起来。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 1][]

遍历节点4之后11，由于此时节点4为叶子节点，遍历其左子树结束，要遍历节点4的右子树。但是由于节点4的右子树为空。因此此时需要发生回溯行为，此时在栈中的节点4应该被弹出。获取到此时的根节点2.

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 2][]

由于此时，节点2和节点2的左子树都被访问过了，节点2便没有了保存的必要（**保存是因为访问右子树**）。借助栈的pop操作，弹出节点2.以先序的方式遍历节点5。然后遍历完节点5，继续弹出节点，此时栈中只剩节点1.获取节点1.由于节点1和节点1的左子树均遍历完成 ，因此从栈中弹出节点1，即完成了对左子树和根的遍历。

我们知道深度优先遍历的目标是每次遍历根节点，然后遍历完左子树，再遍历完右子树。但**由于不知道遍历右子树的时机，因此，我们必须保存起来找到右子树的变量，即这里的根节点（1）**，还要就是要深刻的体会，通过递归**来实现深度优先遍历**的实现，我们**先遍历根节点，然后以同样深度优先遍历的方式来遍历左子树，再以同样深度优先遍历的方式来遍历右子树**。通过比较两种方式就可以有理解这种栈实现深度优先遍历的契机。

# 代码实现 #

## 使用栈实现先根遍历 ##

/** * 通过栈先根遍历深度优先二叉树 * * @param root 二叉树的根节点 */
        public static void preOrderTraverseWithStack(Node root) { 
            Stack<Node> stack = new Stack<>();
            Node treeNode = root;
            while (treeNode != null || !stack.isEmpty()) { 
                if (treeNode == null) { 
                    System.out.print("null ");
                }
                while (treeNode != null) { 
                    // 遍历的动作仅在此处
                    System.out.print(treeNode.getData() + " ");
                    stack.push(treeNode);
                    treeNode = treeNode.getLeft();
                    if (treeNode == null) { 
                        System.out.print("null ");
                    }
                }
                if (!stack.isEmpty()) { 
                    Node pop = stack.pop();
                    treeNode = pop.getRight();
                }
                
            }
    
        }

上述代码理解的准确取决于每次循环的treeNode变量值的含义。treeNode在每次循环开始时，指尚未访问过左右孩子的根节点。当第一次循环结束的时候，内层while循环结束，此时treeNode为空，指的是4节点的左子树，接下来的if，会更新treeNode，通过弹出栈顶元素，得到4节点，更新为其右节点，此时的右节点为null。这样进入下一层循环。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 1][]

> 注意，在程序执行的过程中，**null不入栈**。

下一层次循环，treeNode为4的右子，堆栈中有两个元素1、5。由于treeNode为空，直接跳过while循环，进入if，再次弹出栈顶，得到节点2，并更新treeNode为节点2的右子，即元素5。此时进入下一层循环。之后的逻辑就与处理4节点一样了。不再赘述。

使用栈进行深度二叉树遍历完成
    3 2 9 null null 10 null null 8 null 4 null

再次，把先根遍历的递归实现附录如下：

public static void preOrderTraverse(Node root) { 
            if (root == null) { 
                System.out.print("null ");
                return;
            }
    
            // 遍历当前节点
            System.out.print(root.getData() + " ");
            preOrderTraverse(root.left);
            preOrderTraverse(root.right);
        }

以辅助理解。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 5][]

## 使用栈实现后根遍历 ##

public static class PostUtils { 
            Node node;
            private int flag;
    
            public int getFlag() { 
                return flag;
            }
    
            public Node getNode() { 
                return node;
            }
    
            public void setFlag(int flag) { 
                this.flag = flag;
            }
    
            public void setNode(Node node) { 
                this.node = node;
            }
    
            PostUtils() { 
    
            }
    
            public PostUtils(Node node, int flag) { 
                this.node = node;
                this.flag = flag;
            }
        }
     
    	/** * 使用后根遍历，借助栈 * * @param root 二叉树根节点 */
        public static void postOrderTraverseWithStack(Node root) { 
            if (root==null) { 
                return;
            }
            Stack<PostUtils> stack = new Stack<>();
            stack.push(new PostUtils(root, 0));
            while (!stack.isEmpty()) { 
                PostUtils utils = stack.pop();
                if (utils.getFlag() == 0) { 
                    stack.push(new PostUtils(utils.getNode(), 1));
                    if (utils.getNode().getLeft()!=null) { 
                        stack.push(new PostUtils(utils.getNode().getLeft(), 0));
                    } else { 
                        System.out.print("null ");
                    }
                } else if (utils.getFlag() == 1) { 
                    stack.push(new PostUtils(utils.getNode(), 2));
                    if (utils.getNode().getRight() != null) { 
                        stack.push(new PostUtils(utils.getNode().getRight(), 0));
                    } else { 
                        System.out.print("null ");
                    }
                } else if (utils.getFlag() == 2){ 
                    System.out.print(utils.getNode().getData() + " ");
                }
            }
        }

在大有哥数据结构一书中，有关于后根遍历二叉树的算法伪代码。

> 书中的任一节点q都需要进栈3次，出栈3次。第一次出栈是为了遍历节点q的左子树，第二次出栈是为了遍历节点q的右子树，第三次出栈是为了访问节点q。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 6][]

使用栈进行深度二叉树后根遍历
    null null 9 null null 10 2 null null null 4 8 3

> 注意：二叉树的先根，中根和后根遍历三种遍历序列，叶子节点的相对次序是相同的，叶节点都是按照从左到右的次序排列，三种遍历序列间的区别仅仅在于非叶节点的次序以及非叶节点和叶节点的次序有所不同。

# 下载 #

[使用栈实现二叉树深度优先遍历][Link 3]

# 总结 #

最近在工作之余做了一下笔试题，才发现自己的凝练思维做的很差，尤其是算法的编程和实践，这还是由于自己对于基础的数据结构理解的不够深入，无法实现洞察的缘故。平时自己还是应该多写一些经典的高质量的代码来锻炼思维和手指对于编程的敏感性。2020年年度的工作到了今天也就算告一段落了，学到了很多，失去了很多，就这样吧。

本文主要讲述了通过栈这种数据结构来替代递归实现二叉树的深度优先遍历。大家有空还是可以去阅读以下**漫画算法**和数据结构的其他书，把常用的算法和数据结构悉数于心，这样，无论是面试或者工作，一旦能实践自己的所学，碰撞出火花，还是很美妙的体验。

> 2021年2月7日10:58:04于AUX

[Link 1]: https://blog.csdn.net/lk142500/article/details/111776076
[Link 2]: https://blog.csdn.net/lk142500/article/details/111147993
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70]: /images/20221024/228a46d0e4a24baca8bdb5f78ec0314b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 1]: /images/20221024/22565b8bb72d49bfa8989c25692cddf7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 2]: /images/20221024/26c4cd01246d4bb4843700710fed9ad1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 3]: /images/20221024/f2c90f42e796444187b1dcac1b833827.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 4]: /images/20221024/b63153fbafc342c380103830a5d5a8d1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 5]: /images/20221024/d7ae0520c0ae49adb8f1433d23c664aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xrMTQyNTAw_size_16_color_FFFFFF_t_70 6]: /images/20221024/5399811fa958414582a380312fe41185.png
[Link 3]: https://download.csdn.net/download/lk142500/15116988