结丹期
8. 什么是二叉树？二叉树的前序、中序、后序遍历分别是什么？
二叉树 是一种每个节点最多有两个子节点的数据结构，通常称为 左子节点 和 右子节点。
遍历方式：
前序遍历：先访问根节点，然后访问左子树，最后访问右子树。
中序遍历：先访问左子树，然后访问根节点，最后访问右子树。
后序遍历：先访问左子树，然后访问右子树，最后访问根节点。
举例：
如果二叉树是：
A
/ \
B C
前序遍历：A -> B -> C
中序遍历：B -> A -> C
后序遍历：B -> C -> A
9. 二叉搜索树（BST）是什么？如何在二叉搜索树中插入和删除节点？
二叉搜索树（BST） 是一种特殊的二叉树。
满足以下性质：
对于每个节点，其左子树的所有节点值都小于该节点的值
右子树的所有节点值都大于该节点的值
总结起来就是：左子小于父，右子大于父
插入节点：从根节点开始，比较待插入值和当前节点的值：
如果小于当前节点，进入左子树；如果大于当前节点，进入右子树。
重复直到找到空节点，插入新节点。
删除节点：
节点没有子节点，直接删除。
节点有一个子节点，用该子节点替代被删除节点。
节点有两个子节点，找到右子树中的最小节点或左子树中的最大节点替换该节点，然后删除最小或最大节点。
10. 什么是平衡二叉树？AVL 树和红黑树的区别是什么？
平衡二叉树 是一种特殊的二叉树，确保树的左右子树高度差不超过 1，以避免树退化为链表，影响查找效率。
AVL 树 和 红黑树 都是平衡二叉树的变种，区别在于它们维持平衡的方式不同：
AVL 树：每个节点的左右子树高度差最多为
1，因此更严格，但插入和删除时需要更多旋转操作来维持平衡。红黑树：每个节点除了存储数值外，还存储一个颜色（红或黑）。通过颜色规则来维持近似平衡，插入和删除的调整操作较少，性能更优。
总结：
AVL树适合频繁查找的场景。红黑树适合插入和删除操作较多的场景，如
Java的TreeMap和TreeSet。
11. 如何判断一个二叉树是否是平衡二叉树？
判断一个二叉树是否为 平衡二叉树，可以通过递归计算每个节点的高度，检查左右子树的高度差是否大于 1。
算法思路：
对每个节点，递归计算其左子树和右子树的高度。
如果某个节点的左右子树高度差超过
1，则该树不是平衡二叉树。如果所有节点的高度差都不超过
1，则是平衡二叉树。
举例：
对于下面的二叉树：
A
/ \
B C
/
D
节点 B 的左子树高度为 1，右子树高度为 0，因此平衡。
根节点 A 的左右子树高度差为 1，因此该二叉树是平衡的。
12. 什么是图？图的存储方式有哪些？
图 是由节点（顶点）和边组成的数据结构，节点之间通过边相连。
图可以是 有向图 或 无向图，也可以是 加权图（边有权重）或 非加权图。
如下所示为无向图表示：
A --- B
\ /
C
存储方式：
邻接矩阵：用一个二维数组存储图，数组的行列表示节点，矩阵中的值表示节点之间是否存在边。
优点：快速查找两个节点之间是否有边。
缺点：占用空间较大，尤其是稀疏图（边较少）。
邻接表：每个节点对应一个链表，链表中存储与该节点相连的所有节点。
优点：节省空间，适合稀疏图。
缺点：查找两个节点是否相连需要遍历链表，效率低于邻接矩阵。
13. 广度优先搜索（BFS）和深度优先搜索（DFS）有什么区别？
BFS 和 DFS 是图的遍历算法，区别在于遍历的顺序和策略不同。
广度优先搜索（BFS）：
使用队列，按层次逐步遍历节点，先访问所有相邻节点，再访问这些相邻节点的邻居。
应用场景：适合寻找最短路径或广度优先的场景，如迷宫最短路径问题。
深度优先搜索（DFS）：
使用栈（递归实现），优先深入到某条路径的尽头，然后回溯，继续探索其他路径。
应用场景：适合探索所有路径、查找连通分量等问题，如图的连通性判断。
BFS 更像逐层扩展，会遍历图的每一层，而 DFS 会优先走到底部再返回。
在遍历一棵树时，BFS 类似于从根节点逐层展开，而 DFS 则类似于一直走到树的最深处，再回到上一级。
14. 如何在图中判断是否存在环？
判断图中是否存在 环，可以通过以下两种方法：
DFS 法：使用深度优先搜索，标记访问过的节点。如果在一次
DFS遍历中再次访问到已经在当前路径上的节点，则说明存在环。- 思路：对每个节点，使用递归搜索，如果在同一递归调用栈中遇到已访问的节点，则说明存在环。
拓扑排序法（针对有向无环图）：将图进行拓扑排序。如果排序过程中某个节点没有入度为
0的邻居节点，则说明图中存在环。
假设有图：
A -> B -> C -> A
使用 DFS 进行遍历时，从 A 开始，遍历到 C 后，再回到 A，说明存在环。