# 二叉树的性质
# 性质1
在二叉树的第i层上至多有
第i层上至少有1个结点。
# 性质2
深度为k的二叉树至多有
至少有k个结点。
# 性质3
对任何一颗二叉树，如果其叶子数为n1,度为2的结点数为n2，则n1=n2+1。
# 两种特殊形式的二叉树
# 满二叉树
一颗深度为k且有
个结点的二叉树称为满二叉树。 # 特点：
1.每一层上的结点数都是最大结点数。
2.叶子节点全部在最底层。
# 完全二叉树
深度为k的具有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应时，称之为完全二叉树。
# 注：
在满二叉树中，从最后一个结点开始，==连续==去掉任意个结点，即是一颗完全二叉树。
# 特点：
1.叶子只可能分布在层次最大的两层上。
2.对任一结点，如果其右子树的最大层次为i,则其左子树的最大层次必为i或i+1。
# 性质4
# 性质5
# 二叉树的存储结构
# 二叉树的顺序存储
# 实现:
按满二叉树的结点层次编号，依次存放二叉树中的数据元素。
//二叉树顺序存储表示 #define MAXTSIZE 100 Typedef TELemType SqBiTree[MAXTSZIE] SqBiTree bt;1
2
3
4# 一个非满二叉树且非完全二叉树的例子：
# 例题：
# 存储缺点
# 特点：
- 结点间关系蕴含在其存储结构中。
- 浪费空间，适用于满二叉树和完全二叉树。
# 二叉树的链式存储结构
# 结点结构：
# 存储结构的定义(实现)：
typedef struct BiNode{ TElemType data; struct BiNode *Ichild,*Rchild; }BiNode,*BiTree;1
2
3
4# 图例：
其中，^表示指针域为空。
在n个结点的二叉链表中，有n+1个空指针域。
分析：必有2n个链域。除了根结点外，每个结点有且仅有一个双亲，所以，只会有n-1个结点的链域存放指针，指向非空结点。2n-(n-1)=n+1。
# 三叉链表
# 存储结构的定义(实现)：
typedef struct TriTNode{ TelemType data; struct TriNode *Lchild,*Parent,*Rchild; }TriTNode,*TriTree1
2
3
4
# 遍历二叉树
# 遍历定义：
顺着某一条搜索路径巡防二叉树中的结点，使得每个结点==均被==访问一次，而且==仅被访问一次==（又称周游）
“访问”的范围很广，可以是对结点作各种处理，如：输出结点的信息，修改结点的数据值等，但要求这种访问不破坏原来的数据结构。
# 遍历目的：
得到树中所有结点的一个线性排列。
# 遍历用途：
它是树结构增删改查和排序运算的前提，是二叉树一切运算的基础和核心。
- 遍历方法
依次遍历二叉树中的三个组成部分，便是遍历了整个二叉树。
假设：L：遍历左子树 D：访问根结点 R：遍历右子树
则遍历二叉树的方案有：
DLR DRL LDR LRD RDL RLD 六种
若规定==先左后右==，则只有三种情况：
DLR——先（根）序遍历
LDR ——中（根）序遍历
LRD——后（根）序遍历
# 1.遍历二叉树算法描述
先序遍历二叉树 中序遍历二叉树 后序遍历二叉树 若二叉树为空，则空操作；否则
（1）访问根结点
（2）先序遍历左子树
（3）先序遍历右子树若二叉树为空，则空操作；否则
（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树若二叉树为空，则空操作；否则
（1）后序遍历左子树
（2）后序遍历右子树
（3）访问根结点由二叉树的递归定义可知，遍历左子树和遍历右子树可如遍历二叉树一样==“递归”==进行。
# 先序遍历的操作定义：
先序遍历的顺序为ABC，遍历到子树为空结束。
顺序为ABELDHMIJ
# 先序遍历的操作定义：
中序遍历的顺序为BAC
顺序为ELBAMHIDJ
# 后序遍历的操作定义：
顺序为BCA
顺序为LEBMIHJDA
# 例题：
先序：ABDGCEHF
中序：DGBAEHCF
后序：GDBHEFCA
先序：-+axb-cd/ef
表达式的==前缀表示===（波兰式）
中序：a+bxc-d-e/f
==中缀表示==
后序：abcd-x+ef/-
==后缀表示==（逆波兰式）
# 2.根据遍历序列确定二叉树
- 若二叉树中的结点的值均不相同，则二叉树结点的先序序列、中序序列、后序序列都是唯一的。
- 由二叉树的先序序列和中序序列、或由二叉树的中序序列和后序序列都可以确定唯一一棵二叉树。
# 例题：
中序的话，知道了根结点A的位置，那么一定能确定CDBFE是A的左子树，IHGJ是A的右子树。
# 总结：
前序和后序判断根结点，中序判断左右结点。
# 遍历的算法实现
# 先序遍历
若二叉树为空，则空操作；否则
（1）访问根结点
（2）先序遍历左子树
（3）先序遍历右子树Status PreOrderTraverse(BiTree){ if(T==NULL)return OK; else{ visit(T);//访问根结点 PreOrderTraverse(T->Lchild);//递归遍历左子树 PreOrderTraverse(T->Rchild);//递归遍历右子树 } }1
2
3
4
5
6
7
8其中的访问根结点：例如，输出根结点 printf(“%d\t”,T->data)
中序遍历
若二叉树为空，则空操作；否则
（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树Status InOrderTraverse(BiTree){ if(T==NULL)return OK; else{ InOrderTraverse(T->Lchild);//递归遍历左子树 visit(T);//访问根结点 InOrderTraverse(T->Rchild);//递归遍历右子树 } }1
2
3
4
5
6
7
8后序遍历
若二叉树为空，则空操作；否则
（1）后序遍历左子树
（2）后序遍历右子树
（3）访问根结点Status PostOrderTraverse(BiTree){ if(T==NULL)return OK; else{ PostOrderTraverse(T->Lchild);//递归遍历左子树 PostOrderTraverse(T->Rchild);//递归遍历右子树 visit(T);//访问根结点 } }1
2
3
4
5
6
7
8# 遍历算法的分析
如果去掉输出语句，==从递归的角度看，三种算法是完全相同的==。或者说这三种算法的访问路径是相同的，只是访问结点的时机不同。
从虚线的出发点到终店的路径上，每个结点经过3次。
- 第一次经过时访问：先序遍历
- 第二次经过时访问：中序遍历
- 第三次经过时访问：后序遍历
时间效率：O(n) //每个结点只访问一次
空间效率：O(n) //栈占用的最大辅助空间
# 二叉树遍历的非递归算法
# 中序遍历非递归算法
关键：在中序遍历过某结点的整个左子树后，如何找到该结点的根以及右子树。
# 基本思想：
- 建立一个栈
- 根结点进栈，遍历左子树
- 根结点出栈，输出根结点，遍历右子树
Status InOrderTraverse(BiTree T){ BiTree T; InitStack(S); p=T; while(p||!StackEmpty(S)){ if(p){ Push(S,p); p=p->Lchild; }else{ Pop(S,q); printf("%c\n",q->data); p=q->Rchild; } } return OK; }1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17# 二叉树的层次遍历
对于一棵二叉树，从根结点开始，按从上到下、从左到右的顺序访问每一个结点。
每一个结点仅仅访问一次。
层次遍历结果：abfcdgeh
# 算法设计思路：
- 将根结点进队
- 队不空时循环：从队列中出列一个结点*p，访问它
- 若它有左孩子结点，将左孩子结点进队
- 若它有右孩子结点，将右孩子进队
typedef struct{ BTNode data[MaxSize];//存放队中元素 int front,rear;//队头和队尾指针 }SqQueue;//顺序循环队列类型1
2
3
4void LevelOrder(BTNode *b){ BTNode *p; SqQueue *qu; initQueue(qu);//初始化队列 enQueue(qu,b);//根结点指针入队 while(!QueueEmpty(qu)){//队不为空，则循环 deQueue(qu,p);//出队结点p printf("%c",p->data);//访问结点p if(p->Lchild!=NULL) enQueue(qu,p->Lchild);//有左孩子则将其入队 if(p->Rchild!=NULL) enQueue(qu,p->Rchild);//有右孩子则将其入队 } }1
2
3
4
5
6
7
8
9
10
11
12
13
14# 二叉树遍历算法的应用
# 二叉树的建立
按先序遍历序列建立二叉树的二叉链表
例：已知先序序列为：ABCDEGF
- 从键盘输入二叉树的结点信息，建立二叉树的存储结构
- 在建立二叉树的过程中按照二叉树先序方式建立
Status CreateBiTree(BiTree & T){ scanf("%c",&ch); if(ch=="#") T=NULL; else{ if(!(T=(BiTNode*)malloc(sizeof(BiTNree)))){ exit(STACKOVERFLOW);//T = new BiTNode; } T->data=ch;//生成根结点 CreateBiTree(T->Lchild);//构造左子树 CreateBiTree(T->Rchild);//构造右子树 } return OK; }1
2
3
4
5
6
7
8
9
10
11
12
13
14
15# 复制二叉树
如果是空数，递归结束
否则，申请新结点空间，复制根结点
- 递归复制左子树
- 递归复制右子树
int Copy(BiTree T,BiTree &newT){ if(T==NULL) return 0; else{ newT = new BiTNode; newT->data=T->data; Copy(T->Lchild,newT->Lchild); Copy(T->Rchild,newT->Rchild); } }1
2
3
4
5
6
7
8
9
10
# 计算二叉树深度
如果是空数，则深度为0
否则，递归计算左子树的深度记为m，递归计算右子树的深度记为n，二叉树的深度则为m与n的较大者加1
int Depth(BiTree T){ int m,n; if(T==NULL) return 0; else{ m=Depth(T->Lchild); n=Depth(T->Rchild); if(m>n){ return m+1; }else{ return n+1; } } }1
2
3
4
5
6
7
8
9
10
11
12
13
14# 计算二叉树结点总数
如果是空树，则结点个数为0
否则，结点个数为左子树的结点个数+右子树的结点个数+1
int NodeCount(BiTree T){ if(T==NULL){ return 0; }else{ return NodeCount(T->Lchild)+NodeCount(T->Rchild)+1; } }1
2
3
4
5
6
7
8# 计算叶子结点个数
如果是空数，则个数为0
否则，二叉树个数=左子树个数+右子树个数
int LeadCount(BiTree T){ if(T==NULL){ return 0; }else{ return LeadCount(T->Lchild)+LeaderCount(T->Rchild); } }1
2
3
4
5
6
7# 线索二叉树
# 问题：
为什么要研究线索二叉树？
当用二叉链表作为二叉树的存储结构时，可以很方便地找到某个结点的左右孩子，但是一般情况下，无法直接找到该结点在某种遍历序列中的前驱和后继结点。
# 提出的问题：
如何寻找特定遍历序列中二叉树结点的前驱和后继？
# 解决的方法:
- 通过遍历寻找——费时间
- 再增设前驱后继指针域——增加存储负担
- ==利用二叉链表中的空指针域==
# 回顾：二叉树链表中空指针域的数量：
在n个结点的二叉链表中，有n+1个空指针域。
分析：必有2n个链域。除了根结点外，每个结点有且仅有一个双亲，所以，只会有n-1个结点的链域存放指针，指向非空结点。2n-(n-1)=n+1。
# 利用二叉链表中的空指针域：
如果某个结点的左孩子为空，那么这个左孩子指针域改为指向其前驱；如果右孩子为空，那么右孩子指针域改为指向其后继——==这种改变指向的指针称为“线索”==
加上了线索的二叉树称为==线索二叉树==
对
对二叉树按某种遍历次序使其变为线索二叉树的过程叫线索化
# 图例：
为区分Lchild和Rchild指针到底是指向孩子的指针还是指向前驱或者后继，对二叉链表中每个结点增设两个标识域ltag和rtag，并约定：
ltag=0 Lchild指向该结点的左孩子
ltag=1 Lchild指向前驱
rtag=0 Rchild指向右孩子
rtag=1 Rchild指向后继
typedef struct BiThrNode{ int data; int ltag,rtag; struct BiThrNode* Lchild,*Rchild; }BiThrNode,*BiThrTree;1
2
3
4
5# 先序线索二叉树
# 先序线索二叉树
# 后序线索二叉树
