TD05-二叉树
一、二叉树
1、与树相似，二叉树也是递归的形式定义
2、二叉树是有序树，其左、右子树颠倒，则成为另一棵不同的二叉树（有5种基本形态—空二叉树、只有根结点、只有左子树、只有右子树、左右子树都有）
二叉树与度为2的有序树的区别：
1 度为2的树至少有3个结点，二叉树可以为空
2 度为2的有序树的孩子的左右次序是相对的（若某个结点只有一个孩子，则这个孩子无需区分左右次序）
二叉树的结点次序是确定的，在左就是左，在右就是右
几种特殊二叉树：
满二叉树：高为h，含有2^h -1个结点的二叉树。
特点：
编号为i的结点，若有双亲，双亲为i/2（向下取整）；若有左孩子，左孩子为2i，若有右孩子，右孩子为2i+1。
完全二叉树：高度为h，n个结点的二叉树，且每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应。
特点：
1、若 i <= n/2 (向下取整)，则结点i为分支结点；
2、叶子结点只能在最大的两层中出现，且在左边位置；
3、度为1的结点最多有一个，且该结点只有左孩子；
若某编号为i的结点为叶子结点或只有左孩子，则编号大于i的结点都是叶子结点；
4、若n为奇数，则每个分支点都有左孩子和右孩子；若n为偶数，编号最大的分支结点没有右孩子，其余分支结点都有左右孩子。
二叉排序树：左子树上 所有结点的关键字均小于根结点的关键字
二、二叉树性质
1、 n0=n2+1
2、 非空二叉树第k层至多2^(k-1)个结点
3、 高度h的二叉树至多有2^h -1个结点
4、 i>1时，双亲编号 i/2(向下取整)；
2i<=n时，结点i左孩子 2i;
2i+1<=n时，结点右孩子2i+1;
结点i所在层次（深度）为log2i(向下取整)+1
5、 具有n个结点的完全二叉树高度为log2(n+1)(向上取整)或log2n(向下取整+1)
三、二叉树的存储结构
1、顺序存储
二叉树的顺序存储用一组地址连续的存储单元依次自上而下、自左向右存储完全二叉树。
完全二叉树和满二叉树 采用顺序存储合适，树中结点的序号可以唯一反应结点之间的逻辑关系；一般二叉树需要添加一些并不存在的空结点。
//二叉树的顺序存储
#define MAXSIZE 100
typedef TElemtype SqBiTree[MAXSIZE];
SqBiTree bt;
2、链式存储
由于顺序存储空间利用率低，二叉树一般采用链式存储结构。链表结点表示存储二叉树中的每个结点（数据域data，左指针lchild，右指针rchild）
//二叉树链式存储结构
typedef struct BiTNode {
TElemtype data; //结点数据域
struct BiTNode* lchild, * rchild;
}BiTNode,*BiTree;
含有n个结点的二叉链表中，含有n+1个空链域
四、二叉树的遍历和线索二叉树
1、二叉树的遍历（递归算法）
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);
}
}
时间复杂度O(n)；
递归工作栈的深度等于树的深度，所以，最坏情况n个结点深度为n，最坏情况空间复杂度O(n)。
2、二叉树的遍历（非递归算法）
中序遍历：
//中序遍历非递归算法
void InOrder2(BiTree T) {
InitStack(S); //初始化栈s
BiTree p = T; //p遍历指针
while (p || !IsEmpty(S)) { //栈不空或p不空 循环
if (p) {
Push(S, p); //进栈
p = p->lchild; //左孩子不空，一路左走
}
else
{
Pop(S, p); //栈顶元素出栈
visit(p); //访问栈结点
p = p->rchild; //走向右子树
}
}
}
先序遍历：
思想类似，把访问结点操作放在入栈操作前
//先序遍历非递归算法
void PreOrder2(BiTree T) {
InitStack(S); //初始化栈s
BiTree p = T; //p遍历指针
while (p || !IsEmpty(S)) { //栈不空或p不空 循环
if (p) {
visit(p); //访问栈结点
Push(S, p); //进栈
p = p->lchild; //左孩子不空，一路左走
}
else
{
Pop(S, p); //栈顶元素出栈
p = p->rchild; //走向右子树
}
}
}
后序遍历：
//后序
void PostOrder2(BiTree T) {
InitStack(S);
BiTree p = T;
BiTree r = NULL;
while (p || !IsEmpty(S)) {
if (p) {
Push(S, p);
p = p->lchild;
}
else {
GetTop(S, p);
if (p->rchild && p->rchild != r) {
p = p->rchild;
Push(S, p);
p = p->lchild;
}
else {
Pop(S, p);
visit(p->data);
r = p;
p = NULL;
}
}
}
}
3、二叉树的层次遍历
借助队列
算法思路：
根结点进队；
队不空循环：队列出一个结点p，访问
//层次遍历
void LevelOrder(BiTree T) {
SqQueue* 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);
}
}