二叉树

介绍

如果树中每个节点最多只能有两个子节点, 这样的树就称为 二叉树

二叉树可以为空, 也就是没有节点

若二叉树不为空, 则它由根节点和称为其左子树 TL 和右子树 TR 的两个不相交的二叉树组成

特性

• 一个二叉树第 i 层的最大节点数为: 2^(i-1) i >= 1
• 深度为 k 的二叉树有最大节点总数为: 2^k-1 k >= 1
• 对任何非空二叉树 T , 若 n0 表示叶节点多个数 n2 是度为 2 的非叶节点个数, 那么两者满足关系 n0 = n2 + 1

其他树

完美二叉树/满二叉树

除了最下一层的叶节点外, 每一层节点都有两个子节点

完全二叉树

除了最下一层的叶节点外, 其他各层的节点数都达到最大个数, 并且只能缺少右侧的若干节点, 左侧的不能缺少

二叉搜索树/二叉排序树/二叉查询树

跳转