PHP 函数中如何使用递归来实现二叉树？

使用 php 递归实现二叉树涉及：创建一个二叉树节点类。使用递归实现插入、前序、中序和后序遍历函数。创建一个包含值的二叉树，并按上述遍历方式输出结果。

使用 PHP 递归实现二叉树

什么是二叉树？

二叉树是一种数据结构，其中每个节点最多有左右两个子节点。

立即学习“PHP免费学习笔记（深入）”；

什么是递归？

递归是一种函数调用自身的编程技术，在处理树形结构时非常有用。

唱鸭

音乐创作全流程的AI自动作曲工具，集 AI 辅助作词、AI 自动作曲、编曲、混音于一体

下载

如何使用递归实现二叉树？

我们可以使用 PHP 类来创建一个二叉树节点，并使用递归来遍历树：

class Node {
    public $value;
    public $left;
    public $right;

    public function __construct($value) {
        $this->value = $value;
        $this->left = null;
        $this->right = null;
    }
}

function insert($root, $value) {
    if (!$root) {
        return new Node($value);
    } elseif ($value < $root->value) {
        $root->left = insert($root->left, $value);
    } else {
        $root->right = insert($root->right, $value);
    }
    return $root;
}

function preOrder($root) {
    if ($root) {
        echo $root->value . " ";
        preOrder($root->left);
        preOrder($root->right);
    }
}

function inOrder($root) {
    if ($root) {
        inOrder($root->left);
        echo $root->value . " ";
        inOrder($root->right);
    }
}

function postOrder($root) {
    if ($root) {
        postOrder($root->left);
        postOrder($root->right);
        echo $root->value . " ";
    }
}

实战案例

创建一个包含值的二叉树，并按前序、中序和后序遍历它：

$root = null;
$root = insert($root, 10);
$root = insert($root, 5);
$root = insert($root, 15);
$root = insert($root, 2);
$root = insert($root, 7);
$root = insert($root, 12);
$root = insert($root, 20);

echo "Preorder: ";
preOrder($root);
echo "\n";

echo "Inorder: ";
inOrder($root);
echo "\n";

echo "Postorder: ";
postOrder($root);

输出：

Preorder: 10 5 2 7 15 12 20
Inorder: 2 5 7 10 12 15 20
Postorder: 2 7 5 12 20 15 10