Bina struktur data pepohon carian lanjutan dengan PHP

Membina pepohon carian lanjutan menggunakan PHP melibatkan mencipta kelas nod (Nod) dan kelas pepohon carian (SearchTree), serta melaksanakan kaedah untuk memasukkan, mencari dan memadamkan elemen. Unsur-unsur disimpan dalam pokok binari dalam kerumitan masa logaritma, dengan setiap nod mengandungi nilai dan pautan ke subpokok kiri dan kanannya. Dalam amalan, anda boleh mencipta pepohon carian dan memasukkan elemen, mencari nilai tertentu, atau memadamkan elemen daripada pepohon itu.

Bina struktur data pepohon carian lanjutan menggunakan PHP

Pepohon carian ialah struktur data yang cekap yang membolehkan mencari, memasukkan dan memadam elemen dalam kerumitan masa logaritma. Artikel ini akan membimbing anda membina pepohon carian lanjutan menggunakan PHP.

1 Buat kelas nod

Pertama, buat kelas bernama Node untuk mewakili nod dalam pepohon: Node 的类来表示树中的节点：

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

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

2. 创建搜索树类

接下来，创建一个名为 SearchTree

class SearchTree {
    private $root;

    public function __construct() {
        $this->root = null;
    }

    // 其他方法（见下文）
}

2 Buat kelas pepohon carian

Seterusnya. Buat kelas yang dipanggil SearchTree untuk mewakili pepohon carian itu sendiri:

public function insert($value) {
    if ($this->root === null) {
        $this->root = new Node($value);
    } else {
        $this->_insert($value, $this->root);
    }
}

private function _insert($value, $node) {
    if ($value < $node->value) {
        if ($node->left === null) {
            $node->left = new Node($value);
        } else {
            $this->_insert($value, $node->left);
        }
    } else {
        if ($node->right === null) {
            $node->right = new Node($value);
        } else {
            $this->_insert($value, $node->right);
        }
    }
}

3 Memasukkan elemen

Untuk memasukkan elemen baharu, gunakan kaedah berikut:

public function find($value) {
    if ($this->root === null) {
        return null;
    } else {
        return $this->_find($value, $this->root);
    }
}

private function _find($value, $node) {
    if ($value === $node->value) {
        return $node;
    } elseif ($value < $node->value) {
        if ($node->left === null) {
            return null;
        } else {
            return $this->_find($value, $node->left);
        }
    } else {
        if ($node->right === null) {
            return null;
        } else {
            return $this->_find($value, $node->right);
        }
    }
}

4 elemen

Untuk mencari elemen, anda boleh menggunakan kaedah berikut:

public function delete($value) {
    if ($this->root === null) {
        return;
    } else {
        $this->root = $this->_delete($value, $this->root);
    }
}

private function _delete($value, $node) {
    // ...
}

5 Padam elemen

Untuk memadam elemen, anda boleh menggunakan kaedah berikut (ini adalah proses rekursif, pelaksanaan khusus ialah. ditinggalkan):

$tree = new SearchTree();
$tree->insert(10);
$tree->insert(5);
$tree->insert(15);
$tree->insert(7);
$tree->insert(12);
$tree->insert(20);

Kes praktikal

Mari buat pepohon carian dan masukkan beberapa elemen: 🎜

$foundNode = $tree->find(12);
if ($foundNode !== null) {
    echo "Found the node with value 12." . PHP_EOL;
}

🎜 Kemudian, kita boleh cari elemen: 🎜

$tree->delete(12);

🎜Akhir sekali, kita boleh memadamkan elemen: 🎜

Atas ialah kandungan terperinci Bina struktur data pepohon carian lanjutan dengan PHP. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!