PHP构造二叉树算法示例

PHP构造二叉树算法示例

二叉树（Binary Tree），是由节点组成，每个节点最多有两个子树的树结构。在二叉树中，如果把所有非叶子节点的度看做2，则每个节点的度为0、1或2，因此可以看做是一种特殊的树。

如何在PHP中构造二叉树呢？下面将详细讲解PHP构造二叉树算法示例的完整攻略。

步骤1. 定义节点类

二叉树由节点组成，因此第一步是定义节点类。

class TreeNode {
    public $val;
    public $left = null;
    public $right = null;

    function __construct($val) {
        $this->val = $val;
    }
}

在上面的代码中，定义了一个名为TreeNode的类，这个类包含3个属性，$val表示节点的值，$left和$right分别表示左子树和右子树。

步骤2. 通过递归构造二叉树

递归法是构造二叉树的一种常用方法。该方法从根节点开始，先构造左子树，再构造右子树，最后将左右子树合并到根节点。

下面是一个递归构造二叉树的示例。

function buildTree($preorder, $inorder) {
    if (empty($preorder)) {
        return null;
    }

    // 取前序遍历的第一个元素作为根节点
    $rootVal = array_shift($preorder);
    $root = new TreeNode($rootVal);

    // 在中序遍历中，找到根节点所在位置
    $index = array_search($rootVal, $inorder);

    // 构造左子树
    $root->left = buildTree(array_slice($preorder, 0, $index), array_slice($inorder, 0, $index));

    // 构造右子树
    $root->right = buildTree(array_slice($preorder, $index), array_slice($inorder, $index + 1));

    return $root;
}

在上面的代码中，$preorder表示二叉树的前序遍历序列，$inorder表示二叉树的中序遍历序列。算法的思想是，先取前序遍历序列的第一个元素作为根节点，在中序遍历中找到根节点所在位置，将中序遍历序列分为两段，左边的是左子树，右边的是右子树。然后递归构造左子树和右子树，最后将左右子树合并到根节点。最后返回根节点即可。

示例1：构造一棵二叉树

假设有一棵二叉树，前序遍历序列为[3, 9, 20, 15, 7]，中序遍历序列为[9, 3, 15, 20, 7]，构造这棵二叉树的过程如下：

1. 取前序遍历序列的第一个元素3作为根节点。
2. 在中序遍历中，找到根节点所在位置，即中序遍历序列中的第二个元素9。
3. 将中序遍历序列分为两段，左边的是左子树的中序遍历序列[9]，右边的是右子树的中序遍历序列[15, 20, 7]。
4. 用左子树的中序遍历序列[9]和前序遍历序列[9]递归构造左子树，得到一个节点9，将其作为根节点的左子节点。
5. 用右子树的中序遍历序列[15, 20, 7]和前序遍历序列[20, 15, 7]递归构造右子树，得到一个节点20和一个节点7，将20作为根节点的右子节点，将7作为20的右子节点。
6. 将左右子树合并到根节点3。
7. 返回根节点3。

最终得到的二叉树如下：

     3
   /   \
  9    20
      /  \
    15    7

示例2：构造一棵完整二叉树

完整二叉树是指除了最后一层节点不满足节点个数为2的幂次方外，其它层的节点个数都是已知的且满足节点个数为2的幂次方。对于一棵完整二叉树，可以使用数组来表示，数组的下标表示节点的编号，节点编号从1开始。

下面是一个构造一棵完整二叉树的示例。

function buildCompleteTree($nums) {
    $n = count($nums);
    $nodes = array_fill(1, $n, null);

    // 构造所有节点
    for ($i = 1; $i <= $n; $i++) {
        $nodes[$i] = new TreeNode($nums[$i - 1]);
    }

    // 构造父子关系
    for ($i = 1; $i <= intval($n / 2); $i++) {
        if ($i * 2 <= $n) {
            $nodes[$i]->left = $nodes[$i * 2];
        }
        if ($i * 2 + 1 <= $n) {
            $nodes[$i]->right = $nodes[$i * 2 + 1];
        }
    }

    return $nodes[1];
}

在上面的代码中，$nums表示二叉树的节点值数组。算法的思想是，首先构造所有节点，然后构造父子关系。节点$i$的左儿子是节点$2i$，右儿子是节点$2i+1$，这是完整二叉树的特点。最后返回根节点即可。

示例：构造一个完整二叉树

假设有一棵完整二叉树，节点值数组为[1, 2, 3, 4, 5, 6]，构造这棵完整二叉树的过程如下：

1. 构造所有节点，得到6个节点，即节点1到节点6。
2. 构造父子关系，根节点是节点1，左儿子是节点2，右儿子是节点3，节点2的左儿子是节点4，右儿子是节点5，节点3的左儿子是节点6。
3. 返回根节点1。

最终得到的二叉树如下：

     1
   /   \
  2     3
 / \   /
4   5 6

上述就是构造二叉树的 PHP 示例，希望对你有所帮助。