二叉树遍历的几种常见方法

雨点打透心脏的1/2处 2022-11-20 08:20 88阅读 0赞

# 二叉树的遍历方法 #

**一.二叉树分类：**

*  完全二叉树
 *  满二叉树
 *  扩充二叉树
 *  平衡二叉树

**二.二叉树的四种遍历方式：**

*  前序遍历（先根，再左，最后右）
 *  中序遍历（先左，再根，最后右）
 *  后序遍历（先左，再右，最后根）
 *  层次遍历（说不清）

## 1.递归遍历 ##

#### （1）前序遍历 ####

遍历方法：先根节点，再左节点，最后右节点。

![在这里图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h4eHh4eHh4MDA3NzIyOTk_size_16_color_FFFFFF_t_70_pic_center]  
实现代码：

/*声明结点TreeNode类*/
    public static void preOrderTraveral(TreeNode node){
        
        if(node == null){
        
             return;
         }
         System.out.print(node.data+" ");
         preOrderTraveral(node.leftChild);
         preOrderTraveral(node.rightChild);
    }
    
    /*再来创建一颗二叉树：*/
    public static TreeNode createBinaryTree(LinkedList<Integer> list){
        
        TreeNode node = null;
        if(list == null || list.isEmpty()){
        
            return null;
        }
        Integer data = list.removeFirst();
        if(data!=null){
        
            node = new TreeNode(data);
            node.leftChild = createBinaryTree(list);
            node.rightChild = createBinaryTree(list);
        }
        return node;
    }

#### （2）中序遍历 ####

先左节点，再根节点，最后右节点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h4eHh4eHh4MDA3NzIyOTk_size_16_color_FFFFFF_t_70_pic_center 1]  
实现代码：

public static void inOrderTraveral(TreeNode node){
        
        if(node == null){
        
            return;
        }
        inOrderTraveral(node.leftChild);
        System.out.print(node.data+" ");
        inOrderTraveral(node.rightChild);
    }

#### （3）后序遍历 ####

先左节点，再右节点，最后根节点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h4eHh4eHh4MDA3NzIyOTk_size_16_color_FFFFFF_t_70_pic_center 2]  
实现代码：

public static void postOrderTraveral(TreeNode node){
        
        if(node == null){
        
            return;
        }
        postOrderTraveral(node.leftChild);
        postOrderTraveral(node.rightChild);
        System.out.print(node.data+" ");
    }

**答案：**

*  前序遍历结果为：ABDFECGHI；
 *  中序遍历结果为：DBEFAGHCI；
 *  后序遍历结果为：DEFBHGICA

## 2.非递归遍历： ##

#### （1）前序遍历 ####

public static void preOrderTraveralWithStack(TreeNode node){
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode treeNode = node;
        while(treeNode!=null || !stack.isEmpty()){
        
            //迭代访问节点的左孩子，并入栈
            while(treeNode != null){
        
                System.out.print(treeNode.data+" ");
                stack.push(treeNode);
                treeNode = treeNode.leftChild;
            }
            //如果节点没有左孩子，则弹出栈顶节点，访问节点右孩子
            if(!stack.isEmpty()){
        
                treeNode = stack.pop();
                treeNode = treeNode.rightChild;
            }
        }
    }

#### （2）中序遍历 ####

public static void inOrderTraveralWithStack(TreeNode node){
        
       Stack<TreeNode> stack = new Stack<TreeNode>();
       TreeNode treeNode = node;
       while(treeNode!=null || !stack.isEmpty()){
        
           while(treeNode != null){
        
               stack.push(treeNode);
               treeNode = treeNode.leftChild;
           }
           if(!stack.isEmpty()){
        
               treeNode = stack.pop();
               System.out.print(treeNode.data+" ");
               treeNode = treeNode.rightChild;
           }
    
       }
    }

#### （3）后序遍历 ####

public static void postOrderTraveralWithStack(TreeNode node){
        
       Stack<TreeNode> stack = new Stack<TreeNode>();
       TreeNode treeNode = node;
       TreeNode lastVisit = null;   //标记每次遍历最后一次访问的节点
       //节点不为空，结点入栈，并且指向下一个左孩子
       while(treeNode!=null || !stack.isEmpty()){
        
           while(treeNode!=null){
        
               stack.push(treeNode);
               treeNode = treeNode.leftChild;
           }
           //栈不为空
           if(!stack.isEmpty()){
        
               //出栈
               treeNode = stack.pop();
               /**
                * 这块就是判断treeNode是否有右孩子，
                * 如果没有输出treeNode.data，让lastVisit指向treeNode，并让treeNode为空
                * 如果有右孩子，将当前节点继续入栈，treeNode指向它的右孩子,继续重复循环
                */
               if(treeNode.rightChild == null || treeNode.rightChild == lastVisit) {
        
                   System.out.print(treeNode.data + " ");
                   lastVisit = treeNode;
                   treeNode  = null;
               }else{
        
                   stack.push(treeNode);
                   treeNode = treeNode.rightChild;
               }
    
           }
    
       }
    }

#### 3.层次遍历 ####

public static void levelOrder(TreeNode root){
        
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
        
            root = queue.pop();
            System.out.print(root.data+" ");
            if(root.leftChild!=null) queue.add(root.leftChild);
            if(root.rightChild!=null) queue.add(root.rightChild);
        }
    }

## 三、时间复杂度 ##

*  二叉查找树 ：O(n)
 *  平衡二叉树 ：O(logn)
 *  红黑树 ：Olog(n)

**master公式的使用：计算时间复杂度**  
T(N) = a\*T(N/b) + O(N^d)

1.  log(b,a) > d ->复杂度为O（N^log(b,a)）
2.  log(b,a) = d ->复杂度为O（N^d\*logN）
3.  log(b,a) < d ->复杂度为O（N^d）

**感谢** Du~佛系码农，**原文地址**：

> https://www.cnblogs.com/du001011/p/11229170.html

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h4eHh4eHh4MDA3NzIyOTk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/2cca088093f4475b812c18fba34c93b4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h4eHh4eHh4MDA3NzIyOTk_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201027192216794.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h4eHh4eHh4MDA3NzIyOTk=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h4eHh4eHh4MDA3NzIyOTk_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201027192232935.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h4eHh4eHh4MDA3NzIyOTk=,size_16,color_FFFFFF,t_70#pic_center