二叉树基本概念
二叉树
- 一个二叉树的第i层的最大节点是
2^(i-1) . 例如：1层=>1 2层=>2 3层=>4 .... i层 就是2^(i-1) - 深度为k的最大节点数是：
2^k-1 - 对任何非空二叉树T， 若n0表示为叶子节点，n2表示度2的非叶子节点。总是满足：
n0 = n2 + 1 - 节点的度：节点的子树个数。例如：二叉树中最大的度就是2
- 叶子节点：也称为终端节点，没有子树的节点或是度为0的节点
- 节点的层次：从根节点开始，假设根节点是1，根节点的子节点是2，以此类推
- 树的深度：也称为树的高度，树中所有节点的层次最大值称为树的深度
满二叉树
- 满二叉树又是 完美二叉树
- 除了最后一层以外的节点都是满的
- 满二叉树又称特殊的完全二叉树。(
满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树)
完全二叉树
- 除了最后一层，其余的节点都是满的
- 最后一层从左到右的叶子节点是连续的
- 只缺若干个右侧节点
二叉搜索树
- 左子树的所有值比父节点要小
- 右子树的所有值比父节点要大
- 任意子树都是二叉搜索树
红黑树
- 节点只能是黑色/ 红色
- 根节点必须是黑色
- 每个叶子节点都是黑色的空节点(NIL节点)
- 每个红色节点的两个子节点都是黑色的(每个叶子到根的所有路径上不能出现两个连续的红色节点)
- 从任一节点到叶子节点的所有路径都包含相同数数目的黑色节点
