二叉树基本概念和性质

二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。
图3.1展示了一棵普通二叉树：

所以二叉树顾名思义就是一个节点的度小于等于两个度的树同时子树是有左右之分的不能随意颠倒（有序树）

二叉树基本概念和性质

二叉树性质

1）在二叉树的第i层上最多有2i-1 个节点。（i>=1）
2）二叉树中如果深度为k,那么最多有2k-1个节点。(k>=1）
3）n0=n2+1 n0表示度数为0的节点数，n2表示度数为2的节点数。

其实也很好理解就是1度的节点对于叶子的数量不会有增加或者减少影响每次出现一个2度节点就会多一片叶子因此加上根节点产生的叶子就是2度节点数量＋根的数量也就是 n2+1

4）在完全二叉树中，具有n个节点的完全二叉树的深度为[log2n]+1，其中[log2n]是向下取整。
5）若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点有如下特性：

(1) 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 [i/2] 的结点为其双亲结点;
(2) 若 2i>n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点；
(3) 若 2i+1>n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。