Comment implémenter des opérations de traversée d'arbre binaire et de recherche en PHP à l'aide d'algorithmes récursifs ?

Comment utiliser un algorithme récursif pour implémenter des opérations de traversée d'arbre binaire et de recherche en PHP ?

L'arbre binaire est une structure de données couramment utilisée et ses opérations incluent le parcours et la recherche. En PHP, nous pouvons utiliser des algorithmes récursifs pour implémenter ces opérations. Ce qui suit présente comment utiliser des algorithmes récursifs pour implémenter des opérations de traversée d'arbre binaire et de recherche en PHP, et fournit des exemples de code spécifiques.

1. Définir la classe de nœuds d'arbre binaire

Tout d'abord, nous devons définir une classe de nœuds d'arbre binaire, qui contient la valeur du nœud et des références aux nœuds enfants gauche et droit. Le code est le suivant :

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

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

2. Créer un arbre binaire

On peut utiliser le code suivant pour créer un arbre binaire simple :

// 创建二叉树
$root = new TreeNode(1);
$root->left = new TreeNode(2);
$root->right = new TreeNode(3);
$root->left->left = new TreeNode(4);
$root->left->right = new TreeNode(5);
$root->right->left = new TreeNode(6);
$root->right->right = new TreeNode(7);

3. Parcours d'un arbre binaire

Le parcours d'un arbre binaire est divisé en parcours pré-commande, parcours dans l'ordre et parcours post-commande. Les implémentations récursives de ces trois méthodes de parcours sont présentées ci-dessous.

• Parcours de pré-commande

Le parcours de pré-commande visite d'abord le nœud racine, puis traverse le sous-arbre de gauche et enfin traverse le sous-arbre de droite. Le code est le suivant :

function preorderTraverse($root) {
    if ($root == null) {
        return;
    }

    echo $root->value . " ";  // 访问根节点
    preorderTraverse($root->left);  // 遍历左子树
    preorderTraverse($root->right);  // 遍历右子树
}

// 示例运行
echo "前序遍历结果：";
preorderTraverse($root);
echo "
";

• Parcours dans l'ordre

Le parcours dans l'ordre traverse d'abord le sous-arbre de gauche, puis visite le nœud racine et enfin traverse le sous-arbre de droite. Le code est le suivant :

function inorderTraverse($root) {
    if ($root == null) {
        return;
    }

    inorderTraverse($root->left);  // 遍历左子树
    echo $root->value . " ";  // 访问根节点
    inorderTraverse($root->right);  // 遍历右子树
}

// 示例运行
echo "中序遍历结果：";
inorderTraverse($root);
echo "
";

• Traversée post-commande

La traversée post-commande traverse d'abord le sous-arbre gauche, puis traverse le sous-arbre droit et enfin visite le nœud racine. Le code est le suivant :

function postorderTraverse($root) {
    if ($root == null) {
        return;
    }

    postorderTraverse($root->left);  // 遍历左子树
    postorderTraverse($root->right);  // 遍历右子树
    echo $root->value . " ";  // 访问根节点
}

// 示例运行
echo "后序遍历结果：";
postorderTraverse($root);
echo "
";

4. Recherche d'arbre binaire

La recherche d'arbre binaire peut être réalisée à l'aide d'un algorithme récursif en comparant les valeurs des nœuds. Voici un exemple de code pour trouver une valeur spécifiée dans un arbre binaire :

function searchValue($root, $value) {
    if ($root == null) {
        return false;
    }

    if ($root->value == $value) {  // 找到目标值
        return true;
    }

    // 在左子树中查找
    if (searchValue($root->left, $value)) {
        return true;
    }

    // 在右子树中查找
    if (searchValue($root->right, $value)) {
        return true;
    }

    return false;  // 未找到目标值
}

// 示例运行
$searchValue = 5;
if (searchValue($root, $searchValue)) {
    echo "二叉树中存在值为 {$searchValue} 的节点
";
} else {
    echo "二叉树中不存在值为 {$searchValue} 的节点
";
}

Grâce à l'exemple de code ci-dessus, nous pouvons utiliser des algorithmes récursifs pour implémenter des opérations de traversée d'arbre binaire et de recherche en PHP. Vous pouvez ajuster la structure de l'arborescence binaire et les valeurs trouvées dans l'exemple pour exécuter et tester le code selon vos besoins.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!