1.特殊的二叉树
（1）满二叉树
一棵树高度为h，且含有2^h-1个结点的二叉树。
特点：只有最后一层有叶子结点；
不存在度为1的结点；
按层序从1开始编号，结点i的左孩子为20i，右孩子为2i+1；结点i的父节点为[i/2]（向下取整）。
（2）完全二叉树
当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树。
特点：只有最后两层可能有叶子结点；
最多只有一个度为1的结点；
按层序从1开始编号，结点i的左孩子为20i，右孩子为2i+1；结点i的父节点为[i/2]（向下取整）；
i<=[n/2]（向下取整）为分支结点，i>[n/2]（向下取整）为叶子结点。
（3）二叉排序树
一个二叉树或者是空二叉树，或者是具有如下性质的二叉树：
左子树上所有结点的关键字均小于根结点的关键字；
右子树上所有结点的关键字均大于根结点的关键字。
左子树和右子树又是一颗二叉排序树。
（4）平衡二叉树
树上任一结点的左子树和右子树的深度之差不超过1。
平衡二叉树能有更高的搜索效率。
2.二叉树的性质
（1）设非空二叉树中度为0、1和2的结点个数分别为n0、n1、n2，则n0=n1+1（叶子结点比二分支结点多一个）
（2）二叉树第i层至多有2^(i-1)个结点(i>=1)
m叉树第i层至多有m^(i-1)个结点(i>=1)
（3）高度为h的二叉树至多有2^h-1个结点（满二叉树）
高度为h的m叉树至多有(m^h-1)/(m-1)个结点
等比数列的求和公式：a(1-qn)/(1-q)
3.完全二叉树的性质
（1）具有n个（n>0）结点的完全二叉树的高度h为[log2(n+1)]（向上取整）或[log2n]+1（向下取整）
（2）对于完全二叉树，可以由结点数n推出度为0、1和2的结点个数为n0、n1和n2。
完全二叉树最多只有一个度为1的结点，即n1=0或1
n0=n2+1->n0+n2一定是奇数
若完全二叉树有2k（偶数）个结点，则必有n1=1，n0=k，n2=k-1；
若完全二叉树有2k-1（奇数）个结点，则必有n1=0，n0=k，n2=k-1.
4.二叉树的存储结构
（1）顺序存储
#define MaxSize 100
struct TreeNode {ElemType value; //结点中的数据元素bool isEmpty; //结点是否为空
};TreeNode t[MaxSize];//初始化时所有结点标记为空
for(int i=0;i<MaxSize;i++){t[i].isEmpty = true;
}定义一个长度为MaxSize的数组t，按照从上至下、从左至右的顺序依次存储完全二叉树中的各个结点。
（2）链式存储
struct ElemType{int value;
};//二叉树的结点(链式存储)
typedef struct BiTNode{ElemType data; //数据域struct BiTNode *lchild,*rchild; //左、右孩子指针
}BiTNode,*BiTree;//定义一颗空树
BiTree root = NULL;//插入根节点
root = (BiTree)malloc(sizeof(BiTNode));
root->data = {1};
root->lchild = NULL;
root->rchild = NULL;//插入新结点
BiTNode * p = (BiTNode *)malloc(sizeof(BiTNode));
p->data = {2};
p->lchild = NULL;
p->rchild = NULL;
root->lchild = p; //作为根结点的左孩子可以根据实际需要定义三叉链表，方便找父节点。
typedef struct BitNode{ElemType data; //数据域struct BiTNode *lchild,*rchild; //左、右孩子指针struct BiTNode *parent; //父节点指针
}BiTNode,*BiTree;5.二叉树的先中后序遍历
（1）先序遍历
//先序遍历
void PreOrder(BiTree T){if(T!=NULL){visit(T); //访问根结点PreOrder(T->lchild); //递归遍历左子树PreOrder(T->rchild); //递归遍历右子树}
}（2）中序遍历
//中序遍历
void InOrder(BiTree T){if(T!=NULL){InOrder(T->lchild); //递归遍历左子树Visit(T); //访问根结点InOrder(T->rchild); //递归遍历右子树}
}（3）后序遍历
//后序遍历
void PostOrder(BiTree T){if(T!=NULL){PostOrder(T->lchild); //递归遍历左子树PostOrder(T->rchild); //递归遍历右子树Visit(T); //访问根结点}
}6.求树的深度（应用）
int treeDepth(BiTree T){if(T == NULL){return 0;}else{int l = treeDepth(T->lchild);int r = treeDepth(T->rcjild);//树的深度 = Max(左子树深度，右子树深度)+1return l>r ? l+1 : r+1;}
}7.二叉树的层次遍历
算法思想：
①初始化一个辅助队列
②根结点入队
③若队列非空，则队头结点出队，访问该结点，并将左、右孩子插入队尾（如果有的话）
④重复③直至队列为空
//二叉树的结点（链式存储）
typedef struct BiTNode{char data;struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;//链式队列结点
typedef struct LinkNode{BiTNode * data; //保存结点指针struct LinkNode *next;
}LinkNode;typedef struct{LinkNode *front,*rear; //队头队尾
}LinkQueue;//层序遍历
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); //右孩子入队}
}
8.由遍历序列构造二叉树
只给出一颗二叉树的前/中/后/层序遍历序列中的一种，不能唯一确定一颗二叉树。
若要构造二叉树必须得知中序遍历序列。
9.线索二叉树
（1）线索二叉树结构
//线索二叉树结点
typedef struct ThreadNode{ElemType data;struct ThreadNode *lchild,*rchild;int ltag,rtag; //左、右线索标志
}ThreadNode,*ThreadTree;对应tag位为0时，表示指针指向其孩子；
对应tag位为1时，表示指针是“线索”。
将n+1个空链域连上前驱、后继
（2）土方法找中序前驱
//辅助全局变量，用于查找结点p的前驱
BiTNode *p; //p指向目标结点
BiTNode * pre=NULL; //指向当前访问结点的前驱
BiTNode * final=NULL; //用于记录最终结果//中序遍历
void InOrder(BiTree T){if(T!=NULL){InOrder(T->lchild); //递归遍历左子树visit(T); //访问根结点InOrder(T->rchild); //递归遍历右子树}
}//访问结点q
void visit(BiTNode * q){if(q==p) //当前访问结点刚好是结点pfinal = pre; //找到p的前驱elsepre = q; //pre指向当前访问的结点
}（3）中序线索化
//全局变量pre,指向当前访问结点的前驱
ThreadNode *pre = NULL;//中序线索化二叉树T
void CreateInThread(ThreadTree T){pre = NULL; //pre初始为NULLif(T!=NULL){ //非空二叉树才能线索化InThead(T); //中序线索化二叉树if(pre->child==NULL)pre->rtag=1; //处理遍历的最后一个结点}
}//线索二叉树结点
typedef struct ThreadNode{ElemType data;struct ThreadNode *lchild,*rchild;int ltag,rtag; //左、右线索标志
}ThreadNode,*ThreadTree;//中序遍历二叉树，一边遍历一边线索化
void InThread(ThreadTree T){if(T!=NULL){InThread(T->lchild); //中序遍历左子树visit(T); //访问根节点InThread(T->rchild); //中序遍历右子树}
}void visit(ThreadNode *q){if(q->lchild==NULL){ //左子树为空，建立前驱线索q->lchild=pre;q->ltag=1;}if(pre!=NULL&&pre->rchild==NULL){pre->rchild=q; //建立前驱结点的后继线索pre=q;}
}（4）先序线索化
先序线索化有转圈问题，需要特别注意。
//全局变量pre，指向当前访问结点的前驱
ThreadNode *pre=NULL;//先序线索化二叉树T
void CreatePreThread(ThreadTree T){pre=NULL; //pre初始为NULLif(T!=NULL){ //非空二叉树才能线索化PreThread(T); //先序线索化二叉树if(pre->rchild==NULL)pre->rtag=1; //处理遍历的最后一个结点}
}//先序遍历二叉树，一边遍历一边线索化
void PreThread(ThreadTree T){if(T!=NULL){visit(T); //先处理根结点if(T->ltag==0) //lchild不是前驱线索PreThread(T->rchild);PreThread(T->rchild);}
}void visit(ThreadNode *q){if(q->lchild==NULL){ //左子树为空，建立前驱线索q->lchild=pre;q->ltag=1;}if(pre!=NULL&&pre->rchild==NULL){pre->rchild=q; //建立前驱结点的后续线索pre->rtag=1;}pre=q;
}（5）后序线索化
//全局变量pre，指向当前访问结点的前驱
ThreadNode *pre=NULL;//后序线索化二叉树T
void CreatePostThread(ThradTree T){pre=NULL; //pre初始化为NULLif(T!=NULL){PostThread(T); //后序线索化二叉树if(pre->rchild==NULL)pre->rtag=1; //处理遍历的最后一个结点}
}//后序遍历二叉树，一边遍历一边线索化
void PostThread(ThreadTree T){if(T!=NULL){PostThread(T->lchild); //后序遍历左子树PostThread(T->rchild); //后序遍历右子树visit(T); //访问根结点}
}void visit(ThreadNode *q){if(q->lchild==NULL){ //左子树为空，建立前驱线索q->lchild=pre;q->ltag=1;}pre=q;
}（6）中序线索二叉树找中序后继
在中序二叉树中找到指定结点*p的中序后继next
①若p->rtag==1,则next=p->rchild
②若p->rtag==0
next=p的右子树中最左下结点
//找到以P为根的字树中，第一个被中序遍历的结点
ThreadNode *Firstnode(ThreadNode *p){//循环找到最左下结点（不一定是叶节点）while(p->ltag==0)p=p->lchild;return p;
}//在中序线索二叉树中找到结点p的后继结点
ThreadNode *Nextnode(ThreadNode *p){//右子树中最左下结点if(p->rtag==0)return Firstnode(p->rchild);else return p->rchild; //rtag==1直接返回后继线索
}//对中序线索二叉树进行中序遍历（利用线索实现的非递归算法）
void Inorder(ThreadNode *T){for(ThreadNode *p=Firstnode(T);P!=NULL;p=Nextnode(p))visit(p);
}（7）中序线索二叉树找中序前驱
在中序线索二叉树中找到指定结点*p的中序前驱pre
①若p->ltag==1，则pre = p->lchild
②若p->ltag==0
pre = p的左子树中最右下结点
//找到以p为根的子树中，最后一个被中序遍历的结点
ThreadNode *Lastnode(ThreadNode *p){//循环找到最右下结点（不一定是叶结点）while(p->rtag==0) p=p->rchild;return p;
}//在中序线索二叉树中找到结点p的前驱结点
ThreadNode *Prenode(ThreadNode *p){//左子树中最右下结点if(p->ltag==0)return Lastnode(p->lchild);else return p->lchild; //ltag==1直接返回前驱线索
}//对中序线索二叉树进行逆向中序遍历
void RevInorder(ThreadNode *T){for(ThreadNode *p=Lastnode(T);p!=NULL;p=Prenode(p))visit(p);
}（7）先序线索二叉树
①找先序后继
若p有左孩子，则先序后继为左孩子，若p没有左孩子，则先序后继为右孩子。
②找先序前驱
先序遍历中，左右子树中的结点只可能是根的后继，不可能是前驱。
改用三叉链表可以找到父节点：
如果能找到p的父节点，且p是左孩子，p的父节点即为其前驱；
如果能找到p的父节点，且p是右孩子，其左兄弟为空，p的父结点即为其前驱；
如果能找到p的父节点，且p是右孩子，其左兄弟非空，p的前驱为左兄弟子树中最后一个被先序遍历的结点；
如果p是根结点，则p没有先序前驱。
（8）后序线索二叉树
①找后序前驱
若p有右孩子，则后序前驱为右孩子；
若p没有右孩子，则后序前驱为左孩子。
②找后序后继
后序遍历中，左右子树中的结点只可能是根的前驱，不可能是根的后继。
改用三叉链表可以找到父节点：
如果能找到p的父节点，且p是右孩子，p的父节点即为其后继；
如果能找到p的父节点，且p是左孩子，其右兄弟为空，p的父节点即为其后继；
如果能找到p的父节点，且p是左孩子，其右兄弟非空，p的后继为右兄弟子树中第一个被后序遍历的结点；
如果p是根结点，则p没有后序后继。
