1概念
二叉树Binary Tree是n个结点的有限集合。它或者是空集n=0，或者是由一个根结点以及两颗互不相交、分别称为左子树和右子树的二叉树组成。
7 6 3 5 4 2 1根结点根结点的左子树根结点的右子树二叉树与普通有序树不同，二叉树严格区分左子和右子，即使只有一个子结点也要区分左右。
二叉树的树度数最大为2。
2性质*
1514 71312 6 31110 598 4 2 11二叉树的第k层上的结点最多个2k-1个
2深度为k的二叉树最多有2k-1个结点
Sn=a1(1-qn)/(1-q)=a1(1-2k)/(1-2)=(1-2k)/-1=2k-1
3在任意一颗二叉树中，树叶的数目比度数为2的结点数目多1。
N：结点的总数
N0：没有子结点的结点个数
N1：只有一个子结点的结点个数
N2：有两个子结点的结点个数
总结点 = 各节点数目之和 N = N0 + N1 + N2
总结点 = 所有子节点 + 根 N = 0 × N0 + 1 × N1 + 2 × N2 + 1
联立以上两式可得： N0 = N2 + 1
(网易)一棵二叉树有8个度为2的节点，5个度为1的节点，那么度为0的节点个数为 ( 9 )
满二叉树和完全二叉树
满二叉树：深度为k(k>=1)时结点个数为2k-1
1514 71312 6 31110 598 4 2 1完全二叉树：只有最下面两层有度数小于2的节点，且最下面一层的结点集中在最左边的若干位置上。
7 6 31110 598 4 2 13实现
二叉树的存储结构有两种，分为顺序存储和链式存储
3.1顺序存储
二叉树的顺序存储，指的是使用顺序表（数组）存储二叉树。需要注意，顺序存储只适用于完全二叉树。换句话说，只有完全二叉树才可以用顺序表存储。因此，如果我们想要顺序存储普通二叉树，就需要将其提前转换成完全二叉树。
普通二叉树转完全二叉树的方法很简单，只需给二叉树额外添加一些结点，将其"拼凑"成一个完全二叉树即可。
如图所示：
（1）普通二叉树的转化
左侧是普通二叉树，右侧是转化后的完全(满)二叉树。
完全(满)二叉树的顺序存储，仅需要从根结点开始，按照层次依次将树中结点存储到数组即可。
（2）完全二叉树示意图
存储图 2 所示的完全二叉树：
（3）完全二叉树存储状态示意图
存储由普通二叉树转化来的完全二叉树也是如此。
图 1 中普通二叉树在顺组中的存储状态如图：
（4）普通二叉树的存储状态
完全二叉树中结点按照层次并从左到右依次编号（123...），若结点i有左子，则其左子的结点编号为2*i，右子编号为2*i+1。
7 6 310 598 4 2 1设完全二叉树的结点数为n，某结点的编号为i。
当i>1时(不是根结点时)，有父节点，其编号为i/2。
当2*i <= n时，有左子，其编号为2*i，否则没有左子，没左子一定没右子，其本身为叶节点。
当2*i+1 <= n时，有右子，其编号为2*i+1，否则就没有右子。
3.1.1遍历*
先序：根----->左----->右
A B D H I E J C F K G
中序：左----->根----->右
H D I B E J A F K C G
后序：左----->右----->根
H I D J E B K F G C A
已知遍历结果如下，试画出对应的二叉树：
先序：A B C E H F I J D G K 根----->左----->右
中序：A H E C I F J B D K G 左----->根----->右
因为先序是根在最前面的，所以在先序中从前往后地取结点拿到中序中作为根，循环重复。
3.2链式存储
（1）普通二叉树示意图
链式存储此二叉树，从根结点开始，将各个结点以及其左右子的地址使用链表进行存储。
（2）二叉树链式存储结构示意图
3.2.1定义操作完全二叉树结构体*
结点结构体由三部分组成：
1指向左子结点的指针(Lchild)
2结点存储的数据（结点编号）
3指向右子结点的指针(Rchild)
（3）二叉树结点结构
3.2.2创建二叉树*
return rootL || Rmalloc return rootL || Rmalloc return rootL || Rmalloc 71312 6 31110 5 9 8 4 2 13.2.3先序遍历*
3.2.4中序遍历
3.2.5后序遍历
3.2.6层序遍历
队列的思想
不需要敲代码，看懂就行
