PHP 二叉树的构建和遍历

网上PHP关于二叉树的内容比较少，毕竟实际开发中用得不多。这里把自己学习的结果分享出来，共勉。

<?php

/**
 * 节点类
 */
class TreeNode
{

    private ?self $left = null;

    private ?self $right = null;

    private int $value;

    public function __construct(int $value)
    {
        $this->value = $value;
    }

    /**
     * @return int
     */
    public function getValue(): int
    {
        return $this->value;
    }

    /**
     * @return self|null
     */
    public function getLeft(): ?self
    {
        return $this->left;
    }

    /**
     * @return self|null
     */
    public function getRight(): ?self
    {
        return $this->right;
    }

    /**
     * @param self $left
     */
    public function setLeft(self $left): void
    {
        $this->left = $left;
    }

    /**
     * @param self $right
     */
    public function setRight(self $right): void
    {
        $this->right = $right;
    }
}

/**
 * 树
 */
class Tree
{

    private TreeNode $root;

    public function __construct(array $dataSet1, array $dataSet2, string $method)
    {
        switch ($method) {
            case 'pre': // 根据前序和中序遍历的结果构建
                $this->root = $this->makeFromPreOrderAndInOrder($dataSet1, $dataSet2);
                break;
            case 'post':// 根据后序和中序遍历的结果构建
                $this->root = $this->makeFromPostOrderAndInOrder($dataSet1, $dataSet2);
                break;
            default:
                throw new InvalidArgumentException;
        }
    }

    /**
     * 从前序遍历和中序遍历的结果构建原来的树
     * 解法：先序中的首元素a 必为该二叉树的根结点，在中序序列里a之前的元素一定是a的左子树部分，a之后的元素一定为a的右子树部分。
     *
     * @param int[] $pre
     * @param int[] $in
     * @return TreeNode
     */
    public function makeFromPreOrderAndInOrder(array $pre, array $in): TreeNode
    {
        $currentRoot = $pre[0]; // 前序遍历的首元素肯定是根节点
        $currentRootPos = array_search($currentRoot, $in, true);
        $left = array_slice($in, 0, $currentRootPos);
        $right = array_slice($in, $currentRootPos + 1);
        $preLeft = array_slice($pre, 1, $currentRootPos);
        $preRight = array_slice($pre, $currentRootPos + 1);
        $currentRoot = new TreeNode($currentRoot);

        if ($left) {
            $currentRoot->setLeft($this->makeFromPreOrderAndInOrder($preLeft, $left));
        }

        if ($right) {
            $currentRoot->setRight($this->makeFromPreOrderAndInOrder($preRight, $right));
        }

        return $currentRoot;
    }

    /**
     * 从后序遍历和中序遍历的结果重新构建树
     * 思路同上，只是反了过来
     *
     * @param array $post
     * @param array $in
     * @return TreeNode
     */
    public function makeFromPostOrderAndInOrder(array $post, array $in): TreeNode
    {
        $currentRoot = $post[count($post) - 1]; // 后序遍历的最后一个元素是根节点
        $currentRootPos = array_search($currentRoot, $in, true);
        $left = array_slice($in, 0, $currentRootPos);
        $right = array_slice($in, $currentRootPos + 1);
        $postLeft = array_slice($post, 0, $currentRootPos);
        $postRight = array_slice($post, $currentRootPos, -1);

        $currentRoot = new TreeNode($currentRoot);

        if ($left) {
            $currentRoot->setLeft($this->makeFromPostOrderAndInOrder($postLeft, $left));
        }

        if ($right) {
            $currentRoot->setRight($this->makeFromPostOrderAndInOrder($postRight, $right));
        }

        return $currentRoot;
    }

    /**
     * 前序遍历
     *
     * @param TreeNode|null $treeNode
     * @return array
     */
    public function preOrderTraversal(TreeNode $treeNode = null): array
    {
        if (is_null($treeNode)) {
            $treeNode = $this->root;
        }

        $ret = [];

        $ret[] = $treeNode->getValue(); // 节点马上输出

        if ($treeNode->getLeft()) {
            $ret = array_merge($ret, $this->preOrderTraversal($treeNode->getLeft()));
        }
        if ($treeNode->getRight()) {
            $ret = array_merge($ret, $this->preOrderTraversal($treeNode->getRight()));
        }

        return $ret;
    }

    /**
     * 中序遍历
     *
     * @param TreeNode $treeNode
     * @return array
     */
    public function inOrderTraversal(TreeNode $treeNode = null): array
    {
        if (is_null($treeNode)) {
            $treeNode = $this->root;
        }

        $ret = [];

        if ($treeNode->getLeft()) {
            $ret = array_merge($ret, $this->inOrderTraversal($treeNode->getLeft()));
        }

        $ret[] = $treeNode->getValue(); //只有当遍历完左节点后才输出

        if ($treeNode->getRight()) {
            $ret = array_merge($ret, $this->inOrderTraversal($treeNode->getRight()));
        }

        return $ret;
    }

    /**
     * 后序遍历
     *
     * @param TreeNode|null $treeNode
     * @return array
     */
    public function postOrderTraversal(TreeNode $treeNode = null): array
    {
        if (is_null($treeNode)) {
            $treeNode = $this->root;
        }

        $ret = [];

        if ($treeNode->getLeft()) {
            $ret = array_merge($ret, $this->postOrderTraversal($treeNode->getLeft()));
        }

        if ($treeNode->getRight()) {
            $ret = array_merge($ret, $this->postOrderTraversal($treeNode->getRight()));
        }

        $ret[] = $treeNode->getValue(); // 遍历完左右节点后才输出

        return $ret;
    }
}

function exampleTree()
{
    $n6 = new TreeNode(6);
    $n6->setLeft(new TreeNode(7));
    $n6->setRight(new TreeNode(8));
    $n4 = new TreeNode(4);
    $n4->setRight($n6);
    $n2 = new TreeNode(2);
    $n2->setLeft($n4);
    $n1 = new TreeNode(1);
    $n1->setLeft($n2);
    $n3 = new TreeNode(3);
    $n3->setRight(new TreeNode(5));
    $n1->setRight($n3);
    return $n1;
}


$pre = [1, 2, 4, 6, 7, 8, 3, 5];
$in = [4, 7, 6, 8, 2, 1, 3, 5];
$post = [7, 8, 6, 4, 2, 5, 3, 1];

$tree = new Tree($post, $in, 'post');

var_export($tree->preOrderTraversal());