树的高度
树的高度是节点高度的最大值。
每一层节点的高度如图所示。
方法一：递归
根节点的高度显然就是二叉树的高度。
/**
* 获取树的高度* @return*/
public int height(){return height2(root);
}/*** 使用递归方法获取树的高度* @param node* @return*/
private int height1(Node<E> node){if(node==null)return 0;//当前节点的高度等于左右子节点高度最大值+1return Math.max(height1(node.left)+1,height1(node.right)+1);
}
方法二：非递归
通过层序遍历的方法计算高度，每走完一层，高度就加了1。显然该方法要计算每层的节点数并记录，而该层的节点数显然是上一层的节点访问完出队，并将左右节点入队列后队列的大小。而第一层的节点只有根节点，节点数为1。
/**
* 获取树的高度* @return*/
public int height(){return height2(root);
}/*** 使用非递归方法获取树的高度* @param node* @return*/
private int height2(Node<E> node){Queue<Node<E>> queue=new LinkedList<>();queue.offer(node);int levelSize=1;//while(!queue.isEmpty()){Node<E> node=queue.poll();levelSize--;//节点数减一int height=0;if(null!=node.left)queue.offer(node.left);if(null!=node.right)queue.offer(node.right);//如果当前层节点数用完则层数加一,并跟新下一层节点数if(0==levelSize){height++;levelSize=queue.size();}}return height;
}
判断是否是完全二叉树
完全二叉树就是节点从上往下，从左往右依次放置节点的二叉树，显然其结构与层序遍历很有关联。而一棵完全二叉树有四种节点：
（1）有两个子节点的节点（什么都无法表明，只需将左右节点入队列）
（2）有左子节点，无右子节点的节点（表明后面的节点必须是叶子节点，如图中的节点：3，层序遍历在3之后都是叶子节点）
（3）有右子节点，无左子节点的节点（显然已经不是完全二叉树了）
（4）既无左子节点，又无右子节点（叶子节点：表明后面存在的节点必须也是是叶子节点）
那么创建一个变量记录出否出现了（3）（4）情况，通过层序遍历，就能判断出一棵树是否是完全二叉树了。
此外可以在节点类中新增isLeaf方法和hasTwoChildren方法，让代码看起来更简洁。
//构造树节点
private static class Node<E>{E element;Node<E> left;Node<E> right;Node<E> parent;public Node(E element, Node<E> parent) {this.element = element;this.parent = parent;}public boolean isLeaf(){return left==null&&right==null;}public boolean hasTwoChildren(){return left!=null&&right!=null;}
}
public boolean isComplete(){Queue<Node<E>> queue=new LinkedList();queue.offer(root);boolean isLeaf=false;while(!queue.isEmpty()){Node<E> node=queue.poll();//如果要求是叶子节点但不是，则不是完全二叉树if(isLeaf&&!node.isLeaf())return false;if(node.hasTwoChildren()){queue.offer(node.left);queue.offer(node.right); }else if(node.left==null&&node.right!=null){return false;//不是完全二叉树}else{//否则后面的节点必须是叶子节点isLeaf=true;if(null!=node.left)//左节点可能不为空queue.offer(node.left);}}return true;
}
