二分搜索树的遍历

偏执的太偏执、 2021-09-23 21:52 399阅读 0赞

# 1、前序遍历 中->左->右 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70][]

## 示例代码: ##

//二分搜索树的前序遍历
        public void preOrder() { 
            preOrder(root);
        }
    
        //前序遍历以node为根的二分搜索树,递归算法
        private void preOrder(Node node) { 
            if (node == null) { 
                return;
            }
            System.out.println(node.e);
            preOrder(node.left);
            preOrder(node.right);
        }
    
        @Override
        public String toString() { 
            StringBuffer res = new StringBuffer();
            generateBSTString(root, 0, res);
            return res.toString();
        }
    
        private void generateBSTString(Node node, int depth, StringBuffer res) { 
            if (node == null) { 
                res.append(generateDepthString(depth) + "null\n");
                return;
            }
            res.append(generateDepthString(depth) + node.e + "\n");
            generateBSTString(node.left, depth + 1, res);
            generateBSTString(node.right, depth + 1, res);
        }
    
        private String generateDepthString(int depth) { 
            StringBuffer res = new StringBuffer();
            for (int i = 0; i < depth; i++) { 
                res.append("--");
            }
            return res.toString();
        }

# 2、中序遍历 左->中->右 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 1]

## 示例代码: ##

//二分搜索树的中序遍历
        public void inOrder() { 
            inOrder(root);
        }
    
        //中序遍历以node为根的二分搜索树,递归算法
        private void inOrder(Node node) { 
            if (node == null) { 
                return;
            }
            inOrder(node.left);
            System.out.println(node.e);
            inOrder(node.right);
        }

# 3、后序遍历 左->右->中 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 2]

## 示例代码: ##

//二分搜索树的后序遍历
        public void postOrder() { 
            postOrder(root);
        }
    
        //后序遍历以node为根的二分搜索树,递归算法
        private void postOrder(Node node) { 
            if (node == null) { 
                return;
            }
            postOrder(node.left);
            postOrder(node.right);
            System.out.println(node.e);
        }

# 深入理解二分搜索树的遍历 #

**注意紫色点和蓝色点的过程，其实我们对每一个节点都有三次的访问机会。分别是在遍历左子树之前、在遍历左子树之后会回到这个节点、之后才回去遍历右子树、遍历完右子树之后又来到了这个节点。**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 6]

# 前序遍历的非递归写法 (借助栈) #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 7]  
**代码：**

//二分搜索树前序遍历的非递归实现
        public void preOrderNR() { 
            Stack<Node> stack = new Stack<Node>();
            stack.push(root);
            while (!stack.isEmpty()) { 
                Node cur = stack.pop();
                System.out.println(cur.e);
                if (cur.right != null) { 
                    stack.push(cur.right);
                }
                if (cur.left != null) { 
                    stack.push(cur.left);
                }
            }
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 8]

# 二分搜索树的层序遍历–>广度优先遍历 #

**代码：**

//二分搜索树的层序遍历
        public void levelOrder() { 
            Queue<Node> q = new LinkedList<Node>();
            q.add(root);
            while (!q.isEmpty()) { 
                Node cur = q.remove();
                System.out.println(cur.e);
                if (cur.left != null) { 
                    q.add(cur.left);
                }
                if (cur.right != null) { 
                    q.add(cur.right);
                }
            }
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 9]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70]: /images/20210923/5a735c0a538a4485936afbbb77652254.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 1]: /images/20210923/53fa0cd704714a10a9112fc43dd5020c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 2]: /images/20210923/9d31c9da1ab64156ae5198b3d0002e99.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 3]: /images/20210923/a0f4e6de7ded44c392dd837c085b58c9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 4]: /images/20210923/5a67c534a8644f6fbe8aca1b3162e754.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 5]: /images/20210923/987e5602e89643358c73db7a8dcb9337.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 6]: /images/20210923/9d21cd828c2549c9b9ca366db5fd35af.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 7]: /images/20210923/d1e57ed7e9da42c0a890b6f6d9644bcf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 8]: /images/20210923/0bcfa40577dd455abeb8354d814539bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 9]: /images/20210923/4bcb1a780874495eb0e998e3891828f1.png