介绍

常见属性

• 节点的高度：节点到叶子节点的最长路径
• 节点的深度：根节点到该节点的路径
• 节点的层数：节点的深度 + 1
• 树的高度：根节点的高度

常见二叉树

• 满二叉树（Full）：除叶子节点外，每个节点都有左右子树
• 完全二叉树（Complete）：叶子节点只出现在最下面两层，且最后一层叶子节点都紧密靠左排列，除了最后一层，其他层节点个数达到最大
• 二叉搜索树（BST）：任意一个节点，左子树中的每个节点都小于该节点，右子树的每个节点都大于该节点，且左右子树也是二叉搜索树
• 平衡二叉树（AVL）：任意节点的左右子树高度相差不能大于 1

注意

判断二叉搜索树时，不能仅仅判断左右子节点是否满足「左小右大」，一定要注意是整个左子树和整个右子树

实现方法

• 基于链表的链式储存
• 基于数组的顺序存储

对于顺序存储，根节点存储在下标 i=1 的位置，对于任意节点 i，其左节点为 2i，右节点为 2i+1，父节点为 i/2 。完全二叉树天然适合于顺序存储，除了下标为 0 的位置，能够充分利用所有的内存空间

复杂度分析

对于二叉搜索树来说，操作的时间复杂度取决于树的高度，即与二叉树的形状有关

• 当二叉树在比较平衡的状态下，查找、插入、删除都只需要 O(logn) 时间
• 极度不平衡的情况下，时间复杂度则会退化为 O(n)

对比散列表

• 散列表中的数据是无序的，二叉树只需 O(n) 时间就可以输出有序数组（中序）
• 散列表性能不稳定（散列冲突的存在），平衡二叉树性能非常稳定
• 散列的构造更复杂，需要考虑散列函数、散列冲突、扩容方法等，二叉树只需要考虑平衡性
• 散列表装载因子不能太高，二叉树更能充分利用空间