二叉树的完全性判断

概述

完全二叉树是一种特殊的二叉树，它的定义与满二叉树有一定的差异。满二叉树要求每层的节点同时拥有左右子树，而完全二叉树则允许最后一层有部分节点缺少子树。具体而言，当树的高度为h时，第h层可能存在叶子节点，但这些叶子节点的左子树必须为空。如果最后一层部分节点缺少左子树，而右子树完全不存在，则树仍然可以是完全二叉树。

这两种树的主要区别在于它们的结构特征。满二叉树的每一层都满员，而完全二叉树则要求除了最后一层外，其他所有层必须满员。非完全二叉树则完全不满足这些条件，可能存在中间层或其他层的节点缺少左或右子树。

判断完全二叉树的方法

要判断一个二叉树是否是完全二叉树，可以采用以下步骤：

判断树是否为空，直接返回错误。

层序遍历树。

遍历过程中，遇到每个节点：

如果节点左右孩子同时存在，则继续处理左右子节点。

如果节点的左孩子为空但右孩子存在，则返回错误，说明树不是完全二叉树。

如果节点的右孩子为空但左孩子存在，或者节点本身是叶子节点（左右都为空），则将该节点加入队列，继续处理后续节点。

遍历结束后，若未遇到错误，树即为完全二叉树。

代码实现

Java实现

package algorithm;import java.util.*;public class CheckAllBinTree {    public boolean check(AllBinTreeNode root) {        if (root == null) {            return false;        }        Queue
   
     queue = new LinkedList<>();        queue.add(root);        boolean isLeaf = true;        while (!queue.isEmpty()) {            AllBinTreeNode current = queue.poll();            AllBinTreeNode left = current.left;            AllBinTreeNode right = current.right;            if (left != null || right != null) {                isLeaf = false;            }            if (isLeaf && (left != null || right != null)) {                return false;            }            if (left != null) {                queue.add(left);            }            if (right != null) {                queue.add(right);            } else {                isLeaf = true;            }        }        return true;    }}public class AllBinTreeNode {    AllBinTreeNode left = null;    AllBinTreeNode right = null;    public AllBinTreeNode() {}    public AllBinTreeNode(AllBinTreeNode left, AllBinTreeNode right) {        this.left = left;        this.right = right;    }}

C++实现

#include 
   
    using namespace std;template
    
     struct TreeNode {    T data;    TreeNode* left = nullptr;    TreeNode* right = nullptr;    TreeNode(T x) : data(x), left(nullptr), right(nullptr) {}};template
     
      bool IsComplete(TreeNode
      
       * root) {    if (root == nullptr) {        return false;    }    queue
       
        
         *> q; q.push(root); while (!q.empty()) { TreeNode
         
          * current = q.front(); q.pop(); bool hasLeft = current->left != nullptr; bool hasRight = current->right != null; if (hasLeft && hasRight) { q.push(current->left); q.push(current->right); } else if (!hasLeft && hasRight) { return false; } else if (hasLeft || !hasRight) { q.push(current->left); q.push(current->right); } } return true;}

以上实现主要包含以下步骤：

使用队列进行层序遍历。

检查每个节点左、右孩子的情况。

根据检查结果，决定是返回true还是false。

通过这种方式，可以高效地判断二叉树是否为完全二叉树。代码结构简洁，易于理解和维护。

转载地址：http://ugsiz.baihongyu.com/

你可能感兴趣的文章