一、概念
1.结点
2.边
3.根
4.叶子结点
5.分支结点
6.子树
二、术语
1.结点之间的关系描述
（1）祖先
（2）子孙
（3）双亲（父）
（4）孩子
（5）兄弟
（6）堂兄弟
（7）路径
自上而下
（8）路径长度
经过了几条边
2.结点、树的属性描述
（1）结点的层次（深度）
从上到下数，默认从1开始，看题目要求
（2）结点的高度
从下到上数
（3）树的高度（深度）
从上到下，到底
（4）结点的度
几个子节点
结论：非叶子结点度>0;叶子结点度=0
（5）树的度
结点的度max
3.有序树、无序树
（1）有序树
从左->右有序，eg家谱，先出生的在左面
（2）无序树
左右可以交换，eg国家行政区
4.森林
m棵不相交树的集合
考点：树与森林相互转换
树->森林：在头顶加个根节点，连起来
森林->树：去掉最上面的根节点
三、考点(*)
1.结点数=总度数+1
理解：总度数表示总孩子个数，一个孩子带着一根线，只有根节点头上不带线
2.度为m的树 vs m叉树
度为m的树表示至少有一个结点的度 = m，其他的都<=m
m叉树表示，一个结点的度max = m，但不要求有没有这样的结点
结论：(前者度为m的树，后者m叉树)
①任意度<=m
②至少有一个结点的度 = m；允许所有结点度<m
③一定是非空树，至少有m+1个结点；可以是空树
3.度为m的树第i层最多有 m^(i-1)个结点
该层是满的，此时最多
4.高度为h的m叉树最多有m^h-1/m-1个结点
每层都是满的
n = m^0+m^1+m^2+······+m^(h-1)
5.高度为h的m叉树最少有h个结点
每层就一个
区别：if高为h，度为m，最少h-1+m
h-1层就1个，有一层m个
6.有n个结点的m叉树最小高度为logm(n(m-1)+1) 向上取整(up)
设高度为h，树前h-1层都是满的(往宽里长)，so 前h-1层满<n<=前h层满
四、二叉树
1.概念
m叉树，令m=2
2.特点
（1）每个结点最多只有两棵子树
度<=2
（2）左右孩子不能颠倒（有序）
（3）vs度=2
度为2的树至少有一个结点有两个孩子
（4）5种状态
空树、只有根节点、只有lchild、只有rchild、左右都有
3.特殊的二叉树
（1）满二叉树
1）理解
每一层都是满的，每个结点都有2个孩子,so高度为h，拥有2^h-1个结点
2）特点（自己画图就理解了）
a)只有最后一层有叶子结点
b)不存在度为1的结点
只有度为0和度为2的结点
c)按层序为1开始编号
i)位序为i的左孩子位序为2i
ii)右孩子2i+1
iii)i的父结点位序为i/2 down
（2）完全二叉树
将满二叉树从右下依次减少结点，都是完全二叉树
attn:满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
1)特点
a)只有最后两层可能有叶子结点
b)最多只有1个度
c)按层序为1开始编号
位序为i的lchild、rchild、parent
d)总共有n个结点
i)i<=n/2 down 分支结点
ii)i>n/2 down 叶子结点
2）性质考点
a)有n个结点，高度为log2(n+1) up or log2n+1 down
b)n个结点推出度为012的结点个数
n=2k（偶数个结点） n1 = 1,n0=k,n2=k-1
n=2k+1(奇数个结点) n1=0,n0=k,n2=k-1
（3）二叉排序树
左<右
（4）平衡二叉树
每个结点的左右子树深度<=1
√ ×
4.性质考点(*)
（1）非空二叉树度为012的结点，个数为n012，则n0=n1+n2
推导：n = n1+n2+n3 各度结点数相加
n = n0*0+ n1*1 + n2*2+1
（2）二叉树第i层最多有 2^(i-1)个结点
（3）高度为h的二叉树最多有2^h-1/2-1个结点
5.存储结构
（1）顺序存储
1)定义
2)初始化
空第一个元素，这样下标与位置相同，便于存取
3）打印
（2）链式存储（二叉树链式存储）
1)定义
2)初始化
3）创建（一个一个加）
每次创建的时候需要新创建结点，因为头结点在初始化的时候创建了，so直接赋值即可6.遍历（会手算+代码）
以此为例
（1）先序
1）手算
way1：根左右依次写
way2：从根开始，先向左走，到底了再向上，可以向右再向右走，第一次到了就输出
2）代码
遇到就visit，之后递归左孩子和右孩子
（2）中序
1）手算
way1：左根右
way2：第二次到了就输出
2）代码
先递归左孩子，第二次遇到就visit，之后递归右孩子
（3）后序
1）手算
way1：左右根
way2：第三次到了就输出
2）代码
先递归左右孩子，第三次遇到就visit
（4）层序
1）手算
从左到右依次输出
2）代码
利用辅助队列，入队根节点，入队之后if队列不为null，出队，判断此结点左右孩子是否为空，if不为空，入队，循环
（5）根据次序创建树
1）前+中
2）后+中
3）层+中
7.线索二叉树
（1）作用
方便从一个结点，找它的前驱和后继
if不用线索二叉树，我们一共需要遍历两次
（2）存储结构
1）思路
n个结点的二叉树，n+1个空指针表示该节点的前驱和后继，so并非所有结点都是有空指针，so用ltag、rtag==1表示可以建设成线索二叉树，则指向某节点的前驱or后继
2）代码
（3）三种线索二叉树
前序中序后序
分别前中后序遍历，从而确定前驱和后继
（4）手算画出线索二叉树
步骤：
step1：遍历
step2：标号
step3：连线
1）前序
2）中序
3）后序
（5）用代码线索化
（6）找前驱and后继
三种树的前驱后继（6种）