二叉树
基础特征
1、树中每一个节点最多只能有两棵树，即每个节点最多为2
2、二叉树的子树有左右之分，即左子树与右子树,次序不能颠倒 也就是可以设为: 左子树=0 右子树=1
3、二叉树即使只有一个子树时，也要区分左子树还是右子树
满二叉树
满二叉树是一种特殊的二叉树,指所有分支节点都存在左右子树，且所有叶子节点都在同一层上。
可以理解为是一个二进制树 由祖节点开始分支 第一节点只有一棵树 设为: 0
第二节点开始 分支为 0 1 两颗树 且第二节点最多为两颗树
第三节点则根据第二节点的两颗树进行分支 且每个分支根据节点特征最多为2 则 第三节点最多存在 四颗树
且这四颗树中 两颗树存在于 第二节点的0树 两颗树存在于第二节点的1树
节点依次类推 1、2、4、8、16、32、64
完全二叉树
若设二叉树的深度为h，除第h层外，其它层 (1~h -1)的节点都为最大树
例: 深度为4 则深度在4之前所有节点全部存在
根据二进制算 则整棵树的节点最少为 1+2+4颗树 而第4层则为+2+4+1 ～ 1+2+4+8 颗树之间
完全二叉树的特点为:
1、叶子节点可以在最后一层或倒数第二层
2、最后一层的叶子节点一定集中在左部连续位置
3、完全二叉树严格按照层序编号
4、若一个节点为叶子节点，那么编号比其大的节点均为叶子节点
二叉树的相关性质
1、在非空的二叉树的i层上,至多有2的i-1次方个节点(i >= 1)
2、在深度为h的二叉树上最多有2的h-1次方个节点(h >= 1)
3、对于任何一颗非空的二叉树，如果叶子节点数为n0,深度数为2的节点个数为n2,则 n0 = n2 + 1
完全二叉树的性质
1、具有n个节点的完全二叉树的深度为log2n + 1
2、如果有一颗n个节点的完全二叉树的节点按层次序号编号，对其任意一层的节点i,(1 >= i >= n) 有一下三种可能
2.1 如果i = 1 则节点是二叉树的根,无双亲,如果i > 1,则其双亲节点为 i/2
2.2 如果2i > n 那么节点i没有左孩子,否则左孩子为2i
2.3 如果2i+1 > n 那么节点i没有右孩子,否则右孩子为2i + 1
