二叉树的对角线遍历

在这里，我们将看到如何以对角线的方式遍历二叉树。要打印二叉树中的对角线节点，我们需要计算对角线距离。让我们通过一个例子来理解这一点。

考虑下面的树

在上图中，对角线距离用 'd' 的符号表示。标记对角线距离有两个规则：

• 只有当节点有左子节点时，'d' 变量才会加 1。
• 对于每个右子节点，'d' 与父节点保持不变（'d' 对于右子节点保持不变）。

在上图中，节点 'a' 的对角线距离为 0。由于节点 'a' 有两个子节点，即节点 'b'（左子节点）和节点 'c'（右子节点），因此节点 'b' 的对角线距离会增加并变为 1，而节点 'c' 的对角线距离将保持不变并变为 0。节点 'b' 有一个左子节点，即 'd'，其对角线距离将变为 2，而节点 'e' 是右子节点，因此其对角线距离值将保持不变，即 1。节点 'c' 有一个左子节点，即 'f'，因此其对角线距离值将增加，'f' 的 'd' 值将变为 1。节点 'c' 也有一个右子节点，即 'g'，其对角线距离值将与其父节点 'c' 保持相同。

一旦计算出所有节点的对角线距离，我们就可以找到对角线。具有相同对角线距离值的节点将被视为一条对角线。在上图中，我们可以观察到节点 'a'、'c' 和 'g' 具有相同的对角线距离值，因此“acg”将被视为一条对角线。节点 'b'、'e' 和 'f' 具有相同的对角线距离值，即 1，因此“aef”将被视为一条对角线。只有具有对角线距离值 2 的一个节点。因此，上图中的二叉树有三条对角线：“acg”、“bef”和“d”。

考虑下面的树，以便更清楚地理解带对角线距离的节点的标记。

在上图的二叉树中，对角线距离值为 0 的节点是 'a'、'c'、'g'、'm' 和 'r'。对角线距离值为 1 的节点是 'b'、'e'、'f'、'k'、'l' 和 'q'。对角线距离值为 2 的节点是 'd'、'i'、'j'、'm'、'p'、'v' 和 't'。对角线距离值为 3 的节点是 'h'、'u' 和 's'。只有一个值为 4 的节点是 'n'。因此，存在 5 条对角线，它们是“a c g m r”、“b e f k l q”、“d i j m p v t”、“h u s”和“n”。

标记带对角线距离值的节点的简便方法

• 首先，将根节点标记为 0。如下所示，标记根节点的右侧系列为 0
  简单来说，我们可以说 0^th 对角线是“a c g m r”。
• 其次，0^th 对角线中元素的左子节点应标记为 1，即 0+1 = 1。
• 按第一步的方式标记右侧系列。节点 'b' 的右侧系列，即 'e' 和 'k' 将被标记为 1。节点 'f' 没有子节点。节点 'l' 的右子节点，即 'q' 将被标记为 1。
  因此，1st 对角线将是“b e k f l q”。
• 现在，1th 对角线中所有元素的左子节点应标记为 2，即 1+1 = 2。
• 将右侧系列标记为其父节点。节点 'd' 的右侧系列是“i m v”，因此节点 'i'、'm' 和 'v' 被标记为 2。节点 'p' 的右侧系列是 't'。。
  因此，2^nd 对角线将是“d i m v j p t”。
• 现在，我们将标记对角线距离值为 2 的节点的子节点。首先，我们将标记左子节点。节点 'd' 的左子节点是 'h'，因此节点 'h' 将被标记为 3，即 2+1 = 3。节点 'm' 的左子节点是 'u'，因此节点 'u' 将被标记为 3，即 2+1 = 3。节点 'p' 的左子节点是 's'，因此节点 's' 将被标记为 3，即 2+1 = 3。
  标记完左侧系列后，我们将标记右侧系列。由于没有右子节点系列，因此不会进行标记。最终树如下所示
  因此，3^rd 对角线将是“h s”。
• 现在，我们将标记对角线距离值为 3 的节点的子节点。只有一个节点 'h' 有左子节点 'n'。因此，'n' 将被标记为 4。因此，4^th 对角线将是“n”。

算法

考虑下面的树，以便更清楚地理解上述算法。

在这里，我们使用队列数据结构来打印对角线元素。

根据上述算法，元素 'a' 被插入队列，然后是 NULL 值，如下所示

然后，while 循环将执行，直到队列为空。

在第 0 次迭代中，'a' 将从队列中出队。现在，'p' 指向节点 'a' 并且不等于 NULL，因此它将打印 'a'，如下所示

a->left 不为 NULL，因此 enqueue(a->left) // b；队列将如下所示

p = a ->right // c

由于 'p' 指向节点 'c'，因此条件 **p != NULL 为真，并将打印 'c'。**

在第 1 次迭代中，'p' 不等于 NULL；它等于 'c'。

c->left 不为 NULL // 'f'；因此 'f' 将被入队，如下所示

p = c-> right // 'g'

由于 'p' 指向节点 'g'，因此条件 **p!= NULL** 为真，并将打印 'g'。

在第 2 次迭代中，'p' 不为 NULL；它等于 'g'。

g->left 为 NULL；因此，条件 p->left 为假。

p = g->right // 'l'

由于 'p' 指向节点 'l'，因此条件 **p!= NULL** 为真，并将打印 'l'。

在第 3 次迭代中，'p' 不为 NULL；它等于 'l'。

p-> left 不为 NULL // 'm'；因此 'm' 将被入队，如下所示

p = l->right // 'n'

由于 'p' 指向节点 'n'，因此条件 p != NULL 为真，并将打印 'n'

在 **第 4 次迭代中**，'p' 不为 NULL；它等于 'n'。

p->left 为 NULL；因此，条件 p->left 为假。

p =p->right; 由于节点 'n' 没有右子节点，因此 'p' 等于 NULL。

现在条件 p!= NULL 为假，因此控制跳出内层循环。控制移到外层循环，我们将检查队列是否为空。由于队列不为空，因此控制移入循环，元素将从队列中出队，现在 'p' 指向节点 'd'。

在 **第 0 次迭代中**，

由于 p!= NULL，因此内层循环的条件为真。它将打印 'b'。

p->left 不为 Null // 'd'，因此 p->left 条件为真，它将 'd' 入队，如下所示

p = b->right // 'e'

在 **第 1 次迭代中**，条件 **p!=NULL** 为真，因为 'p' 指向节点 'e'。它将打印 'e'。

p-> left 为 Null，因此 p->left 条件为假。

p = e->right // 由于节点 'e' 没有右子节点，因此 'p' 包含 NULL 值。

现在条件 **p!= NULL** 为假，因此控制跳出内层循环。控制移到外层循环，我们将检查队列是否为空。由于队列不为空，因此控制移入循环。首先，元素将从队列中出队，现在 'p' 指向节点 'f'。

在 **第 0 次迭代中**，

由于 **p!= NULL**，因此内层循环的条件为真。它将打印 'f'。

p-> left 不为 NULL，因此 p-> left 条件为真。

p = f->right // 'k'

在 **第 1 次迭代中**，条件 **p!= NULL** 为真，因为 'p' 指向节点 'k'。它将打印 'k'。

p-> left 为 Null，因此 p-> left 条件为假。

p = k-> right // 由于节点 'k' 没有右子节点，因此 'p' 包含 NULL 值。

现在条件 **p!= NULL** 为假，因此控制跳出内层循环。控制移到外层循环，我们将检查队列是否为空。由于队列不为空，因此控制移入循环。首先，元素将从队列中出队，现在 'p' 指向节点 'm'。

在 **第 0 次迭代中**，

由于条件 'p!= NULL' 为真，因此控制进入内层循环。它将打印 'm'。

p-> left 为 Null，因此 p-> left 条件为假。

p = m -> right // 由于节点 'm' 没有右子节点，因此 'p' 包含 NULL 值。

现在条件 **p!= NULL** 为假，因此控制跳出内层循环。控制移到外层循环，我们将检查队列是否为空。由于队列不为空，因此控制移入循环。首先，元素将从队列中出队，现在 'p' 指向节点 'd'。

在 **第 0 次迭代中**，

由于条件 p!= NULL 为真，因此控制进入循环。它将打印 'd'。

p-> left 不为 NULL // 'h'；因此，p->left 条件为真，它将 'h' 入队，如下所示

p = d->right; // i;

在 **第 1 次迭代中**，

由于条件 **p!= NULL** 为真，因为 'p' 指向节点 'i'，因此控制进入循环。它将打印 'i'。

p-> left 为 Null，因为节点 'i' 没有左子节点，因此 p-> left 条件为假。

p = i->right; // 由于节点 'i' 没有右子节点；因此，'p' 指向 NULL 值。

现在条件 **p!= NULL** 为假，因此控制跳出内层循环。控制移到外层循环，我们将检查队列是否为空。由于队列不为空，因此控制移入循环。首先，元素将从队列中出队，现在 'p' 指向节点 'j'。

在 **第 0 次迭代中**，

由于条件 **p!= NULL** 为真，因为 'p' 指向节点 'j'，因此控制进入循环。它将打印 'j'。

p->left 为 Null，因为节点 'j' 没有左子节点。

p = j->right; 由于节点 'j' 没有右子节点，因此 'p' 包含 NULL 值。

现在条件 **p!= NULL** 为假，因此控制跳出内层循环。控制移到外层循环，我们将检查队列是否为空。由于队列不为空，因此控制移入循环。首先，元素将从队列中出队，现在 'p' 指向节点 'h'。

在 **第 0 次迭代中**，

由于条件 **p!= NULL** 为真，因为 'p' 指向节点 'h'，因此控制进入循环。它将打印 'h'。

p->left 为 Null，因为节点 'h' 没有左子节点。

p= h->right; 由于节点 'h' 没有右子节点，因此 'p' 包含 NULL 值。

现在条件 **p!= NULL** 为假，因此控制跳出内层循环。控制移到外层循环，我们将检查队列是否为空。由于队列为空，因此控制跳出外层循环。