特殊二叉树
满二叉树
所有分支节点都有左右子树，并且叶子节点在同一层
完全二叉树
对于一个树高为h的二叉树，如果其第0层至第h-1层的节点都满
如果最下面一层节点不满，则所有的节点在左边的连续排列，空位都在右边
层次遍历如果遇到空节点，队列中还有子树不是完全二叉树
二叉树性质
性质一：在二叉树的第i层最多有2^(i-1)的结点（i>=1）
最多结点的二叉树是满二叉树，除了叶结点，所有结点的度都为2，所以，第i层最多有2^(i-1)个结点
性质2：深度为k的二叉树至多有2^k-1个结点（k>=1）
由性质1可以求出每层的结点数，则k（k>=1）层二叉树总共节点数为：n = 2^0 + 2^1 + ... 2^(k-1)=1*(1-2^k)/(1-2) = 2^k - 1
性质3：对任何一颗二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1
二叉树的总结点数为：n = n0 + n1 + n2（n0为叶结点，n1为度为1的结点数，n2为度为2的结点数）；
那么结点数为n的二叉树有多少条连接线呢？很明显每个结点，<font color="#c41230">除了根结点都有指向连接线</font>，所以，结点数为n的二叉树的总连接线为n-1；
从一个结点的度来算，度为1的结点会有1条连接线，连接子结点；
度为2的结点会有2连接线，连接子结点；
根结点没有双亲结点，所以没有连向根结点的连接线，那么有：n-1 = 1*n0 + 2*n2；
和第一条方程式联合可得：n0=n2+1。
性质4：具有n个结点的完全二叉树的深度为⎣log2(n)⎦ + 1（⎣x⎦表示不大于x的最大整数，取下界）
设置有n个结点的完全二叉树的深度为k，则：<br>2^(k-1)-1< n <= 2^k-1<br>
因为k是整数，所以：<br>2^(k-1)<= n < 2^k
取对数得：<br>k-1<=log2(n)<k，即：k<=log2(n)+1并且k>log2(n)<br>所以：k=|log2(n)| + 1
性质5：如果对一颗有n个结点的完全二叉树（其深度为|log2(n)| + 1）的结点按层编号（从第1层到第|log2(n) + 1|层，每层从左到右），对任一结点i（1<= i <= n）有
如果i=1，则结点i是二叉树的根结点，无双亲；如果i>1，则其双亲是结点|i/2|（取下界）。
如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i
如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1
存储结构
顺序结构
由于二叉树每个结点最多只有2个子树，并且左右子树是有顺序的，所以，可以使用数组直接存储
没有节点的位置存为空，直到最后一个节点
链式结构
每个节点除数据元素外，包含一个指向左子树的指针和指向右子树的指针
遍历
二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问有且仅有一次
前序
若二叉树为空，则返回；否则，先遍历根结点，然后遍历左子树，再遍历右子树。
中序
如果二叉树为空，则返回；否则，从根结点开始，先遍历左子树，然后是根结点，左后是右子树。
后序
如果二叉树为空，则返回；否则，先遍历左子树，然后遍历右子树<br>
层序
如果二叉树为空，则返回；否则，从树的第一层，根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序逐个结点访问。
线索二叉树
加上向前驱和后续的指针称线索二叉树
https://blog.csdn.net/u014492609/article/details/40477795#
如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后续，<br>那么采取线索二叉链表的存储结构就是非常不错的选择<br>
前驱
后驱
