二叉搜索树
二叉搜索树概念
定义：它或者是一棵空树，或者是具有下列性质的 二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的 根结点 的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为 二叉搜索树 。
（1）每个节点包含一个key，也称data的数据域
（2）左子树不为空的情况下，左子树的每个节点值都小于根节点的值，即：L < P
（3）右子树不为空的情况下，右子树的每个节点值都大于根节点的值，即：P < R
（4）节点的值不允许出现重复
（5）任意节点的左，右子树，均符合上面的规则
如何判断一颗树为二叉搜索树？
1、如果这颗树是空树，直接判定为是搜索二叉树
2、如果这棵树不是空树，我们就需要判定这棵树的左子树的每一个节点都小于头节点，右子树的每一个节点都大于头节点，且每颗子树都符合这样的规则。
我们可以利用二叉树的中序遍历（左头右）来依次存放进一个队列结构中，然后依次出队判断前一个节点是否小于后一个节点，从而达成对这颗树是否为二叉树的判断。
public class IsBST {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int value) {
this.value = value;
}
}
public static boolean isBST(Node head) {
/**
* 如果这颗树为空的化，直接判定为true
*/
if (head == null) {
return true;
}
/**
* 创建queue队列，process让这颗树以中序遍历的结果入队，
* 然后for循环进行遍历比较
*/
Queue<Node> queue = new LinkedList<Node>();
process(head, queue);
int pre = Integer.MIN_VALUE;
for (Node node : queue) {
if (pre >= node.value) {
return false;
}
pre = node.value;
}
return true;
}
private static void process(Node head, Queue<Node> queue) {
if (head == null) {
return;
}
process(head.left, queue);
queue.add(head);
process(head.right, queue);
}
}
满二叉树
满二叉树概念
一个二叉树，如果每一个层的节点数都达到最大值，则这个二叉树就是满二叉树。
也就是说，如果一个二叉树的深度为K，且节点总数是(2^k) -1 ，则它就是满二叉树。
怎么判断一颗树是满二叉树？
根据满二叉树节点总数=（2^k-1）的定义，我们可以求出这棵树左子树的深度和节点总数和右子树的深度和节点总数，然后求左右子树深度的最大值和左右子树的节点总数和，最后利用定义判断是否符合。
public class IsFBT {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int value) {
this.value = value;
}
}
public static boolean isFBT(Node head) {
if (head == null) {
return true;
}
/**
* 判断是否符合二叉树的公式
*/
return process(head).nodes == (1 << process(head).height - 1);
}
public static class ReturnType {
public int height;
public int nodes;
public ReturnType(int height, int nodes) {
this.height = height;
this.nodes = nodes;
}
}
public static ReturnType process(Node node) {
if (node == null) {
return new ReturnType(0, 0);
}
/**
* 递归求出左右子树的高度和节点总数
*/
ReturnType leftData = process(node.left);
ReturnType rightData = process(node.right);
/**
* 得到深度和节点总数
*/
int height = Math.max(leftData.height, rightData.height) + 1;
int nodes = leftData.nodes + rightData.nodes + 1;
return new ReturnType(height, nodes);
}
}
完全二叉树
完全二叉树的概念
一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
如何判断一颗树是完全二叉树？
1、依次从每层中检测，在这颗树中，如果有子树存在有右孩子无左孩子的情况，返回false。
2、在不违背条件1的情况下，如果遇到了第一个左右孩子不双全的子树，那么后续遇到的所有节点都是叶节点，才返回true。
public class IsCBT {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static boolean isCBT(Node head) {
if (head == null) {
return true;
}
LinkedList<Node> queue = new LinkedList<>();
//开关，是否遇到过左右两个孩子不双全的节点
boolean leaf = false;
Node l = null;
Node r = null;
queue.add(head);
while (!queue.isEmpty()) {
head = queue.poll();
l = head.left;
r = head.right;
if (
//如果遇到了不双全的节点之后，又发现当前节点不是叶节点
(leaf && (l != null || r != null))
||
(l == null && r != null)
) {
return false;
}
if (l != null) {
queue.add(l);
}
if (r != null) {
queue.add(r);
} else {
leaf = true;
}
}
return true;
}
}
平衡二叉树
平衡二叉树的概念
- 可以是空树。
- 假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过 1。
如何判断一颗树为平衡二叉树？
根据上面平衡二叉树的概念，我们只需要判断这颗二叉树的左子树和右子树都是平衡二叉树且左右子树的深度差的绝对值不超过1，且每颗子树都符合这个规则。
public class IsBalancedTree {
public static class Node {
public int value;
public practice.Node left;
public practice.Node right;
public Node(int value) {
this.value = value;
}
}
public static boolean isBalancedTree(practice.Node head){
return process(head).isBalanced;
}
public static class ReturnType{
public boolean isBalanced;
public int height;
public ReturnType(boolean isBalanced, int height) {
this.isBalanced = isBalanced;
this.height = height;
}
}
private static practice.ReturnType process(practice.Node head) {
if (head == null) {
return new practice.ReturnType(true,0);
}
practice.ReturnType leftData=process(head.left);
practice.ReturnType rightData=process(head.right);
int height=Math.max(leftData.height,rightData.height)+1;
boolean isBalanced=leftData.isBalanced&&rightData.isBalanced
&&Math.abs(leftData.height- rightData.height)<2;
return new practice.ReturnType(isBalanced,height);
}
}