Bagaimana untuk melaksanakan traversal pokok binari dan operasi carian dalam PHP menggunakan algoritma rekursif?

Bagaimana untuk menggunakan algoritma rekursif untuk melaksanakan traversal pokok binari dan operasi carian dalam PHP?

Pokok binari ialah struktur data yang biasa digunakan, dan operasinya termasuk traversal dan carian. Dalam PHP, kita boleh menggunakan algoritma rekursif untuk melaksanakan operasi ini Berikut akan memperkenalkan cara menggunakan algoritma rekursif untuk melaksanakan operasi traversal dan carian pokok binari dalam PHP, dan menyediakan contoh kod khusus.

1. Tentukan Kelas Nod Pokok Binari

Pertama, kita perlu mentakrifkan kelas nod pokok binari, yang mengandungi nilai nod dan rujukan kepada nod anak kiri dan kanan. Kod tersebut adalah seperti berikut:

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

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

2. Buat pokok binari

Kita boleh menggunakan kod berikut untuk mencipta pokok binari mudah:

// 创建二叉树
$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. Traversal pokok binari

Traversal dibahagikan kepada pokok binari traversal pra-pesanan, traversal tertib dan traversal pasca pesanan. Pelaksanaan rekursif bagi ketiga-tiga kaedah traversal ini diperkenalkan di bawah. . Kodnya adalah seperti berikut:

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

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

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

• In-order traversal

In-order traversal mula-mula melintasi subpokok kiri, kemudian melawati nod akar, dan akhirnya melintasi subtree kanan. Kodnya adalah seperti berikut:

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

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

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

• Post-order traversal

Post-order traversal mula-mula melintasi subtree kiri, kemudian melintasi subtree kanan, dan akhirnya melawat nod root. Kodnya adalah seperti berikut:

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

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

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

• Carian pokok binari

Carian pokok binari boleh dicapai menggunakan algoritma rekursif dengan membandingkan nilai nod. Berikut ialah contoh kod untuk mencari nilai yang ditentukan dalam pepohon binari:

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} 的节点
";
}

Melalui contoh kod di atas, kita boleh menggunakan algoritma rekursif untuk melaksanakan operasi traversal dan carian pepohon binari dalam PHP. Anda boleh melaraskan struktur pokok binari dan nilai yang terdapat dalam contoh untuk benar-benar menjalankan dan menguji kod seperti yang diperlukan.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan traversal pokok binari dan operasi carian dalam PHP menggunakan algoritma rekursif?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!