二叉树

二叉树是数据结构中的一种重要数据结构，也是树表家族最为基础的结构。

定义：

二叉树的每个结点至多只有两棵子树（不存在度大于2的节点），二叉树的子树有左右之分，次序不能颠倒。二叉树第i层至多有 2^i-1 个结点，深度为k的二叉树至多有 2^k-1 个节点。

满二叉树和完全二叉树：

满二叉树：除最后一层无任何子节点外，每一层的所有节点都有两个子节点。也可以这样理解，除叶子节点外的所有节点均有两个子节点。节点数达到最大值，所有叶子节点必须在同一层上。

满二叉树的性质：

• 一颗树的深度为h，最大层为k，深度与最大层数相同，k=h。
• 叶子树数为2^h。
• 第k层的节点数为2^k-1
• 总节点数是： 2^k-1 ,并且总结点数一定是奇数。
  完全二叉树：若设二叉树的深度为h，除第h层外，其他各层（1~（h-1）层）的节点数都达到最大个数，第h层所有的节点都连续集中在最左边，这就是完全二叉树。

注意：完全二叉树是效率很高的数据结构，堆是一种完全二叉树或者近似完成二叉树，所以效率极高，像十分常用的排序算法、Dijkstra算法、Prim算法等都是要用堆才能优化，二叉排序树的效率也要借助平衡性来提高，而平衡性基于完全二叉树。

二叉树的性质

• 在非空二叉树中，第i层的节点总数不超过2^i-1 ,i>=1;
• 深度 为h的二叉树最多有2^h - 1个节点（h>1），最少有h个节点。
• 对于任意一棵二叉树，如果其叶节点数为N0,而度为2的节点总数为N2，则N0=N2+1.
• 具有n个结点的完全二叉树的深度为log2(n+1);