二叉树的垂直遍历

在本主题中，我们将探讨二叉树的垂直遍历。对于垂直遍历，我们将计算水平距离。我们将为每个节点分配一个水平距离，该水平距离可以从树的任何一边开始计算。在这种情况下，我们将以树的左侧作为起点来计算水平距离。

为了给所有节点分配水平距离，我们将使用以下规则：

• 对于根节点，H_d 的值为 0，即 H_d = 0。
• 对于左子节点，H_d 的值等于父节点的 H_d 减一，即 H_d = H_d - 1。
• 对于右子节点，H_d 的值等于父节点的 H_d 加一，即 H_d = H_d + 1。

考虑下面的树

在上面的树中，“a”是根节点，所以我们将 H_d 的值赋为 0 给该节点。因为“b”是节点“a”的左子节点，所以规则 2 将应用于节点“b”。节点“b”的 H_d 值将等于 0 减 1 (0-1)，即节点“b”的 H_d 等于 -1。节点“c”是节点“a”的右子节点，所以规则 3 将应用于节点“c”。节点“c”的 H_d 值将等于 0 加 1 (0+1)，即节点“c”的 H_d 等于 1。节点“d”是节点“b”的左子节点，所以节点“d”的 H_d 值等于其父节点的 H_d 值减一；因此，H_d = -1-1 = -2。节点“e”是节点“b”的右子节点，所以规则 3 将应用于该节点。节点“e”的 H_d 值等于其父节点的 H_d 值加一；因此，H_d = -1 +1 = 0。节点“f”是节点“c”的左子节点；因此，节点“f”的 H_d 值等于 (1-1) 即零。节点“g”是节点“c”的右子节点；因此，节点“g”的 H_d 值等于 (1+1) = 2。节点“h”是节点“d”的左子节点；因此，节点“h”的 H_d 值等于 (-2-1) = -3。节点“i”是节点“d”的右子节点；因此，节点“i”的 H_d 值等于 -1。节点“j”是节点“e”的左子节点；因此，节点“j”的 H_d 值等于 -1。节点“k”是节点“e”的右子节点；因此，节点“k”的 H_d 值等于 1。节点“l”是节点“g”的左子节点；因此，节点“l”的 H_d 值等于 (2-1) = 1。节点“m”是节点“g”的右子节点；因此，节点“m”的 H_d 值等于 (2+1) = 3。

水平距离值最小的节点是“h”，即 -3，水平距离值最大的节点是“m”，即 3。具有相同水平距离值的节点将存在于同一条垂直线上。

现在我们将创建垂直线。

• 值为 -3 的节点是“h”，因此存在一条穿过节点“h”的垂直线，如下图所示：
• 值为 -2 的节点是“d”，因此存在一条穿过节点“d”的垂直线，如下图所示：
• 对于 H_d = -1，存在三个节点，即“b”、“i”和“j”，因此将创建一条穿过这三个节点的垂直线，如下图所示：
• 对于 H_d = 0，存在三个节点，即“a”、“e”和“f”，因此将创建一条穿过这三个节点的垂直线，如下图所示：
• 对于 H_d = 1，存在三个节点，即“c”、“k”和“l”，因此将创建一条穿过这三个节点的垂直线，如下图所示：
• 对于 H_d = 2，只有一个节点，即“g”，因此一条垂直线穿过节点“g”，如下图所示：
• 对于 H_d = 3，只有一个节点，即“m”，因此一条垂直线穿过节点“m”，如下图所示：

实现二叉树垂直遍历的算法

该算法结合了层序遍历和哈希表。以下是二叉树垂直遍历所需的步骤：

步骤 1： 将根节点入队。

步骤 2： 更新根节点的 H_d 距离为 0。

步骤 3： 将 H_d 0 作为键，根节点作为值添加到哈希表中。

步骤 4： 首先执行出队操作，然后执行以下步骤：

• 检查左子节点和右子节点，然后在哈希表中更新 H_d。
• 将左子节点和右子节点入队。

考虑下面的树

我们将使用队列和哈希表这两种数据结构来实现垂直遍历。

• 我们首先将节点“a”插入队列，并将节点“a”的水平距离值更新为 0。我们还将节点“a”的 H_d 和值添加到哈希表中，如下图所示：

根据算法中指定的步骤 4，从队列中出队元素“a”，并使用节点“a”的左右子节点的 H_d 值更新哈希表，如下图所示：

一旦哈希表更新完毕，我们将节点“a”的左右子节点入队，如下图所示：

步骤 4 循环进行，直到队列变空。

• 检查队列是否为空。队列不为空，所以从队列中出队元素“b”，并检查节点“b”的左子节点和右子节点。由于节点“b”同时拥有左子节点和右子节点，我们将使用节点“d”和“e”的 H_d 值更新哈希表，如下图所示：

一旦哈希表更新完毕，将节点“d”和“e”入队，如下图所示：

• 再次检查队列是否为空。队列不为空，所以从队列中出队元素“c”，并检查节点“c”的左子节点和右子节点。由于节点“c”同时拥有左子节点和右子节点，我们将使用节点“f”和“g”的 H_d 值更新哈希表，如下图所示：

一旦哈希表更新完毕，将节点“f”和“g”入队，如下图所示：

• 再次检查队列是否为空。队列不为空，所以从队列中出队元素“d”，并检查节点“d”的左子节点和右子节点。由于节点“d”同时拥有左子节点和右子节点，我们将使用“h”和“i”的 H_d 值更新哈希表，如下图所示：

一旦哈希表更新完毕，将节点“h”和“i”入队，如下图所示：

• 再次检查队列是否为空。队列不为空，所以从队列中出队元素“e”，并检查节点“e”的左子节点和右子节点。由于节点“e”没有左子节点或右子节点，因此哈希表中不会有任何更新。
• 我们再次检查队列是否为空。队列不为空，所以从队列中出队元素“f”，并检查节点“f”的左子节点和右子节点。由于节点“f”同时拥有左子节点和右子节点，我们将使用“j”和“k”的 H_d 值更新哈希表。

一旦哈希表更新完毕，将节点“j”和“k”入队，如下图所示：

• 我们再次检查队列是否为空。队列不为空，所以从队列中出队元素“g”，并检查节点“g”的左子节点和右子节点。由于节点“g”只有一个右子节点，我们将使用“l”的 H_d 值更新哈希表。

一旦哈希表更新完毕，将节点“g”入队，如下图所示：

• 再次检查队列是否为空。队列不为空，所以从队列中出队元素“h”，并检查节点“h”的左子节点和右子节点。由于节点“h”没有左子节点或右子节点，因此哈希表中不会有任何更新。

• 我们再次检查队列是否为空。队列不为空，所以从队列中出队元素“i”，并检查节点“i”的左子节点和右子节点。由于节点“i”同时拥有左子节点和右子节点，我们将使用“m”和“n”的 H_d 值更新哈希表。

一旦哈希表更新完毕，将节点“m”和“n”入队，如下图所示：

• 再次检查队列是否为空。队列不为空，所以从队列中出队元素“j”，并检查节点“j”的左子节点和右子节点。由于节点“j”没有左子节点或右子节点，因此哈希表中不会有任何更新。

• 再次检查队列是否为空。队列不为空，所以从队列中出队元素“k”，并检查节点“k”的左子节点和右子节点。由于节点“k”同时拥有左子节点和右子节点，我们将使用“p”和“q”的 H_d 值更新哈希表。

一旦哈希表更新完毕，将节点“p”和“q”入队，如下图所示：

• 再次检查队列是否为空。队列不为空，所以从队列中出队元素“l”，并检查节点“l”的左子节点和右子节点。由于节点“l”没有左子节点或右子节点，因此哈希表中不会有任何更新。

• 再次检查队列是否为空。队列不为空，所以从队列中出队元素“m”，并检查节点“m”的左子节点和右子节点。由于节点“m”没有左子节点或右子节点，因此哈希表中不会有任何更新。

• 再次检查队列是否为空。队列不为空，所以从队列中出队元素“n”，并检查节点“n”的左子节点和右子节点。由于节点“n”没有左子节点或右子节点，因此哈希表中不会有任何更新。

• 再次检查队列是否为空。队列不为空，所以从队列中出队元素“p”，并检查节点“p”的左子节点和右子节点。由于节点“p”没有左子节点或右子节点，因此哈希表中不会有任何更新。

• 再次检查队列是否为空。队列不为空，所以从队列中出队元素“q”，并检查节点“q”的左子节点和右子节点。由于节点“q”没有左子节点或右子节点，因此哈希表中不会有任何更新。