一、树的相关定义

何为“结点的度”？

结点的儿子的个数

何为“结点的次数”

同“结点的度”

何为树的度

树中结点度的最大值

二叉树的根在第几层？

第0层

何为“叶子结点”？

度为0的结点

何为“终端结点”？

同“叶子结点”

何为“分支结点”？

度不为0的结点

何为“结点的深度”？

根到结点v的路径长度为v的结点深度
根结点的深度为0

何为“结点的高度”？

结点v到叶结点的最长路径长度

何为“树的高度”？

根结点的高度

二、二叉树的定义及性质

二叉树与树的主要区别

二叉树是有序的，结点的子树分为左子树和右子树。即使某结点只有一棵子树，也要指明该子树是左子树还是右子树

何为“满二叉树”？

高度为k 且结点个数为$2^{k+1}-1$个结点的二叉树

何为“完全二叉树”？

层次遍历时，所有结点的位置能与一棵满二叉树的结点一一对应

具有n个结点的完全二叉树的高度为

$log_{2}n$（取下界）

三、二叉树的遍历

1、非递归中根遍历

算法 NIO(t)
NIO 1.[初始化]
CREAT(S).
p = t.
NIO 2.[入栈]
WHILE p ≠ NULL DO
{
    S.push(p).
    p = left(p)
}
NIO 3.[栈为空？]
IF S 空 THEN RETURN.
S.peek(p).
S.pop().
NIO 4 [访问p]
PRINT(Data(p)).
p = right(p)
NIO 5[循环]
GOTO NIO 2.

非递归后根遍历

每个结点需要入栈3次，入栈3次。
这样需要记录每个结点被访问的次数。
所以建立的堆栈需要有两个值：
(p,i). i记录了被访问的次数

当i=0时，左树入栈
当i=1时，右树入栈
当i=2时，输出

算法 NPO(t)
NPO1.[初始化]
    IF t == NULL THEN RETURN
    CREAT(S). S.push(t,0).
NPO2.[遍历]
    WHILE S 非空 DO{
    S.peek((p,i)).
    S.pop().
    IF i == 0 THEN{
    S.push(p,2).
    IF Left(p) ≠ NULL THEN S.push(Left(p),0). 
    }
    IF i == 1 THEN{
    //略
    }
    IF i == 2 THEN PRINT(Data(p)).
    }

四、表达式树

表达式树主要用在编译器的设计领域

该式表示: (a+b)×(c-d) - e

估计不是重点🐶

五、线索二叉树

懒得写了戳这里—->《彻底理解线索二叉树》

六、哈夫曼树

何为“扩充二叉树”？

当原二叉树中出现空子树时，增加特殊的结点：空树叶。由此组成的二叉树称为扩充二叉树

何为“外通路长度”？

根到外结点路径长度之和

何为“加权外通路长度”？

emmm…乘以结点的权值

它的加权外通路长度为34

何为“最优二叉树”？

加权外通路最小的扩充树。

七、树的存储

左儿子右兄弟表示法中，二叉树何时表示森林？

根节点右子树非空。
将根节点的右分支断开，则它的右儿子结点成为新的根，可以重复该操作得到所有的根。

八、并查集

设计查找（查找元素所在的集合）与归并（合并两个集合）算法。

其中：查找需要完成路径压缩。
归并需要完成小集合向大集合归并。

如何存储？

使用Father[n]数组，存储父节点。

如何存储两个集合的秩？根节点的Father值保存它的秩（集合的元素个数）。为了与父节点下标相区别，使用他的相反数。
Father[3] = 1: 3号结点的父节点为1
Father[5] = -4: 5号结点为根节点，且该集合的秩为4

查找算法：

算法 FIND(x)
FIND 1.[x是根?]
    IF Father[x] ≤ 0 THEN RETURN x.
FIND 2.[查找并压缩]
    fx = FIND(Father(x)).
    Father(x) = fx.
    RETURN fx.

归并算法

算法 UNION(x, y)
UNION 1.[找根]
    fx = FIND(x).
    fy = FIND(y).
UNION 2.[相同根]
    IF fx == fy THEN RETURN.
UNION 3.[归并]
    IF Father[fx] < Father[fy]  THEN Father[fy] = fx.
    ELSE{
    IF Father[fx] == Father[fy] THEN Father[fy] = Father[fy]-1.
    Father[f] = fy.
    }