JAVA版完全二叉树的创建、判断和层次遍历问题

完全二叉树（Complete Binary Tree）是从0到h-1的每一层都具有最大可能的节点数，并且层数h上的所有叶子节点按照从左之右的顺序进行填充。高度为h的最大完全二叉树在层数h上含有 $2^h$ 个节点。

完全二叉树

完全二叉树

满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树。

非完全二叉树

非完全二叉树

二叉树具有的性质

二叉树的性质

性质1：在二叉树的第 $i$ 层上至多有 $2^{i - 1}$

−

$2^{i-1}$ 个结点

（i≥1）（ i ≥ 1 ） $（i≥1）$ 。（数学归纳法可证）

性质2：深度为 $k$ 的二叉树最多有 $2^{k} - 1$

−

$2^k-1$ 个结点

（k≥1）（ k ≥ 1 ） $（k≥1）$ 。（由性质1，通过等比数列求和可证）

性质3：一棵二叉树的叶子结点数为 $n_0$ ，度为2的结点数为 $n_2$ ，则 $n_0$ = $n_2$ + 1。

证：结点总数 $n$ = $n_{0}$

$n_0$ +

n1 n 1 $n_1$ +

n2 n 2 $n_2$ 。设B为分支总数，因为除根节点外，其余结点都有一个分支进入，所以

n=B+1 n = B + 1 $n = B + 1$ 。又因为分支是由度为1或2的结点射出，所以

B=n1+2n2 B = n 1 + 2 n 2 $B = n1 + 2n_2$ 。综上：

n=n0+n1+n2=B+1=n1+2n2+1 n = n 0 + n 1 + n 2 = B + 1 = n 1 + 2 n 2 + 1 $n = n_0 + n_1 + n_2 = B + 1 = n_1 + 2n_2 + 1$ ，得出：

n0=n2+1 n 0 = n 2 + 1 $n_0 = n_2 + 1$ 。

性质4：具有 $n$ 个结点的完全二叉树的深度为 $f l o o r (l o g_{2}^{n}) + 1$

(

)

$floor(log_2^n) + 1$ 。

性质5：如果对一棵有 $n$ 个结点的完全二叉树（其深度为 $f l o o r (l o g_{2}^{n}) + 1$

(

)

$floor(log_2^n) + 1$ ）的结点按层序编号，则对任一结点

i（1≤i≤n） i （ 1 ≤ i ≤ n ） $i（1≤i≤n）$ 有：

（1）如果 $i = 1$ ，则结点i是二叉树的根，无双亲；如果i > 1，则其双亲PARENT(i)是结点 $floor((i)/2)$ 。

（2）如果 $2i > n$ ，则结点 $i$ 无左孩子；否则其左孩子LCHILD(i)是结点 $2 i$

$2i$ 。

（3）如果 $2i + 1 > n$ ，则结点 $i$ 无右孩子；否则其右孩子RCHILD(i)是结点 $2 i + 1$

$2i + 1$ 。

创建一颗完全二叉树的算法设计

定义树的节点

package com.bean.binarytreedemo;public class TreeNode {    int data;    TreeNode leftChild;    TreeNode rightChild;    TreeNode(){        this.leftChild=null;        this.rightChild=null;        this.data=-1;    }    TreeNode(int data){        this.leftChild=null;        this.rightChild=null;        this.data=data;    }    public TreeNode(int data, TreeNode leftChild, TreeNode rightChild) {        this.data = data;        this.leftChild = leftChild;        this.rightChild = rightChild;    }//其它方法省略}

创建一颗完全二叉树

public class ContructBinaryTree {    //根据根节点创建完全二叉树      public static TreeNode createTree(TreeNode root, List
   
     list) {          LinkedList
    
      queue = new LinkedList<>();          queue.add(root);          int count = 0;          while (!queue.isEmpty() && count < list.size()) {              TreeNode lastNode = queue.poll();              if (count < list.size()) {                  TreeNode left = new TreeNode(list.get(count++));                  lastNode.leftChild = left;                  queue.add(left);              }              if (count < list.size()) {                  TreeNode right = new TreeNode(list.get(count++));                  lastNode.rightChild = right;                  queue.add(right);              }          }          return root;      }      /*     * 判断二叉树是否为一颗完全二叉树     * */    public static boolean isCompleteTreeNode(TreeNode root){        if(root == null){            return false;        }        Queue
     
       queue = new LinkedList
      
       ();        queue.add(root);        boolean result = true;        boolean hasNoChild = false;        while(!queue.isEmpty()){            TreeNode current = queue.remove();            if(hasNoChild){                if(current.leftChild!=null||current.rightChild!=null){                    result = false;                    break;                }            }else{                if(current.leftChild!=null&&current.rightChild!=null){                    queue.add(current.leftChild);                    queue.add(current.rightChild);                }else if(current.leftChild!=null&&current.rightChild==null){                    queue.add(current.leftChild);                    hasNoChild = true;                }else if(current.leftChild==null&&current.rightChild!=null){                    result = false;                    break;                }else{                    hasNoChild = true;                }            }        }        return result;    }    /*     * 二叉树的层次遍历     * */    public static ArrayList
       
        
         > levelOrder(TreeNode root){ ArrayList
         
          
           > result = new ArrayList
           
            
             >(); if(root == null){ return result; } Queue
             
               queue = new LinkedList
              
               (); queue.offer(root); while(!queue.isEmpty()){ int size = queue.size(); ArrayList
               
                 level = new ArrayList
                
                 (); for(int i = 0;i < size ;i++){ TreeNode node = queue.poll(); level.add(node.data); if(node.leftChild != null){ queue.offer(node.leftChild); } if(node.rightChild != null){ queue.offer(node.rightChild); } } result.add(level); } System.out.println(result); return result; } public static void main(String[] args) { List
                 
                   list = new ArrayList<>(); for (int i = 1; i <= 10; i++) { list.add(i); } TreeNode root = new TreeNode(0); createTree(root, list); /* * 判断二叉树是否为完全二叉树 * */ boolean isCompleteBinaryTree=isCompleteTreeNode(root); if(isCompleteBinaryTree) { System.out.println("该二叉树[是]一颗完全二叉树."); }else { System.out.println("该二叉树[不是]一颗完全二叉树"); } System.out.println("------------------------------------"); /* * 二叉树的层次遍历为 * */ System.out.println("二叉树的层次遍历为："); levelOrder(root); System.out.println("------------------------------------"); } }

（完）

你可能感兴趣的文章