PHP面试问答题：说说你对二叉树的理解

terry 2年前 (2023-09-25) 阅读数 49 #后端开发

树的理解和实现

到目前为止我们对数据结构的探索只触及了线性部分。无论我们使用数组、链表、堆栈还是队列，它们都是线性数据结构。我们已经看到了线性数据结构操作的复杂性。通常插入和删除的复杂度可以用O(1)来表示。搜索有点复杂，需要 O(n) 复杂度。唯一的例外是 PHP 数组，它本质上是哈希表，如果以这种方式管理索引或键，复杂度可以达到 O(1)。为了解决这个问题，我们可以使用分层数据结构来代替线性数据结构。分层数据可以解决许多线性数据结构难以解决的问题。

当我们谈论家谱、组织结构和网络连接图时，我们实际上是在谈论分层数据。树是一种特殊的抽象数据类型（ADT）。与链表不同，树是分层的。

树的定义和特征

树是由边连接的节点或顶点的层次集合。树不能有环，边仅存在于节点与其降序节点或子节点之间。同一父节点的两个子节点之间不应有边。每个节点可以有一个父节点，除非它是顶级节点（也称为根节点）。每棵树只能有一个根节点。每个节点可以有零个或多个子节点。下图中，A 是父节点，B、C、D 是 A 的子节点。也可以说，A 是 B、C、D 的父节点。B、C、D 被称为兄弟节点，因为它们来自同一个父节点A。

没有子节点的节点称为叶子。上图中，K、L、F、G、M、I、J 是叶子节点。叶节点也称为远程节点或端节点。除根之外的节点都至少有一个子节点，称为内部节点。这里B、C、D、E、H是内部节点。以下是用于描述树的数据结构的一些其他常用术语：

后代：这是可以通过迭代过程从父节点到达的节点。例如，M 是上图中 C 的后代。

祖先：这是从子节点到父节点可以重复到达的节点。例如，B 是 L 的祖先。

度：给定父节点的子节点总数称为其度。在我们的示例中，A 为 3 度，B 为 1 度，C 为 3 度，D 为 2 度。

路径：从源节点到目的节点的节点和边的序列称为两个节点之间的路径。路径的长度是路径中节点的数量。从A到M的路径为A-C-H-M，路径长度为4。

节点高度：节点的高度由该节点与最深节点之间的边数决定。例如，节点B的高度为2。

Level：Level代表节点生成。如果父节点位于 N 层，则子节点位于 N+1 层。因此，层次结构是由节点和根之间的边数定义的。

A在0楼

B、C、D在1楼

E、F、G、H、I、J在2楼

K、L、M在全部位于三楼。

树的高度：树的高度由根节点的高度决定。上图中树的高度为3。

子树：在树结构中，每个子树递归地形成一个子树。换句话说，一棵树由许多子树组成。例如，B和E、K和L形成子树，E、K和L形成子树，并且它们在各自不同的阴影下被识别。

深度：节点的深度由该节点与根节点之间的边数决定。例如，H 的深度为 2，L 的深度为 3。

森林：森林由一群或多棵互不相连的树木组成。

遍历：表示按照特定顺序访问节点的过程。

键：用于搜索，指定节点的值。

使用 PHP 实现树

到目前为止，我们已经了解了树的不同属性。如果我们将树与现实世界的例子进行比较，我们会发现组织结构或家谱可以用数字来表示。对于一个组织结构来说，有一个根节点，可以是公司的CEO，其次是CXO级别的员工，再后面是其他级别的员工。这里我们不限制任何特定节点的任何程度。这意味着一个节点可以有多个子节点。因此，下面是一个节点结构，我们可以在其中定义节点属性、父节点和子节点：

class TreeNode
{
    public $data = null;

    public $children = [];

    public function __construct(string $data = null)
    {
        $this->data = $data;
    }

    public function addChildren(TreeNode $treeNode)
    {
        $this->children[] = $treeNode;
    }
}
复制代码

我们可以看到，我们有两个公共属性声明为数据和子节点。我们还有一种将子节点添加到特定节点的方法。这里我们只是将新的子节点添加到数组的末尾。树是一种递归结构，可以帮助我们递归地构建树并递归地遍历树。

现在我们有了节点，让我们构建一个树结构，它定义树的根节点，并允许我们遍历整个树。所以基本的树结构将如下所示：

class Tree
{
    public $root = null;

    public function __construct(TreeNode $treeNode)
    {
        $this->root = $treeNode;
    }

    public function traverse(TreeNode $treeNode, int $level = 0)
    {
        if ($treeNode) {
            echo str_repeat('-', $level) . $treeNode->data . PHP_EOL;

            foreach ($treeNode->children as $child) {
                $this->traverse($child, $level + 1);
            }
        }
    }
}
复制代码

前面的代码显示了一个简单的树类，我们可以在其中存储基本节点引用并从任何节点遍历树。在遍历部分，我们访问每个子节点，然后立即递归调用遍历方法来获取当前节点的子节点。我们传递一个级别并在节点名称的开头打印一个破折号（-），以便我们可以轻松理解子级别数据。

require './TreeNode.php';

$ceo = new TreeNode('ceo');

$tree = new Tree($ceo);

$cfo = new TreeNode('cfo');
$cto = new TreeNode('cto');
$cmo = new TreeNode('cmo');
$coo = new TreeNode('coo');

$ceo->addChildren($cfo);
$ceo->addChildren($cto);
$ceo->addChildren($cmo);
$ceo->addChildren($coo);

$seniorArchitect = new TreeNode("Senior Architect");
$softwareEngineer = new TreeNode("SoftwareEngineer");

$userInterfaceDesigner = new TreeNode("userInterface Designer");
$qualityAssuranceEngineer = new TreeNode("qualityAssurance Engineer");


$cto->addChildren($seniorArchitect);
$seniorArchitect->addChildren($softwareEngineer);

$cto->addChildren($userInterfaceDesigner);
$cto->addChildren($qualityAssuranceEngineer);

$tree->traverse($tree->root);
复制代码

最终输出结果与此类似。你可以在这里看到完整的代码