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

完全二叉树特点

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

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

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;
  }
}

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

时间: 2017-05-21

java 完全二叉树的构建与四种遍历方法示例

本来就是基础知识,不能丢的太干净,今天竟然花了那么长的时间才写出来,记一下. 有如下的一颗完全二叉树: 先序遍历结果应该为:1  2  4  5  3  6  7 中序遍历结果应该为:4  2  5  1  6  3  7 后序遍历结果应该为:4  5  2  6  7  3  1 层序遍历结果应该为:1  2  3  4  5  6  7 二叉树的先序遍历.中序遍历.后序遍历其实都是一样的,都是执行递归操作. 我这记录一下层次遍历吧:层次遍历需要用到队列,先入队在出队,每次出队的元素检查是其是

Java完全二叉树的创建与四种遍历方法分析

本文实例讲述了Java完全二叉树的创建与四种遍历方法.分享给大家供大家参考,具体如下: 有如下的一颗完全二叉树: 先序遍历结果应该为:1  2  4  5  3  6  7 中序遍历结果应该为:4  2  5  1  6  3  7 后序遍历结果应该为:4  5  2  6  7  3  1 层序遍历结果应该为:1  2  3  4  5  6  7 二叉树的先序遍历.中序遍历.后序遍历其实都是一样的,都是执行递归操作. 我这记录一下层次遍历吧:层次遍历需要用到队列,先入队在出队,每次出队的元素

java中关于Map的三种遍历方法详解

map的三种遍历方法!集合的一个很重要的操作---遍历,学习了三种遍历方法,三种方法各有优缺点~~ 复制代码 代码如下: /* * To change this template, choose Tools | Templates * and open the template in the editor. */package cn.tsp2c.liubao;import java.util.Collection;import java.util.HashMap;import java.util

Python下载网络文本数据到本地内存的四种实现方法示例

本文实例讲述了Python下载网络文本数据到本地内存的四种实现方法.分享给大家供大家参考,具体如下: import urllib.request import requests from io import StringIO import numpy as np import pandas as pd ''' 下载网络文件,并导入CSV文件作为numpy的矩阵 ''' # 网络数据文件地址 url = "http://archive.ics.uci.edu/ml/machine-learning

Java中四种遍历List的方法总结(推荐)

实例如下: package com.ietree.basic.collection.loop; import java.util.ArrayList; import java.util.Iterator; import java.util.List; /** * List遍历 * * @author Dylan */ public class ListLoop { public static void main(String[] args) { // 初始化一个长度为10的ArrayList L

Map集合的四种遍历方式代码示例

很久以前写的代码,和上一个做比较吧!便于以后查看. import java.util.HashMap; import java.util.Iterator; import java.util.Map; public class TestMap { public static void main(String[] args) { Map<Integer, String> map = new HashMap<Integer, String>(); map.put(1, "a&

java实现二叉树的创建及5种遍历方法(总结)

用java实现的数组创建二叉树以及递归先序遍历,递归中序遍历,递归后序遍历,非递归前序遍历,非递归中序遍历,非递归后序遍历,深度优先遍历,广度优先遍历8种遍历方式: package myTest; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Stack; public class myClass { public static void main(

java读取XML文件的四种方法总结(必看篇)

JAVA操作XML文档主要有四种方式,分别是DOM.SAX.JDOM和DOM4J,DOM和SAX是官方提供的,而JDOM和DOM4J则是引用第三方库的,其中用的最多的是DOM4J方式.运行效率和内存使用方面最优的是SAX,但是由于SAX是基于事件的方式,所以SAX无法在编写XML的过程中对已编写内容进行修改,但对于不用进行频繁修改的需求,还是应该选择使用SAX. 下面基于这四种方式来读取XML文件. 第一,以DOM的方式实现. package xmls; import org.w3c.dom.D

java获取当前时间的四种方法代码实例

这篇文章主要介绍了java获取当前时间的四种方法代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 第一种:Date类 public class DateDemo { public static void main(String[] args) { Date day = new Date(); SimpleDateFormat dft = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); S

Map获取键值,Map的几种遍历方法总结(推荐)

Map获取键值 Map以按键/数值对的形式存储数据,和数组非常相似,在数组中存在的索引,它们本身也是对象. Map的接口 Map---实现Map Map.Entry--Map的内部类,描述Map中的按键/数值对. SortedMap---扩展Map,使按键保持升序排列 关于怎么使用,一般是选择Map的子类,而不直接用Map类. 下面以HashMap为例 public static void main(String args[]) { HashMap hashmap =new HashMap();