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 dipanggilSearchTree
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; }
$tree->delete(12);
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!