搜索二叉树,完全二叉树,平衡二叉树的判断
1、概念
搜索二叉树(Binary Search Tree - BST)
它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
完全二叉树(Complete Binary Tree- CBT)
若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边。
经典应用:堆
平衡二叉树(Self-balancing binary search tree)
它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
总的一句话就是,任意节点左右子树的高度差不超过1
2、搜索二叉树的判断
思路
由于搜索二叉树的特性,根节点 > 左,根节点 < 右,那么其中序遍历的顺序必然是升序的。那么我们只需在中序遍历的非递归版本,每个节点都和上一个节点比较,即可知道整个序列是否有序了。
算法实现
/// 判断是否是搜索二叉树,就要判断是否符合左子树 < 根节点,右子树 > 根节点
/// 而该树是搜索二叉树,那么其中序遍历必然是升序的,因此在非递归的中序遍历基础上
/// 修改,只需对比当前数比上一个数都大,即可判断是否是搜索二叉树
public static boolean isBST(Node head) {
if (head == null) {
return true;
}
int pre = Integer.MIN_VALUE;
Stack<Node> stack = new Stack<Node>();
while (!stack.isEmpty() || head != null) {
if (head != null) {
stack.push(head);
head = head.left;
}else {
head = stack.pop();
if (head.value < pre) {
return false;
}
pre = head.value;
head = head.right;
}
}
return true;
}
3、完全二叉树的判断
思路
根据完全二叉树排列特性,必然先挂左边的树,可以得出以下结论:
1、如果一个树,有右孩子,没有左孩子,那么必然不是满二叉树
2、如果一个树,只有左孩子,那么后续节点必然都是叶子节点,才能是满二叉树
算法实现
该算法是在层级遍历的基础上,修改的。
/// 判断是否是满二叉树
/// 1、如果一个树,有右孩子,没有左孩子,那么必然不是满二叉树
/// 2、如果一个树,只有左孩子,那么后续节点必然都是叶子节点,才能是满二叉树
public static boolean isCBT(Node head) {
if (head == null) {
return true;
}
Queue<Node> queue = new LinkedList<Node>();
queue.offer(head);
boolean isLeaf = false;
while(!queue.isEmpty()) {
head = queue.poll();
if (isLeaf) {
if (head.left != null || head.right != null) {
return false;
}
}
// 只有右孩子,没有左孩子,必然不是满二叉树
if (head.left == null && head.right != null) {
return false;
}
if (head.left != null && head.right == null) {
// 开启后续节点必为叶节点的判断
isLeaf = true;
}
if (head.left != null) {
queue.offer(head.left);
}
if (head.right != null) {
queue.offer(head.right);
}
}
return true;
}
4、平衡二叉树的判断
思路
由于平衡二叉树要求任意左右子树的高度差不超过1。那么,要求当前节点是否平衡,我们需要知道两个信息:
1、该节点的左右子树是否平衡
2、该节点的左右子树高度相差是否大于1
那么,我们就可以根据以上两个条件,知道了我们递归的过程中,需要判断以及返回的东西了
算法实现
在递归求二叉树的高度的基础上,做了修改
public static boolean isBalance(Node head) {
boolean[] res = new boolean[1];
res[0] = true;
getHeight(head, res);
return res[0];
}
public static int getHeight(Node head, boolean[] res) {
if (head == null) {
return 0;
}
int lh = getHeight(head.left, res);
if (!res[0]) {
return 0;
}
int rh = getHeight(head.right, res);
if (!res[0]) {
return 0;
}
if (Math.abs(lh - rh) > 1) {
res[0] = false;
}
return Math.max(lh, rh) + 1;
}