判断完全二叉树

本是古典何须时尚 2022-04-15 00:52 206阅读 0赞

完全二叉树的定义: 一棵二叉树，除了最后一层之外都是完全填充的，并且最后一层的叶子结点都在左边。

[https://baike.baidu.com/item/%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91/7773232?fr=aladdin][https_baike.baidu.com_item_E5_AE_8C_E5_85_A8_E4_BA_8C_E5_8F_89_E6_A0_91_7773232_fr_aladdin]

百度定义

思路：层序遍历二叉树

如果一个结点，左右孩子都不为空，则pop该节点，将其左右孩子入队列

如果一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树

如果一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空：：：：：则该节点之后的队列中的结点都为叶子节点；该树才是完全二叉树，否则返回false。

非完全二叉树的例子（对应方法的正确性和必要性）：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 1][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 2][]

下面写代码：

定义结点：

public static class Node {
    		public int value;
    		public Node left;
    		public Node right;
    
    		public Node(int data) {
    			this.value = data;
    		}
    	}

方法：

public static boolean isCBT(Node head) {
    		if (head == null) {
    			return true;
    		}
    		Queue<Node> queue = new LinkedList<Node>();
    		boolean leaf = false;
    		Node l = null;
    		Node r = null;
    		queue.offer(head);
    		while (!queue.isEmpty()) {
    			head = queue.poll();
    			l = head.left;
    			r = head.right;
    			if ((leaf && (l != null || r != null)) || (l == null && r != null)) {
    				return false;//当前结点不是叶子结点且之前结点有叶子结点 || 当前结点有右孩子无左孩子
    			}
    			if (l != null) {
    				queue.offer(l);
    			}
    			if (r != null) {
    				queue.offer(r);
    			} else {
    				leaf = true;//无孩子即为叶子结点
    			}
    		}
    		return true;
    	}

[https_baike.baidu.com_item_E5_AE_8C_E5_85_A8_E4_BA_8C_E5_8F_89_E6_A0_91_7773232_fr_aladdin]: https://baike.baidu.com/item/%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91/7773232?fr=aladdin
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20181119174422675.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20181119174444271.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 2]: /images/20220415/ce52164d6e72483984a161198cf43f5f.png