(此文为王道数据结构学习笔记，只供个人后续复习使用，若有错误，还望指出我改正，谢谢）
二叉树的五种状态：
空二叉树，只有左子树，只有右子树，只有根结点，左右子树都有
满二叉树与完全二叉树：
?
?完全二叉树为去较大号结点的满二叉树，满二叉树为特殊完全二叉树。完全二叉树度为 1 的结点只有最多一个。
二叉排序树：
左子树的结点均小于根结点，右子树的结点均大于根结点，同样的，左右子树各自又为二叉排序树
插入新结点时从根结点开始进行判断：如果小于该结点向左走，如果大于根结点向右走，直到找到空位。
平衡二叉树：树上任意结点的左子树和右子树的深度只差不超过一，平衡二叉树的在同等数量元素下，深度更低，搜索效率更高。
二叉树常考性质：
设非空二叉树的结点度数为0，1，2的数量分别为N0，N1，N2，则N0=N2+1；
高度为 h 的完全二叉树的结点数：最多为满二叉树情况，最少为最低层仅有一个叶子结点
对于完全二叉树，知道结点数，即可知道N0，N1，N2
二叉树的顺序存储
编号由如此规律：
i 的左孩子 2i ，i 的右孩子 2i+1，i 的父结点 i/2 （ i 从 1 开始）
高度为 h 的二叉树，需要用 2的h次方-1 大小空间实现顺序存储，如若不是完全二叉树，则会产生大量空结点，较为浪费空间
#define MaxSize 100
struct TreeNode{
ElemType value; //结点数据
bool isEmpty;//结点是否为空
};
TreeNode t[MaxSize];
for (int i=0;i<MaxSize;i++){
t[i].isEmpty=true;//初始令所有结点指示为空
}二叉树的链式存储
用链式存储，每个结点存储其左右孩子指针和数据域（二叉链表）：方便寻找一个结点的左右孩子，但不方便寻找父结点，如需寻找父结点，则需要从根结点进行遍历。
typedef struct BiTNode{
ElemType data; //数据域
struct BiTNode *lchild, *rchild;//左右孩子指针
}BiTNode, *BiTree;用链式存储，每个结点存储其左右孩子指针、父结点指针和数据域（三叉链表）
typedef struct BiTNode{
ElemType data; //数据域
struct BiTNode *lchild, *rchild;//左右孩子指针
struct BiTNode *parent; //父结点指针
}BiTNode, *BiTree;遍历
先序遍历：根左右
中序遍历：左根右
后序遍历：左右根
对于三层满二叉树（结点A BC DEFG）
先序遍历：ABDECFG
中序遍历：DBEAFCG
后序遍历：DEBFGCA
先序遍历：
void PreOrder(BiTree T){
if(T!=NULL){
visit(T); //访问根结点
PreOrder(T->lchild);//遍历左子树
PreOrder(T->rchild);//遍历右子树
}
}?中序遍历：?
void InOrder(BiTree T){
if(T!=NULL){
PreOrder(T->lchild);//遍历左子树
visit(T); //访问根结点
PreOrder(T->rchild);//遍历右子树
}
}后序遍历：?
void PostOrder(BiTree T){
if(T!=NULL){
PreOrder(T->lchild);//遍历左子树
PreOrder(T->rchild);//遍历右子树
visit(T); //访问根结点
}
}二叉树的层序遍历：（队列辅助层序遍历）
思路：
1。初始化一个辅助队列；
2。根结点入队；
3。若队列非空，则队头结点出队，访问该结点，并将其左右孩子结点插入队尾；
4。重复 3 直到队列为空
void LevelOrder(BiTree T){
LinkQueue Q;
InitQueue(Q); //初始化辅助队列
BiTree p:
EnQueue(Q,T); //根结点入队
while(!IsEmpty(Q)){ //队列不为空则开始循环
DeQueue(Q,p); //队头出队
visit(p); //访问队头
if(p->lchild!=NULL)
EnQueue(Q,p->lchild);//左孩子入队
if(p->rchild!=NULL)
EnQueue(Q,p->rchild);//右孩子入队
}
}由遍历序列构造二叉树
如果只有一个二叉树的前/中/后/层的一种，不能确定一颗二叉树，需要
前+中序遍历二叉树
后+中序遍历二叉树
层+中序遍历二叉树
线索二叉树（线索链表）
先/中/后序线索二叉树：
如果一个结点左右孩子指针并未指向某一结点（即空链域），可以按照先/中/后序遍历的顺序，将其左孩子指向前驱，右孩子指向后继，这些指针成为前驱线索和后继线索。
typedef struct ThreadNode{
ElemType data; //数据域
struct ThreadNode *lchild, *rchild;//左右孩子指针
int ltag, rtag; //左右线索标志，置为1时代表为线索指针
}ThreadNode， *ThreadTree;二叉树的线索化：
中序线索化：
