本文章只是本人个人学习笔记，如有错误，欢迎批评指正
以下是本人自学的视频
概要：非线性结构5.1 树
树(Tree)——n个结点。递归定义：由根（Root）和子树（）组成
树的其他表现形式
5.1.2 树的基本术语
5.1.3 树结构和线性结构的比较3
5.2 树——二叉树
二叉树————结点的度最多为2的树，孩子分别叫左子树、右子树，孩子的顺序不能互换
二叉树可以是空集合，且左右子树可以为空树
为什么要研究二叉树：一般的树很复杂，而二叉树是最简单的树，规律性强。任何树都可与二叉树相互转换
注意：二叉树与树的最主要差别（也因其而是两者概念不同）————即使只有一个孩子，二叉树也要定义该孩子是左子树还是右子树；看下图例子
5.2.2 二叉树的5种基本形态
5.2.3 二叉树的性质
性质1：二叉树在第
层最多有
个结点，最少有 1 个结点
性质2：深度为
的二叉树，最多有
个结点，最少有
个结点。
性质3：二叉树的总边数
，总结点数
，度2结点数
，度1结点数
，度0结点(叶子)数
。
总边数
总结点数
叶子数 与 度2结点数的关系：
5.2.4 特殊的二叉树——满二叉树、完全二叉树
5.2.4.1 满二叉树
满二叉树：所有结点都在的树。即深度
，有
个结点的二叉树
满二叉树特点：
5.2.4.2 完全二叉树
完全二叉树：结点编号和同深度的满二叉树相同的二叉树。满二叉树是特殊的完全二叉树
完全二叉树特点：
完全二叉树的性质
具有
个结点的完全二叉树的深度
。（补充:
：表示不大于x的最大整数，即floor(x)）完全二叉树的编号关系：
结点编号
，则其双亲结点编号为
，左孩子编号
,右孩子编号
5.2.5 二叉树的顺序存储
1.按编号存储：从上到下，从左到右java二叉树的遍历算法，表示数组下标
2.注！！！：即使子树为空，也为其编号，但是该数组位置存储空。目的就是使数组下标与树编号一一对应，可根据数组恢复二叉树原样
3.二叉树顺序存储类型定义
#define MAXTSIZE 100
4.二叉树顺序存储缺点：对于非满二叉树，浪费空间大。适合完全二叉树
5.2.6 二叉树的链式存储——二叉链表
1.二叉链表
2.二叉树链式存储类型定义
typedef struct BiNode {
TElemType data; // 数据域
struct BiNode *Ichild, *rchild; // 指针域:左右孩子指针
3.补充：三叉链表
新增个指针域：指向前驱
5.3 遍历二叉树
遍历————顺着一条路径巡访二叉树的结点，每个结点访问一次
二叉树的遍历通过递归实现
5.3.2 三种遍历方式
子树按照：从左到右遍历
将二叉树拆分成 逐级递减的二叉树，依次执行上述操作
执行到下一结点后都要重新开始执行3个操作，而不是直接访问该结点
1.先序遍历——根左右
2.中序遍历
右图：将BEL是A的左子树，所以BEL访问后才A才右子树；同样，E的左子树访问完后（为空），才E，才右子树L；
3.后序遍历
右图：二叉树拆分
拆分A：BEL——A——DHMIJ
拆分B：EL——B——空
拆分E：空——E——L——————【按照左右根的方式输出LE
EL输出完后，按照左右根的方式输出B
BEL输出完后，按照左右根的方式输出，右子树是DHMIJ，需要拆分
拆分D：HMI——D——J
拆分H：M——H——I——————【按照左右根的方式输出MIH
H输出完后java二叉树的遍历算法 《算法与数据结构基础》学习笔记05_01——非线性结构_树、二叉树、二叉树的遍历，按照左右根的方式输出，JD（注：若J还有子树，则还需再之前拆分J）
D输出完后，输出A
例题：二叉树表示算数表达式
5.3.3 已知遍历次序反推二叉树
【已知先序、中序】or 【已知中序、后序】java二叉树的遍历算法，可以确定二叉树；【已知先序、后序】，不能确定二叉树
1.【已知先序、中序】
先序：判断根结点（首端为根结点）
中序：判断左右子树
2.【已知中序、后序】
后序：判断根结点（末尾为根结点）
中序：判断左右子树
5.3.4 遍历二叉树的实现——递归算法
存储结构：二叉链表
实现方式：递归遍历
三种访问共性：访问路径相同，只是访问时机不同
时间复杂度
————每个结点只访问依次
最大空间复杂度
————递归到最远，栈占用最大辅助空间
1.【先序遍历 DLR】
//【先序遍历DLR————递归算法】
int PreOrderTraverse(BiTree T) {
if(T == NULL) return 1; // 若空二叉树
else { // ——————根左右DLR——————
<p>![java二叉树的遍历算法_遍历树 算法_二叉树的递归遍历算法][22]
visit(T); // 访问根结点
PreOrderTraverse(T->lchild); // 回调递归：遍历左子树
PreOrderTraverse(T->rchild); // 回调递归：遍历右子树
}</p>
2.【中序遍历 LDR】
//【中序遍历LDR————递归算法】
int InOrderTraverse(BiTree T) {
if(T == NULL) return 1; // 若空二叉树
else { // ——————左根右LDR——————
InOrderTraverse(T->lchild); // 回调递归：遍历左子树
visit(T); // 访问根结点
InOrderTraverse(T->rchild); // 回调递归：遍历右子树
}
3.【后序遍历 LRD】
//【后序遍历LRD————递归算法】
int PostOrderTraverse(BiTree T) {
if(T == NULL) return 1; // 若空二叉树
else { // ——————左右根LRD——————
PostOrderTraverse(T->lchild); // 回调递归：遍历左子树
PostOrderTraverse(T->rchild); // 回调递归：遍历右子树
visit(T); // 访问根结点
}
5.3.5 遍历二叉树的实现——非递归算法
【中序遍历LDR】为例
实现方式——栈
//【中序遍历LDR————非递归算法，栈实现】
int InOrderTraverse(BiTree T) {
BTNode *p, *q; // 新建指针
SqStack S; // 新建栈
InitStack(S); // 初始化栈
p = T; // p指针指向根结点
while(p || !StackEmpty(S)) { // 若p指针非空 or 栈非空
if(p) { // 若p非空
Push(S, p); // 让p指向的元素地址 入栈
p = p->lchild; // p 指向左子树
}
else {
Pop(S, q); // 出栈，栈顶元素的地址存在q中
visit(q); // 访问出栈的元素
p = q->rchild; // p指向被访问元素的右子树
}
}
return 1;
5.3.6 二叉树的层次遍历
按照编号遍历：从上到下，从左到右
实现方式：队列
（根结点入队、结点出队、出队结点的孩子入队）
//【二叉树的层次遍历————队列实现】
void LevelOrder(BiTree T) {
BTNode *p = T; // 新建指针，指向二叉树根结点
SqQueue qu; // 新建循环队列
InitQueue(qu); // 初始化队列
enQueue(qu, p); // 根结点地址入栈
while(!QueueEmpty(qu)) { // 队非空，则循环
deQueue(qu, p); // 出队，出队元素地址存储在p中
visit(p->data); // 访问出队结点
if(p->lchild != NULL)
enQueue(qu, p->lchild); // 让出队结点左孩子入队
if(p->rchild != NULL)
enQueue(qu, p->rchild); // 让出队结点右孩子入队
}
5.3.7 遍历二叉树的应用
1.【二叉树的建立——递归遍历实现】
遍历的操作：先序遍历，输入结点的信息，若输入#表示该结点为空
【二叉树的建立——递归遍历实现】
int CreateBiTree(BiTree &T) { // 传入链二叉树
char ch;
cin >> ch;
if(ch == '#') T = NULL; // 该二叉树为空
else {
T = new BiTNode; // 新建二叉树
T->data = ch; // 传入字符数据到二叉树根结点
CreateBiTree(T->lchild); // 递归：构造左子树
CreateBiTree(T->lchild) // 递归：构造右子树
}
return 1;
2.【二叉树的复制——递归遍历实现】
已知二叉树，将其复制一份
【二叉树的建立——递归遍历实现】
int CreateBiTree(BiTree &T) { // 传入链二叉树
char ch;
cin >> ch;
if(ch == '#') T = NULL; // 该二叉树为空
else {
T = new BiTNode; // 新建二叉树
T->data = ch; // 传入字符数据到二叉树根结点
CreateBiTree(T->lchild); // 递归：构造左子树
CreateBiTree(T->lchild) // 递归：构造右子树
}
return 1;
3.【计算二叉树深度——递归遍历实现】
当前结点的深度：计算左子树深度、和右子树深度，取大者+1（通过递归的回调计算上方结点的深度）
//【二叉树的复制——递归遍历实现】
void Copy(BiTree T, BiTree &NewT) { // 输入参数：已知树，新树
if(T == NULL) NewT = NULL; // 若为空树
else {
NewT = new BiTNode; // 新建树
NewT-data = T->data; // 根结点赋值
Copy(T->lchild, NewT->lchild); // 递归：复制左子树
Copy(T->rchild, NewT->rchild); // 递归：复制右子树
}
4.【计算二叉树结点总数——递归遍历实现】
当前二叉树结点总数：左子树结点总数+右子树结点总数+1（通过递归的回调计算大二叉树的结点总数）
//【计算二叉树结点总数——递归遍历实现】
int NodeCount(BiTree T) {
if(T == NULL) return 0; // 空树的结点总数为0
else
return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
// 递归回调：计算当前结点的结点总数
5.【计算二叉树的叶子结点数——递归遍历实现】
当前二叉树叶子结点总数：左子树结点总数+右子树结点总数（通过递归的回调计算大二叉树的叶子数）——
//【计算二叉树的叶子结点数——递归遍历实现】
int LeadCount(BiTree T) {
if(T == NULL) return 0; // 若为空树
if(T->lchild == NULL && T->lchild == NULL)
return 1; // 若不为空树，且无左右子树
else
return LeadCount(T->lchild) + LeadCount(T->rchild);
// 递归回调：计算当前结点的叶子结点数
5.4 线索二叉树
二叉链表一定有n+1个空的指针域
1.利用二叉链表的n+1个指针域——线索化：
2.线索二叉树（ Tree）——线索化后的二叉树
线索二叉树的二叉链表还需增设2个标志域 ltag，rtag——用于标识指向孩子还是前驱后继
3.线索二叉树的定义
//【线索二叉链表】
typedef struct BiThrNode {
ElemType data; // 数据域
int ltag, rtag; // 标志位
struct BiThrNode *lchild, *rchild; // 指针域
补充：线索二叉树仍然会有空指针，可以增设头结点，让这些空结点指向头结点，类似于循环链表
