二叉树的层序遍历及判断一个二叉树是否为完全二叉树

怼烎@ 2022-11-14 00:50 111阅读 0赞

### 层序遍历 ###

*  层序遍历
 *   *  思路：
     *  代码实现：
 *  判断一个二叉树是否为完全二叉树

# 层序遍历 #

我们知道二叉树的遍历分为深度优先遍历和广度优先遍历  
深度优先遍历分为先序遍历、中序遍历、后序遍历  
广度优先遍历 为 层序遍历

顾名思义，层序遍历为一层一层遍历，从上至下，从左至右，如下图：层序遍历结果为：a b c d e f g  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]

## 思路： ##

如何进行二叉树的层序遍历呢？我们首先拿到根节点，然后访问左结点，访问右节点…  
我们可以将结点放在队列中，然后分别把左节点右节点放进队列，最后依次输出可得到层序遍历。

## 代码实现： ##

public class TreeNode { 
        public int val;
        public TreeNode left;
        public TreeNode right;
    
        public TreeNode(int val) { 
            this.val = val;
        }
    
        @Override
        public String toString() { 
            return String.format("TreeNode{%c}", val);
        }
    }

import java.util.LinkedList;
    import java.util.Queue;
      
    public class levelTraversal { 
        public void level(TreeNode root) { 
            if (root == null) { 
                return;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) { 
                TreeNode node = queue.remove();
                System.out.println((char) node.val);
                if (node.left != null) { 
                    queue.add(node.left);
                }
                if (node.right != null) { 
                    queue.add(node.right);
                }
            }
        }
    }

/** * */
    public class Test { 
        public static void main(String[] args) { 
            TreeNode a = new TreeNode('a');
            TreeNode b = new TreeNode('b');
            TreeNode c = new TreeNode('c');
            TreeNode d = new TreeNode('d');
            TreeNode e = new TreeNode('e');
            TreeNode f = new TreeNode('f');
            TreeNode g = new TreeNode('g');
            TreeNode h = new TreeNode('h');
    
            a.left = b; a.right = c;
            b.left = d; b.right = e;
            c.left = f; c.right = g;
            e.right = h;
    
            levelTraversal levelTraversal=new levelTraversal();
            levelTraversal.level(a);
        }
    }

结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 1]

# 判断一个二叉树是否为完全二叉树 #

完全二叉树是由满二叉树而引出的。对于深度为k的，有n个结点的二叉树，当且仅当其没一个节点都与深度为k的满二叉树中编号从1至n的结点对应则是完全二叉树。  
满二叉树是一种特殊的完全二叉树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 2]  
我们可以将二叉树层序遍历出来（包括空节点）  
完全二叉树结果：abcdefg\#\#\#\#\#  
非完全二叉树结果：abcd\#\#ef\#\#\#  
当队列中遇到null时，如果后面都是null，那么就是完全二叉树，否则不是完全二叉树；

题目链接：  
[二叉树的完全性检验][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 3]

class Solution { 
        public boolean isCompleteTree(TreeNode root) { 
            if (root == null) { 
                return true;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            boolean flag = false;
            while (!queue.isEmpty()) { 
                TreeNode node = queue.remove();
                if (node == null) { 
                    flag = true;
                    continue;
                }
                if (flag) { 
                    return false;
                }
                queue.add(node.left);
                queue.add(node.right);
    
            }
            return true;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]: /images/20221022/3dddd913629b4e358517ccb02936b7ba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210327212509683.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210327212840123.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ==,size_16,color_FFFFFF,t_70
[Link 1]: https://leetcode-cn.com/problems/check-completeness-of-a-binary-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20210327221624811.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ==,size_16,color_FFFFFF,t_70