树数据结构面试

树是计算机科学的基础结构，是众多算法和数据表示的支柱。

什么是树？
树数据结构 是一种分层数据结构，其中称为节点的元素集合通过边相互连接，使得任何两个节点之间都存在一条路径。

树数据结构中的基本术语：

  • 父节点： 作为节点的前驱的节点称为该节点的父节点。 {B}是{D, E} 的父节点 。
  • 子节点： 一个节点的直接后继节点称为该节点的子节点。示例：  {D，E}是{B} 的子节点 。
  • 根节点： 树的最顶层节点或没有任何父节点的节点称为根节点。{A } 是树的根节点。一棵非空树必须恰好包含一个根节点以及从根到树的所有其他节点的一条路径。
  • 叶节点或外部节点： 没有任何子节点的节点称为叶节点。 {K，L，M，N，O，P，G} 是树的叶节点。
  • 节点的祖先： 从根到该节点的路径上的任何前驱节点都称为该节点的祖先。 {A,B} 是节点 {E}的祖先节点
  • 后代： 从叶节点到该节点的路径上的任何后继节点。 {E,I} 是节点 {B} 的后代 。
  • 兄弟节点： 同一父节点的子节点称为兄弟节点。 {D,E} 称为兄弟姐妹。
  • 节点的级别： 从根节点到该节点的路径上的边数。根节点的级别为 0。
  • 内部节点： 具有至少一个子节点的节点称为内部节点。
  • 节点的邻居： 该节点的父节点或子节点称为该节点的邻居。
  • 子树：树的任何节点及其后代。

树遍历技术：

1.中序遍历：
算法中序（树）

  • 遍历左子树，即调用Inorder(left->subtree)
  • 访根。
  • 遍历右子树，即调用Inorder(right->subtree)

对于二叉搜索树 (BST)，中序遍历以非降序给出节点。为了以非递增顺序获取 BST 的节点，可以使用中序遍历的变体，其中中序遍历是相反的。

2.预序遍历：
算法预序（树）

  • 访根。
  • 遍历左子树，即调用Preorder(left->subtree)
  • 遍历右子树，即调用Preorder(right->subtree) 

前序遍历用于创建树的副本。前序遍历还用于获取表达式树上的前缀表达式。

3.后序遍历：
后序算法（树）

  • 遍历左子树，即调用Postorder(left->subtree)
  • 遍历右子树，即调用Postorder(right->subtree)
  • 访问根

后序遍历用于删除树。后序遍历对于获取表达式树的后缀表达式也很有用

树数据结构的类型：
以下是树数据结构的类型：

  1. 二叉树
  2. 三叉树
  3. N 叉树或通用树
  4. 二叉搜索树
  5. AVL树
  6. B树

1.二叉树：
在二叉树中，每个节点最多可以有两个与其链接的子节点。一些常见类型的二叉树包括满二叉树、完全二叉树、平衡二叉树和简并二叉树。
以下是不同二叉树的列表：

  • 满二叉树：如果每个节点都有 0 或 2 个子节点，那么二叉树就是满二叉树。以下是完整二叉树的示例。我们也可以说满二叉树是除叶节点之外的所有节点都有两个子节点的二叉树。满二叉树是一种特殊类型的二叉树，其中每个父节点/内部节点有两个子节点或没有子节点。它也称为真二叉树。
  • 退化（或病态）树：每个内部节点都有一个子节点的树。这种树在性能方面与链表相同。退化树或病态树是指左侧或右侧只有一个子节点的树。
  • 偏斜二叉树：偏斜二叉树是一种病态/退化树，其中树要么由左节点主导，要么由右节点主导。因此，偏斜二叉树有两种类型：左偏二叉树和右偏二叉树。
  • 完全二叉树：如果所有级别都完全填满（可能除了最后一级）并且最后一级具有尽可能左侧的所有键，则二叉树是完全二叉树。
  • 完美二叉树 二叉树是一种完美二叉树，其中所有内部节点都有两个子节点，并且所有叶节点都处于同一级别。 平衡二叉树如果树的高度为 O(Log n)，其中 n 是节点数，则二叉树是平衡的。例如，AVL 树通过确保左子树和右子树的高度之差最多为 1 来保持 O(Log n) 高度。

2.三叉树： 
三叉树是一种树形数据结构，其中每个节点最多有三个子节点，通常区分为“左”、“中”和“右”。

3. N叉树或泛型树：
通用树是节点的集合，其中每个节点都是一个由记录和对其子节点的引用列表组成的数据结构（不允许重复引用）。与链表不同，每个节点存储多个节点的地址。

4.二叉搜索树：
二叉搜索树 是一种基于节点的二叉树数据结构，具有以下属性：

  • 节点的左子树仅包含键小于该节点键的节点。
  • 节点的右子树仅包含键大于该节点键的节点。
  • 左子树和右子树也必须是二叉搜索树。

BST 中的操作：
  1. 插入 BST：
  2. 在 BST 中搜索：
  3. BST 中的删除：

4.1插入二叉搜索树：
通过维护二叉搜索树的属性，新的键总是插入到叶子中。我们开始从根开始搜索键，直到找到叶节点。一旦找到叶节点，新节点就会添加为叶节点的子节点。当我们尝试将节点插入二叉搜索树时，请遵循以下步骤：

  • 检查要插入的值（例如 X）与当前节点的值（例如 val）：
    • 如果 X 小于 val 则移至左子树。
    • 否则，移动到右子树。
  • 到达叶子节点后​​，  根据 X 与叶子节点值之间的关系，将X插入到其右侧或左侧。

时间复杂度：O(h)， 其中 h 是二叉搜索树的高度。在最坏的情况下，我们可能必须从根移动到最深的叶节点。倾斜树的高度可能变为 n  ，插入操作的时间复杂度可能变为 O(n)。 辅助空间：如果我们使用迭代方法，则为O(1) ；如果我们使用递归方法，则为(n) 。

4.2 BST搜索：
要在 BST 中搜索值，请将其视为排序数组。现在我们可以使用 二分搜索算法轻松地在 BST 中执行搜索操作。假设我们要搜索数字 X， 我们从根开始。然后：

  • 我们将要搜索的值与根的值进行比较。 
    • 如果相等，我们就完成搜索；如果它更小，我们知道我们需要转到左子树，因为在二叉搜索树中，左子树中的所有元素都较小，而右子树中的所有元素都较大。 
  • 重复上面的步骤，直到无法再遍历为止
  • 如果在任何迭代中找到键，则返回 True。否则为假。

时间复杂度： O(h)，其中 h 是 BST 的高度。辅助空间：如果我们使用迭代方法，则在二叉搜索树中搜索的辅助空间复杂度为 O(1)；如果我们使用递归方法，则为(n) 。 

4.3 BST中的删除：
在此BST中删除节点的任务 可以分为 3 种情况：
案例1.删除BST中的叶子节点
如果要删除的节点是叶节点，则可以简单地将其从树中删除。被删除节点的父节点必须将其相应的子指针设置为NULL，以反映树中的变化。

案例 2. 删除 BST 中具有单个子节点的节点
如果要删除的节点只有一个子节点，则可以提升该子节点来替换已删除的节点。被删除节点的父节点必须更新其相应的子节点指针以指向提升的子节点。

案例 3. 删除 BST 中具有两个子节点的节点
如果要删除的节点有两个子节点，则可以通过从要删除的节点的右子树中选择最小值或从左子树中选择最大值来找到替换节点。找到替换节点后，即可提升其替换被删除的节点。替换节点的左子树（如果存在）必须附加到提升节点的左子节点，替换节点的右子树（如果存在）必须附加到提升节点的右子节点。被删除节点的父节点必须更新其相应的子指针以指向提升的节点。

时间复杂度：  O(h)，其中 h 是 BST 的高度。 辅助空间：  O(n)。

6.AVL树
AVL 树 定义为自平衡 二叉搜索树 (BST)，其中任何节点的左子树和右子树的高度之差不能大于 1。
任何节点的左子树和右子树的高度之差称为  该节点的平衡因子。

旋转 AVL 树中的子树：
AVL 树可以通过以下四种方式之一进行旋转以保持自身平衡：

左旋转：
当一个节点被添加到右子树的右子树中时，如果树失去平衡，我们会进行一次左旋转。

右旋转：
如果将一个节点添加到左子树的左子树上，AVL树可能会失去平衡，我们做一次右旋转。

左右旋转：
左右旋转是在执行右旋转之后发生第一次左旋转的组合。

左右旋转：
左右旋转是在执行左旋转之后发生第一次右旋转的组合。

AVL 树中的操作：

  • 插入
  • 删除
  • 搜寻中