首页 > 代码库 > 【算法导论学习-30】 二叉树专题5:二叉树类型的判断

【算法导论学习-30】 二叉树专题5:二叉树类型的判断

一、完全二叉树的判断

参考:http://blog.csdn.net/lilypp/article/details/6158699/

【分析】根节点开始进行层次遍历,节点入队列,如果队列不为空,循环。遇到第一个没有左儿子或者右儿子的节点,设置标志位,如果之后再遇到有左/右儿子的节点,那么这不是一颗完全二叉树。

/*使用LinkedList实现队列,入队使用queue.offer(),出队使用queue.poll()*/
       Queue<BinaryTreeNode<T>> queue=new LinkedList<>();
        boolean flag=true;
       queue.offer(root);
        while (!queue.isEmpty()) {
           BinaryTreeNode<T> tempNode=queue.poll();
            if (tempNode.getLeftChild()!=null&&flag){
               queue.offer(tempNode.getLeftChild());
           }else if (tempNode.getLeftChild()!=null) {
                return false;
           }else {
                flag=false;
           }
           
            if (tempNode.getRightChild()!=null&&flag){
               queue.offer(tempNode.getRightChild());
           }else if (tempNode.getRightChild()!=null) {
                return false;
           }else {
                flag=false;
           }
           
           }
        /*如果遍历完成仍然没有返回false,表明是完全二叉树*/
        return true;
       }


二、平衡二叉树的判断

【分析-1】root开始往下递归判断节点的左右子树的深度差(动态规划问题,但不容易加入备忘机制,所以比较低效) 。子树的深度被重复计算,所以比较低效。

/*递归判断左右子树的深度,如果深度差的绝对值大于1表明非平衡树*/

    public  int isBalancedTree(BinaryTreeNode<T> node) {

        if (node==null) {

            return 1;

       }

        int leftDepth=getTreeDeep(node.getLeftChild());

        int rightDepth=getTreeDeep(node.getRightChild());

        int diff=leftDepth-rightDepth;

        if (diff<-1||diff>1) {

            return 0;

       }else {

            if (isBalancedTree(node.getLeftChild())==1&&isBalancedTree(node.getRightChild())==1){

                return 1;

           }else {

                return 0;

           }

           

       }

       

    }

    /* 获得树的高度,递归过程 */

    private int getTreeDeep(BinaryTreeNode<T> root) {

        if (root == null) {

            return 0;

       }

        if (root.getLeftChild() == null && root.getRightChild() == null) {

            return 1;

       }

 

        return 1 + Math.max(getTreeDeep(root.getLeftChild()),

               getTreeDeep(root.getRightChild()));

    }

【分析-2】利用动态规划的方法从底向上计算每个子数的深度。从顶向下递归传递一个Integer对象,探底之后就从底向上开始计算,本质上是后续遍历。这里要注意,Depth depth需要传址调用,所以不能用intInterger,而要新定义一个类。

/*isBalancedTree(node.getLeftChild(),leftDepth)&&isBalancedTree(node.getRightChild(),rightDepth)表明先左边探底,然后上移一个节点计算右子数,是后续遍历过程*/
        public boolean isBalancedTree(BinaryTreeNode<T> node,Depth depth){
      if (node==null) {
           depth=new Depth(0);
         return true;
         }
        Depth leftDepth=new Depth(0),rightDepth=new Depth(0);
        if (isBalancedTree(node.getLeftChild(),leftDepth)&&isBalancedTree(node.getRightChild(),rightDepth)){
            int diff=leftDepth.getDepth()-rightDepth.getDepth();
            if (diff<=1&&diff>=-1) {
               depth.setDepth(1 + Math.max(leftDepth.getDepth(),rightDepth.getDepth()));
               System.out.println(depth.getDepth());
                return true;
           }
       }
        return false;
   }
    public boolean isBalancedTree(){
        return isBalancedTree(root, new Depth(0));
   }
    class Depth{
        int depth;
        public Depth(int depth) {
            // TODO 自动生成的构造函数存根
            this.depth=depth;
       }
 
        public int getDepth() {
            return depth;
       }
 
        public void setDepth(int depth) {
            this.depth = depth;
       }
       
   }


三、二叉搜索树(BST)的判断

参考:http://www.2cto.com/kf/201310/250996.html

【分析】BST的中序遍历是递增数列,所以可以利用中序遍历来进行判断。这里也是递归调用,需要传址调用,所以不能用int或Interger来定义pre。

先设计一个类:

class Pre{
    int pre;
 
    public int getPre() {
        return pre;
    }
 
    public void setPre(int pre) {
        this.pre = pre;
    }
   
}


函数体:

public staticbooleanisBST(BinarySearchTreesNode<String> root) {
        Prepre=new Pre();
        pre.setPre(Integer.MIN_VALUE);
        return isBSTOrder(root, pre);
       
    }
    public static booleanisBSTOrder(BinarySearchTreesNode<String> root,Pre pre) {
        if (root==null) {
            return true;
        }
        if (isBSTOrder(root.getLeftChild(), pre)) {
            if (root.getKey()>pre.getPre()) {
                pre.setPre(root.getKey());
                return isBSTOrder(root.getRightChild(), pre);
            }else {
                return false;
            }
        }
       
            return false;
       
    }


【算法导论学习-30】 二叉树专题5:二叉树类型的判断