1、树的基本概念
- 节点的度：节点拥有的子树数目。例如，若一个节点有 3 棵子树，其度为 3。
- 树的度：树中节点的最大度数。如树中所有节点的度最大为 4，则树的度是 4。
- 叶子节点：度为 0 的节点，也叫终端节点，它没有子节点。
- 分支节点：度不为 0 的节点，也称为非终端节点。
- 内部节点：除根节点和叶子节点外的分支节点。
- 父节点：若节点 A 有子节点 B，则 A 是 B 的父节点。
- 子节点：节点的下属节点，如 B 是 A 的子节点。
- 兄弟节点：具有相同父节点的节点互为兄弟节点。
- 层次：根节点在第 1 层，根的子节点在第 2 层，以此类推，节点的层次是从根到该节点的路径长度加 1。
2、二叉树的概念与分类
- 二叉树：每个节点最多有两个子树的树结构，分别称为左子树和右子树。
- 满二叉树：除最后一层无任何子节点外，每一层上的所有节点都有两个子节点的二叉树。
- 完全二叉树：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干节点。
- 非完全二叉树：不满足完全二叉树条件的二叉树。
3、二叉树的重要特性
- 性质 1：在二叉树的第 i 层上至多有
个节点（i≥1）。 - 性质 2：深度为 k 的二叉树至多有
个节点（k≥1）。 - 性质 3：对任何一棵二叉树 T，如果其终端节点数为
，度为 2 的节点数为
，则
。
4、二叉树的遍历
- 前序遍历：先访问根节点，然后前序遍历左子树，最后前序遍历右子树。例如，对于二叉树
root->left->right，前序遍历顺序是root、left、right。 - 中序遍历：先中序遍历左子树，然后访问根节点，最后中序遍历右子树。如对于二叉树
root->left->right，中序遍历顺序是left、root、right。 - 后序遍历：先后序遍历左子树，然后后序遍历右子树，最后访问根节点。例如，对于二叉树
root->left->right，后序遍历顺序是left、right、root。 - 层次遍历：从根节点开始，按层次从左到右依次访问节点。
5、反向构造二叉树
根据给定的遍历序列（如前序、中序或后序遍历序列）来构造二叉树。通常利用前序遍历确定根节点，中序遍历确定左右子树的节点，然后递归地构建二叉树。例如，已知前序遍历序列为ABDECF，中序遍历序列为DBEAFC，可以确定 A 是根节点，然后根据中序序列可知DBE是左子树节点，FC是右子树节点，再继续递归构建左右子树。
6、树转二叉树
将普通树转换为二叉树的方法是：先把树中每个节点的第一个子节点作为二叉树中该节点的左子节点，然后把该节点的兄弟节点作为二叉树中该节点的右子节点。例如，对于一棵树，将根节点的最左边子节点作为二叉树根节点的左子节点，根节点的其他子节点依次作为左子节点的右子节点，以此类推。
7、查找二叉树（二叉排序树）
- 定义：二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左、右子树也分别为二叉排序树。
- 查找：从根节点开始比较，若查找值小于根节点值，则在左子树中继续查找；若大于根节点值，则在右子树中继续查找，直到找到或确定不存在。
8、构造霍夫曼树（最优）
- 霍夫曼树是带权路径长度最短的二叉树。
- 构造方法：根据给定的权值集合，将权值最小的两个节点合并成一个新节点，新节点的权值为这两个节点权值之和，然后将新节点加入集合，重复上述步骤，直到集合中只剩下一个节点，该节点就是霍夫曼树的根节点。例如，给定权值集合
{3, 5, 2, 7}，先选择 2 和 3 合并成 5，然后选择 5 和 5 合并成 10，最后 10 和 7 合并成 17，得到霍夫曼树。
9、线索二叉树
- 线索二叉树是对二叉树的一种改进，通过利用二叉树中的空指针域来存放节点的前驱和后继信息。
- 若节点的左指针为空，则将其指向该节点的前驱节点；若节点的右指针为空，则将其指向该节点的后继节点。这样可以方便在遍历二叉树时快速找到节点的前驱和后继，提高遍历效率。
10平衡二叉树
- 平衡二叉树是一种特殊的二叉排序树，它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度差的绝对值不超过 1。
- 插入和删除节点时，可能会破坏平衡二叉树的平衡性质，需要通过旋转操作来调整树的结构，以保持平衡。例如，常见的旋转操作有左旋、右旋、先左旋后右旋、先右旋后左旋等。
