欢迎来到入门教程网!

Java编程

当前位置:主页 > 软件编程 > Java编程 >

判断二叉树是否为完全二叉树的实例

来源:本站原创|时间:2020-01-10|栏目:Java编程|点击:

完全二叉树特点

完全二叉树是指除了最后一层之外,其他每一层的结点数都是满的。最后一层如果也满了,是一颗满二叉树,也是完全二叉树。最后一层如果不满,缺少的结点也全部的集中在左边,那也是一颗完全二叉树。

判断一棵二叉树是否为完全二叉树

import java.util.*;
class TreeNode {
  int val = 0;
  TreeNode left = null;
  TreeNode right = null;
  public TreeNode(int val) {
    this.val = val;
  }
}
public class CheckCompletion {
  public boolean checking(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    boolean leaf = false; // 叶子结点
    TreeNode left;
    TreeNode right;
    queue.add(root);
    while (!queue.isEmpty()) {
      root = queue.poll();
      left = root.left;
      right = root.right;
      if ((leaf&&(left!=null||right!=null)) || (left==null&&right!=null)) {
        // 如果之前层遍历的结点没有右孩子,且当前的结点有左或右孩子,直接返回false
        // 如果当前结点有右孩子却没有左孩子,直接返回false
        return false;
      }
      if (left != null) {
        queue.offer(root.left);
      }
      if (right != null) {
        queue.offer(root.right);
      }else {
        leaf = false; // 如果当前结点没有右孩子,那么之后层遍历到的结点必须为叶子结点
      }
    }
    return true;
  }
}

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

上一篇:Java编程实现递增排序链表的合并

栏    目:Java编程

下一篇:Java编程基础测试题分享

本文标题:判断二叉树是否为完全二叉树的实例

本文地址:https://www.xiuzhanwang.com/a1/Javabiancheng/8463.html

网页制作CMS教程网络编程软件编程脚本语言数据库服务器

如果侵犯了您的权利,请与我们联系,我们将在24小时内进行处理、任何非本站因素导致的法律后果,本站均不负任何责任。

联系QQ:835971066 | 邮箱:835971066#qq.com(#换成@)

Copyright © 2002-2020 脚本教程网 版权所有