二叉树进阶：平衡二叉树、完全二叉树、满二叉树详解

        在上一篇博客中，我们介绍了二叉树的基本概念、遍历方式以及常见操作。本篇将深入探讨二叉树的几种特殊类型：平衡二叉树、完全二叉树和满二叉树，并通过Java代码示例帮助大家更好地理解这些概念。

 1. 满二叉树 (Full Binary Tree)

定义
满二叉树是指一棵二叉树中，**每个节点都有0个或2个子节点**。换句话说，除了叶子节点外，每个节点都有两个子节点。

 特点
- 叶子节点只能出现在最底层。
- 非叶子节点的度（子节点数）必须为2。
- 如果树的高度为`h`，则节点总数为 `2^h - 1`。

 示例

1/ \2   3/ \ / \4  5 6 7

这是一棵高度为3的满二叉树，节点总数为 `2^3 - 1 = 7`。

Java代码：判断满二叉树

public boolean isFullBinaryTree(TreeNode root) {if (root == null) {return true; // 空树是满二叉树}// 如果左右子树都为空，则是叶子节点if (root.left == null && root.right == null) {return true;}// 如果左右子树都不为空，则递归检查if (root.left != null && root.right != null) {return isFullBinaryTree(root.left) && isFullBinaryTree(root.right);}// 其他情况（一个子节点为空，另一个不为空）不是满二叉树return false;
}

2. 完全二叉树 (Complete Binary Tree)

定义
完全二叉树是指一棵二叉树中，**除了最后一层外，其他层都是满的，并且最后一层的节点都靠左排列。

特点
- 叶子节点只能出现在最底层或次底层。
- 最后一层的节点从左到右连续排列，不能有空缺。
- 常用于实现堆（如优先队列）。

示例

        1/ \2   3/ \ /4  5 6

这是一棵完全二叉树，最后一层的节点靠左排列。Java代码：判断完全二叉树

import java.util.LinkedList;
import java.util.Queue;public boolean isCompleteBinaryTree(TreeNode root) {if (root == null) {return true; // 空树是完全二叉树}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);boolean hasNullNode = false; // 标记是否遇到空节点while (!queue.isEmpty()) {TreeNode current = queue.poll();if (current == null) {hasNullNode = true; // 遇到空节点} else {if (hasNullNode) {return false; // 如果之前有空节点，当前节点不为空，则不是完全二叉树}queue.offer(current.left);queue.offer(current.right);}}return true;
}

 3. 平衡二叉树 (Balanced Binary Tree)

定义
平衡二叉树是指一棵二叉树中，**每个节点的左右子树高度差不超过1**。平衡二叉树的主要目的是保证树的查询效率，避免退化为链表。

 特点
- 每个节点的左右子树高度差不超过1。
- 常见的平衡二叉树有AVL树和红黑树。
- 插入和删除操作可能需要调整树的结构以保持平衡。

        1/ \2   3/ \   \4   5   6

这是一棵平衡二叉树，每个节点的左右子树高度差不超过1。Java代码：判断平衡二叉树

public boolean isBalanced(TreeNode root) {return getHeight(root) != -1;
}private int getHeight(TreeNode root) {if (root == null) {return 0; // 空树高度为0}int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);// 如果左右子树不平衡，返回-1if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {return -1;}// 返回当前树的高度return Math.max(leftHeight, rightHeight) + 1;
}

 4. 二叉搜索树 (Binary Search Tree, BST)

定义
二叉搜索树是一种特殊的二叉树，满足以下性质：
- 左子树的所有节点值小于根节点的值。
- 右子树的所有节点值大于根节点的值。
- 左右子树也分别是二叉搜索树。

特点
- 中序遍历结果是一个有序序列。
- 查找、插入和删除的平均时间复杂度为 `O(log n)`。

示例

        4/ \2   6/ \ / \1  3 5  7

这是一棵二叉搜索树，中序遍历结果为 `[1, 2, 3, 4, 5, 6, 7]`。 Java代码：判断二叉搜索树
 

public boolean isBST(TreeNode root) {return isBSTUtil(root, Long.MIN_VALUE, Long.MAX_VALUE);
}private boolean isBSTUtil(TreeNode root, long min, long max) {if (root == null) {return true;}if (root.val <= min || root.val >= max) {return false;}return isBSTUtil(root.left, min, root.val) && isBSTUtil(root.right, root.val, max);
}

5. 总结

满二叉树：每个节点都有0个或2个子节点。
完全二叉树：除了最后一层，其他层都是满的，最后一层节点靠左排列。
平衡二叉树：每个节点的左右子树高度差不超过1。
二叉搜索树：左子树小于根节点，右子树大于根节点。

这些特殊的二叉树在实际开发中有着广泛的应用，例如：
堆（完全二叉树）用于实现优先队列。
AVL树和红黑树（平衡二叉树）用于高效的数据查找和插入。
二叉搜索树用于排序和搜索。

 6. 参考资料

- 《算法导论》
- 《数据结构与算法分析》
- LeetCode二叉树相关题目

如果你对二叉树的这些特殊类型有任何疑问，或者想了解更多细节，欢迎在评论区留言！