Bina struktur data pepohon carian lanjutan dengan PHP

王林
Lepaskan: 2024-05-07 14:45:02
asal
407 orang telah melayarinya

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.

用 PHP 构建先进的搜索树数据结构

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;
    }
}
Salin selepas log masuk

2. 创建搜索树类

接下来,创建一个名为 SearchTree

class SearchTree {
    private $root;

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

    // 其他方法(见下文)
}
Salin selepas log masuk

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);
        }
    }
}
Salin selepas log masuk

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);
        }
    }
}
Salin selepas log masuk

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) {
    // ...
}
Salin selepas log masuk

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);
Salin selepas log masuk

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;
}
Salin selepas log masuk
🎜 Kemudian, kita boleh cari elemen: 🎜
$tree->delete(12);
Salin selepas log masuk
🎜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!

Label berkaitan:
sumber:php.cn
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan