编程

PHP 中的树和树遍历

743 2024-02-20 20:48:00

我将在本文中介绍树结构。什么是树,如何使用以及何种情况下使用、

请注意,这只是一个基本的介绍,而不是整个故事。我甚至可能在某个地方错了,如果你认为我搞错了:请在评论中告诉我,或者给我发私信。

🌳 什么是树?

要回答这个问题,我们首先要看一下图(Graph)。在图论中,图(Graph)是以某种方式相互关联的数据点(或节点 Node)的(视觉)结构。例如,这种关系可以是有子节点或兄弟节点的父节点。这些节点(Node)之间的关系由一条线/顶点(或边)表示。在“正常”图形中,这些关系可以遍布各处。每个节点都可以连接到另一个甚至多个节点。边缘可以在任何地方弯曲。

那么什么是树呢?它是 Graph 的一个子集,只允许任何两个节点通过一条路径连接,而不是无限路径连接。

图(Graph) vs. 树(Tree)

比如:父节点 Parent 有两个子节点: Child 1Child 2,图 Graph 允许有这些关系:

  • Parent <-> Child 1
  • Parent <-> Child 2
  • Child 1 <-> Child 2

这也被称为循环图( cyclic graph),因为它有一个循环(多个节点连接到相同的节点,在表示中创建循环)。

注意:图不一定有循环,但可以是。

而树(Tree)只允许像这样的关系:

  • Parent <-> Child 1
  • Parent <-> Child 2

或者:

  • Parent <-> Child 1
  • Child 1 <-> Child 2

一幅画胜过千言万语;让我们看一个(简单的)图形与树。

请注意,在树中,每对节点只通过一条边连接,因此永远不会有任何循环。这就是为什么树是非循环图(acyclic graphs)的原因。

什么元素组成一棵树呢?

正如我们在上图中看到的,树的顶部总是有一个节点。这称为根节点(Root Node)。

节点(Node)可以有值,但不强制要求。 它可以有、也可以没有子节点。一个节点如果没有子节点,可以称之为叶子(Leaf) 🍃 .

任何节点都可以有多个子节点,但有些树只允许每个节点有最大数量的子节点。这些被称为 N 元树(N-ary Trees),其中 N 表示每个节点的最大子级数量。可能这些树类型中最著名的是二进制树,它只允许2个子节点;左(left)和右(right)。

关于树的结构还有很多要讲的,但需要基本的理解;这应该足够了。让我们继续行动吧!

🚶 遍历树

树作为一种视觉展示很好,不过你也可以遍历树的完整结构并使用每个节点的数据。当遍历一棵树时,我们会访问树中的每个节点一次。而访问只是一个“在此执行操作”的代词。这个操作可以是任何你想要的:打印、保存或更改。无论你想对节点做什么,每次遍历每个节点都可以访问一次。

遍历一棵树有很多方法。你可以 Zig-zag,随意挑选一个顺序;但树遍历有两种广谱类型:深度优先和宽度优先

↙️ 深度优先遍历树

深度优先树遍历是一种通过拾取特定分支来遍历树的算法;并继续向下移动到分支中,直到它到达末端。只有到那时,它才会返回到另一个分支。

在深度优先树遍历的领域内,有几种类型的遍历;其中三种最常见:前序遍历(PreOrder)、中序遍历(InOrder)和后序遍历(PostOrder)

这些算法是递归的;这意味着它们将在子节点及其子节点上重新开始,依此类推。

在接下来的每个例子中,我们将从下面的二进制树中返回每个节点的值。

用 PHP 表示该树如下:

$root = [
    'value' => 4,
    'children' => [
        [
            'value' => 2,
            'children' => [
                ['value' => 1],
                ['value' => 3],
            ],
        ],
        [
            'value' => 6,
            'children' => [
                ['value' => 5],
                ['value' => 7],
            ],
        ],
    ],
];
 
// Helper function to visualize the visiting of a node.
function visit(array $node): int
{
    return $node['value'];
}

前序遍历 (节点,左(to),右)

当遍历一棵树时,我们从根节点开始,然后应用算法。

在前序算法中,将首先访问一个节点,然后从左到右访问它的子节点。这个过程是递归的;这意味着它将从它的子节点身上重新开始,等等。

因此,该遍历的输出将为:4、2、1、3、6、5、7

首先我们访问 4,然后转到它的第一个子(左)节点,并再次应用相同的算法。因此,从该节点中,我们首先访问 2,然后转到它的第一个(左)子节点,并再次应用算法。当我们达到 1 时,我们命中了一个叶节点(Leaf)。它没有子节点,因此没有左节点或右节点的输出。我们已经达到了这个树枝的最大深度。

所以现在我们回溯到前一个节点 2 并完成它的算法。我们向右走:3。此节点也是一个叶子。所以我们回溯到上一个节点:2。现在已经完成;所以我们进一步回溯到 4。我们向右走并访问:6,算法重复:向左走:5;回溯并向右走:7

示例代码
前序遍历的 PHP 实现:

function preOrder(array $node)
{
    // First we visit the node itself.
    $output[] = visit($node);
 
    // Then apply the algorithm to every child from left -> right.
    foreach ($node['children'] ?? [] as $child) {
        $output[] = preOrder($child);
    }
 
    return implode(', ', $output);
}
 
echo preOrder($root); // 4, 2, 1, 3, 6, 5, 7

中序遍历(左,节点,右)

中序遍历的算法在二叉树上最有意义。这是因为我们先向左走,然后访问节点本身,然后向右走。如果有3个子节点,我们需要选择如何处理中间节点;befóre 或 áfter 节点本身。

运行此算法将产生以下输出:1,2,3,4,5,6,7

因为该算法首先访问左节点,所以我们一直向下遍历,直到到达最左侧的节点 1。因为它没有子节点,我们不能再向左走了。因此,我们访问节点本身。我们也不能向右走;所以我们回溯到上一个节点:2。这已经耗尽了整个的左分支,所以我们访问节点本身。然后我们转到右侧节点,并重复该算法…,等等

示例代码
PHP 实现的中序遍历:

function inOrder(array $node)
{
    // We extract a possible left and right node for clarity.
    $left = $node['children'][0] ?? null;
    $right = $node['children'][1] ?? null;
 
    // We'll apply the algorithm on the left node first.
    if ($left) {
        $output[] = inOrder($left);
    }
 
    // Now we visit the node itself.
    $output[] = visit($node);
 
    // And apply the algorithm on the right node.
    if ($right) {
        $output[] = inOrder($right);
    }
 
    return implode(', ', $output);
}
 
echo inOrder($root); // 1, 2, 3, 4, 5, 6, 7

后序(InOrder)的名称(很可能)是基于它按升序访问每个节点的事实。但这只适用于所谓的排序二叉树。在这种类型的树中,每个左边的子节点都小于节点本身,右边的子节点大于节点本身。就像我们的示例树一样。

后序遍历(左(to), 右, 节点)

在后序遍历中,我们首先访问节点的子节点(从左到右),然后访问节点本身。由于该算法的递归性,输出将为:1,3,2,5,7,6,4

由于我们已经对其他算法进行了两次(令人疲惫的)演练,而这一次的过程与前序遍历几乎相同,我将让你自己尝试这一次。

示例代码
后序遍历的 PHP 实现:

function postOrder(array $node)
{
    // First we'll apply the algorithm on every child from left -> right.
    foreach ($node['children'] ?? [] as $child) {
        $output[] = postOrder($child);
    }
 
    // Then we visit the node itself.
    $output[] = visit($node);
 
    return implode(', ', $output);
}
 
echo postOrder($root); // 1, 3, 2, 5, 7, 6, 4

↔️ 广度优先遍历

在广度优先树遍历中,我们从根节点开始,然后访问子节点。但与深度优先方法不同,该算法不是递归应用的;而是更线性。它是逐级进行的,因此也称为层次遍历(LevelOrder)。该算法通常在树的深度未知甚至是动态的情况下使用。

树层次遍历

层次遍历的算法与前序遍历很相似,不过因为广度优先,实际上在访问下一级子节点前先访问子节点。因此,首先它访问根节点 4,然后是它的子节点:26,然后才是 26 的子节点。i

为了正确看待这一点,LevelOrder 层次遍历的输出将是:4,2,6,1,3,5,7。在进入下一个级别之前,每个级别都会被访问。

要实现此行为,可以使用队列。这是一个简单的列表或数组,当访问节点时,我们会将每个子节点附加到该列表或数组中。首先将根节点添加到队列中,然后在访问队列的第一个节点的队列上启动递归函数;将其子项添加到队列中,然后重新开始;直到整个队列为空。

示例代码
层次遍历的 PHP 实现:

function levelOrder(array $queue, array $output = [])
{
    // If the queue is empty, return the output.
    if (count($queue) === 0) {
        return implode(', ', $output);
    }
 
    // Take the first item from the queue and visit it.
    $node = array_shift($queue);
    $output[] = visit($node);
 
    // Add any children to the queue.
    foreach ($node['children'] ?? [] as $child) {
        $queue[] = $child;
    }
 
    // Repeat the algorithm with the rest of the queue.
    return levelOrder($queue, $output);
}
 
// Put the root on the queue.
$queue = [$root];
echo levelOrder($queue); // 4, 2, 6, 1, 3, 5, 7

🤔 树遍历用途

如果你和我一样,喜欢学习这样的东西;但也希望/需要一个实际的理由来使用它。所以让我们进一步探讨一下。

注意:对于这个示例,你绝对可以不需要树。就像生活中的大多数东西一样,你可以选择使用它;如果你喜欢的话。

示例:创建文档

假设我们有一个内容管理系统(CMS),用于创建文档(或书本)的章节层次结构。它有如下部分:

  • 一个封面 (C)
  • 一个目录 (TOC)
  • 章节 1~3 并带有一些嵌套的子章节

由于有嵌套和层次结构,你的CMS可能已经有了树状结构。所以,让我们接受这一点,并将其放在一棵树上,如下所示:

由于树结构需要根节点,我们选择封面作为根节点。它的子节点为目录及各个主章节。主章节也都有其子章节

渲染整个文档(前序遍历)

如果我们想将每个部分组合成一个单一的逻辑流动文档,我们可以使用前序遍历访问节点。为什么?因为我们首先访问节点本身,然后使用深度优先算法从左到右访问其子节点。这意味着输出将是 C、TOC、1、1.1、1.2、1.3、2、2.1、2.2、3、3.1

使用前序遍历的另一个常见任务是克隆树。由于我们以正确的顺序访问每个节点,因此你可以完整克隆每个节点,并设置正确的父节点(因为它已经存在)。

从树中移除页面(后序遍历)

假设我们不需要主章节 2,但我们确实需要它的子章节 2.12.2(以及可能的孙子章节)。如果我们使用前序遍历,我们将首先访问主节点。如果我们要删除那个节点;你也会失去所有子节点。为了防止这种情况,我们可以使用后序遍历。由于这基本上是自下而上的,我们可以将2.12.2 提升一个级别(通过更新父节点),然后安全地删除章节 2

示例:索引网站(层次遍历)

此例中,我们将索引一个网站。我们的根节点是网站的主页。因为我们不知道会遇到多少链接,我们也不知道树的深度。在这种情况下,最好使用广度优先遍历。因为它一级一级地遍历一棵树;如果这个过程太深,我们可以停止。我们可以设置最大深度。深度优先的方法可能会在分支再次出现之前让你沿着分支深入下去。不理想。

当我们从根节点开始时,我们访问(也称为索引)它。然后我们找到页面上的每个(内部)链接,并将这些页面添加到队列中;并重复该过程,直到队列为空。

为了防止可能的无限循环,因为链接可以在多个页面上并链接回这些页面,你需要跟踪已访问的每个节点,并且只有在尚未访问的情况下才将其添加到队列中。

🔗 有用的链接

📤 PHP有一些使用数据结构的助手类。例如,你可以使用这个 SplQueue 来实现广度优先遍历。

感谢阅读

虽然这篇文章与PHP不是很相关;我认为对树原理和遍历算法有一个基本的了解是很好的。你永远不知道在什么情况下你最终需要这个。

  •  
PHP