1.树的一些结论：
（1）节点个数=度数+1
（2）一个概念的辨析：树的度（例如为n)和m叉树
树的度：表示一个树必有一个节点的度为n，且一定不为空树，节点数最少为n+1
m叉树：可以为空树，可以所有节点的度都小于m
2.二叉树的一些结论
（1）非空二叉树中：n0=n2+1
（2）完全二叉树的话：n1一定为0或1，n0与n2的和一定为奇数
3.二叉树的顺序存储
struct TreeNode{
Elemtype value;
bool isEmpty;
} 二叉树的顺序存储，是通过数组存储的。但无论是不是完全二叉树，都必须按照完全二叉树来进行存储。如果那个位置没有树，就填0，但那个位置必须有。（即最坏情况：哪怕是高度为h的，只有h个节点的树（只有右结点），也需要2的h次方减一个存储单位）
所以，一般来说，顺序存储，只适合完全二叉树。（但不是完全的也可以，但比较浪费）
4.二叉树的链式存储
typedef struct BitNode{
Elemtype data;
struct BitNode *lchild,*rchild;
}BitNode,*BitTree;
n个节点，应该有2n个指向域，但只会有n-1个指针，所以一定有n+1个空链域。
因为二叉树方便找左右孩子节点，但不方便找父亲节点，所以可以引入一个父亲节点。
typedef struct BitNode{
Elemtype data;
struct BitNode *lchild,*rchild;
struct BitNode *parent;
}BitNode,*BitTree;
5.二叉树的遍历
先序——前缀表达
中序——中缀表达
后序——后缀表达
层序遍历：从上到下，从左至右
6.由遍历推二叉树
前/后/层次+中可以推（都是先找根节点在哪，然后在分左右子树，再推）
7.线索二叉树
typedef struct ThreadNode{
Elemtype data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag;
------左右线索标志
}ThreadNode,*ThreadTree;
中序线索化（只要没有左右孩子，ltag和rtag就为1）
文章图片
先序线索化（只有先序线索化会有转圈的问题（第一张图），只有ltag=0 才能先序线索化）
文章图片
文章图片
后序同中序（基本代码相同）
线索二叉树找前序和后继（先序是在左孩子存在，后序是在右孩子存在的情况下（即没有对应的线索指针））
文章图片
8.树
（1）双亲表示法
文章图片
增：新增元素，直接在表中添加即可，无需按顺序
删：（1）将后面的数字改为-1（会增加空数据，降低效率） （2）删除该元素以及其子元素（如果有）
优点：查找双亲方便
缺点：查找孩子节点需要从头遍历
（2）孩子表示法
文章图片
（3）孩子兄弟表示法（即树与二叉树的转换）
文章图片
（4）森林和树的转换
文章图片
（5）树的遍历
树的先根遍历——对应二叉树的先序遍历（深度优先遍历）
树的后根遍历——对应二叉树的中序遍历（深度优先遍历）
树的层序遍历——从上至下，从左至右（广度优先遍历）
（6）森林的遍历
森林的先序遍历——所有树的先序遍历
森林的中序遍历——所有树的后序遍历
遍历总结：
文章图片
（7）哈夫曼树的构造
文章图片
【树与二叉树】（8）如何对数据编码（无前缀编码：即所有的字母或数据皆为叶子节点）
文章图片
推荐阅读
- 数据结构|Map和Set
- 数据结构|【数据结构】二叉搜索树
- 数据结构|【八大排序④】归并排序、不基于比较的排序（计数排序、基数排序、桶排序）
- 数据结构|【数据结构】优先级队列 - 堆
- 数据结构于算法|十大排序算法基本原理及其实现
- 牛客刷题集锦|『牛客|每日一题』 栈的压入、弹出序列
- #|红黑树的学习
- Linux|进程间通信之共享内存
- 数据结构|谁才是排序王中王（快？归？希？）