二叉树的基本概念

二叉树的定义：

N（N > 0）个节点的有限集合，由一个根节点以及两颗互不相交的、分别称为左子树和右子树的二叉树组成。

二叉树的结构特点：

每个节点最多只有两棵子树 ，不存在度大于2的节点（1 : 2）；左子树和右子树次序不能颠倒（有序树）

二叉树的分类

满二叉树

一颗深度为k，且有2k-1个节点的二叉树

完全二叉树

除最后一层外，每一层上的节点数均达到最大值，在最后一层上只缺少右边的若干接点。

一个满二叉树一定是一个完全二叉树，但是一个完全二叉树不一定是满二叉树。

二叉树的相关概念：

二叉树的性质：

性质1：在二叉树的第 i 层上至多有2i-1个节点（i > 0）【想法Tag：每一层 可参考16进制 Bit位】性质2：深度为 k 的二叉树至多有2k-1个节点（k> 0）【想法Tag：可参考 对应层数的Bit位 置1】性质3：对于任何一颗二叉树，度为2的节点数+1 = 数的叶子节点数性质4：具有 n 个节点的完全二叉树的深度必为 log ⁡ 2 n + 1 \log_2{n}+1 log2​n+1性质5：对完全二叉树，若从上至下，从左至右编号，则编号为i的结点，其左孩子编号为必为2i，其左孩子编号为必为2i+1，其左孩子编号为必为i/2（i = 1时为根除外）