使用 php 递归实现二叉树涉及:创建一个二叉树节点类。使用递归实现插入、前序、中序和后序遍历函数。创建一个包含值的二叉树,并按上述遍历方式输出结果。
使用 PHP 递归实现二叉树
什么是二叉树?
二叉树是一种数据结构,其中每个节点最多有左右两个子节点。
立即学习“PHP免费学习笔记(深入)”;
什么是递归?
递归是一种函数调用自身的编程技术,在处理树形结构时非常有用。
如何使用递归实现二叉树?
我们可以使用 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