php树类技巧_PHP面试说说你理解的二叉树吧

每当我们评论辩论家庭族谱、组织构造和网络连接图时，我们实际上都在评论辩论分层数据。
树是一种分外的抽象数据类型（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。

层次：层次代表节点的天生。
如果父节点处于层次N，则其子节点将位于N+ 1层次。
因此，该层次由节点和根之间的边数定义。

A在0层

B，C和D是1层

E，F，G，H，I，J是2层

K，L，M都在第3层。

树的高度：树的高度是由它的根节点的高度定义的。
上图树的高度是3。

子树：在树构造中，每个孩子递归地形成子树。
换句话说，树由许多子树组成。
例如，B和E、K和L构成了一个子树，E、K和 L构成了一个子树，每个不同的阴影中都对它们进行了识别。

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

森林：森林是由一组或更多的不相交的树组成。

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

键：用于搜索，表示节点的值。

到目前为止，我们已经理解了树的不同属性。
如果我们比拟树和现实的例子，我们创造组织构造或族谱树可以用数表示。
对付一个组织构造，有一个根节点可以是公司的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); } } }}

前面的代码显示了一个大略的树类，我们可以存储根节点引用，也可以从任意节点遍历树。
在遍历部分中，我们访问每个子节点，然后立即递归调用遍历方法来获取当前节点的子节点。
我们通过一个level，在节点名称的开头打印出一个破折号（-），这样我们就可以很随意马虎地理解子级数据。

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);

末了输出的结果类似这样，完全的代码可以在这里看到

不同类型的树

在代码天下中有很多不同类型的树，我们一起来看下。

二叉树是一种基本的树构造，二叉树的每个节点最多有两个孩子。

二叉搜索树

二叉搜索树（BST）是一种分外类型的二叉树，个中节点以排序的办法存储，即在任何给定的点上，节点值必须大于或即是左子节点值，小于右子节点值。
每个节点都必须知足这个属性，这便是二叉搜索树。
二叉搜索树算法总是优于线性搜索，它的韶光繁芜度是O(n)，我们将在往后的内容详细阐明。

自平衡二叉树

自平衡二叉搜索树或高度平衡二叉搜索树是一种分外类型的二叉搜索树，它试图通过自动调度来只管即便保持树的高度或层次尽可能小。
下图左侧的展示了二叉搜索树，右边的是自平衡二叉搜索树：

高度平衡的二叉树总是更好的选择，由于它比常规BST有助于更快地搜索操作。
自平衡或高度平衡二叉搜索树有不同的实现。
一些常见到的如下：