Pokok adalah berbeza daripada senarai terpaut atau jadual cincang Ia adalah struktur data bukan linear yang dibahagikan kepada pokok binari, pokok carian binari, B-pokok, B+ pokok, pokok merah-hitam, dll.
Tree ialah struktur data, iaitu himpunan perhubungan hierarki yang terdiri daripada n nod terhad. Jika anda menggunakan gambar untuk mewakilinya, anda dapat melihat bahawa ia kelihatan seperti pokok terbalik. Oleh itu, kami secara kolektif memanggil jenis struktur data ini sebagai pokok, dengan akar di bahagian atas dan daun di bahagian bawah. Pokok am mempunyai ciri-ciri berikut:
Setiap nod mempunyai 0 atau lebih nod anak
Nod tanpa nod induk dipanggil root Nod
Setiap nod bukan akar mempunyai dan hanya mempunyai satu nod induk
Setiap nod anak boleh dibahagikan kepada berbilang anak bercabang
Takrif pokok binari ialah: setiap nod mempunyai paling banyak dua nod anak. Iaitu, setiap nod hanya boleh mempunyai empat situasi berikut:
Kedua-dua subpokok kiri dan subpokok kanan kosong
Hanya yang kiri subtree exists Tree
Hanya subtree kanan wujud
Kedua-dua subtree kiri dan subtree kanan wujud
Pokok carian binari juga dipanggil pokok pengisihan binari Ia sama ada pokok kosong atau pokok binari dengan sifat berikut:
Jika. subpokok kirinya tidak kosong, maka nilai semua nod pada subpokok kiri adalah kurang daripada nilai nod akar Jika subpokok kanannya tidak kosong, maka nilai semua nod pada subpokok kanan adalah lebih besar daripada nilai nod akar. Python:
Dengan mentakrifkan kelas nod, termasuk nilai nod, subnod kiri dan kanan serta atribut lain, dan kemudian menggunakan fungsi rekursif untuk melaksanakan penyisipan, carian, pemadaman dan operasi lain. Contoh kod adalah seperti berikut:
class Node: def __init__(self, data): self.data = data self.left = None self.right = None class BST: def __init__(self): self.root = None def insert(self, value): if self.root is None: self.root = Node(value) else: self._insert(value, self.root) def _insert(self, value, node): if value < node.data: if node.left is None: node.left = Node(value) else: self._insert(value, node.left) elif value > node.data: if node.right is None: node.right = Node(value) else: self._insert(value, node.right) def search(self, value): if self.root is None: return False else: return self._search(value, self.root) def _search(self, value, node): if node is None: return False elif node.data == value: return True elif value < node.data: return self._search(value, node.left) else: return self._search(value, node.right) def delete(self, value): if self.root is None: return False else: self.root = self._delete(value, self.root) def _delete(self, value, node): if node is None: return node elif value < node.data: node.left = self._delete(value, node.left) elif value > node.data: node.right = self._delete(value, node.right) else: if node.left is None and node.right is None: del node return None elif node.left is None: temp = node.right del node return temp elif node.right is None: temp = node.left del node return temp else: temp = self._find_min(node.right) node.data = temp.data node.right = self._delete(temp.data, node.right) return node def _find_min(self, node): while node.left is not None: node = node.left return node
class BST: def __init__(self): self.values = [] def insert(self, value): if len(self.values) == 0: self.values.append(value) else: self._insert(value, 0) def _insert(self, value, index): if value < self.values[index]: left_child_index = 2 * index + 1 if left_child_index >= len(self.values): self.values.extend([None] * (left_child_index - len(self.values) + 1)) if self.values[left_child_index] is None: self.values[left_child_index] = value else: self._insert(value, left_child_index) else: right_child_index = 2 * index + 2 if right_child_index >= len(self.values): self.values.extend([None] * (right_child_index - len(self.values) + 1)) if self.values[right_child_index] is None: self.values[right_child_index] = value else: self._insert(value, right_child_index) def search(self, value): if value in self.values: return True else: return False def delete(self, value): if value not in self.values: return False else: index = self.values.index(value) self._delete(index) return True def _delete(self, index): left_child_index = 2 * index + 1 right_child_index = 2 * index + 2 if left_child_index < len(self.values) and self.values[left_child_index] is not None: self._delete(left_child_index) if right_child_index < len(self.values) and self.values[right_child_index] is not None: self
di mana kunci kamus mewakili nilai nod, dan nilai kamus ialah kamus yang mengandungi sebelah kiri. dan nod anak kanan. Contoh kod adalah seperti berikut:
def insert(tree, value): if not tree: return {value: {}} elif value < list(tree.keys())[0]: tree[list(tree.keys())[0]] = insert(tree[list(tree.keys())[0]], value) else: tree[list(tree.keys())[0]][value] = {} return tree def search(tree, value): if not tree: return False elif list(tree.keys())[0] == value: return True elif value < list(tree.keys())[0]: return search(tree[list(tree.keys())[0]], value) else: return search(tree[list(tree.keys())[0]].get(value), value) def delete(tree, value): if not search(tree, value): return False else: if list(tree.keys())[0] == value: if not tree[list(tree.keys())[0]]: del tree[list(tree.keys())[0]] elif len(tree[list(tree.keys())[0]]) == 1: tree[list(tree.keys())[0]] = list(tree[list(tree.keys())[0]].values())[0] else: min_key = min(list(tree[list(tree.keys())[0]+1].keys())) tree[min_key] = tree[list(tree.keys())[0]+1][min_key] tree[min_key][list(tree.keys())[0]] = tree[list(tree.keys())[0]] del tree[list(tree.keys())[0]] elif value < list(tree.keys())[0]: tree[list(tree.keys())[0]] = delete(tree[list(tree.keys())[0]], value) else: tree[list(tree.keys())[0]][value] = delete(tree[list(tree.keys())[0]].get(value), value) return tree
4. Gunakan tindanan untuk melaksanakan
Tentukan kelas nod, termasuk nilai nod, subnod kiri dan kanan serta atribut lain.
Tentukan tindanan dan mula-mula tolak nod akar pada tindanan.
Apabila tindanan tidak kosong, keluarkan elemen atas tindanan dan kendalikan padanya: jika nilai yang hendak dimasukkan kurang daripada nilai nod semasa, masukkan nilai ke disisipkan sebagai nod anak kiri, dan tolak nod anak kiri ke tindanan jika nilai yang akan dimasukkan lebih besar daripada nilai nod semasa, masukkan nilai yang akan dimasukkan sebagai nod anak kanan, dan tolak nod anak kanan; ke dalam timbunan; jika nilai yang akan ditemui atau dipadam adalah sama dengan nilai nod semasa, Kemudian kembalikan atau padamkan nod.
Selepas operasi selesai, teruskan ambil nod seterusnya daripada tindanan dan kendalikan sehingga tindanan kosong.
Perlu diingatkan bahawa dalam pelaksanaan ini, disebabkan penggunaan tindanan untuk menyimpan proses melintasi pokok, ia mungkin mengakibatkan penggunaan memori yang tinggi. Di samping itu, disebabkan oleh ciri-ciri tindanan, pelaksanaan ini hanya boleh menyokong traversal pertama mendalam (Depth-First Search, DFS) dan tidak boleh menyokong carian breadth-first (BFS).
class Node: def __init__(self, data): self.data = data self.left = None self.right = None def insert(root, value): if not root: return Node(value) stack = [root] while stack: node = stack.pop() if value < node.data: if node.left is None: node.left = Node(value) break else: stack.append(node.left) elif value > node.data: if node.right is None: node.right = Node(value) break else: stack.append(node.right) def search(root, value): stack = [root] while stack: node = stack.pop() if node.data == value: return True elif value < node.data and node.left: stack.append(node.left) elif value > node.data and node.right: stack.append(node.right) return False def delete(root, value): if root is None: return None if value < root.data: root.left = delete(root.left, value) elif value > root.data: root.right = delete(root.right, value) else: if root.left is None: temp = root.right del root return temp elif root.right is None: temp = root.left del root return temp else: temp = root.right while temp.left is not None: temp = temp.left root.data = temp.data root.right = delete(root.right, temp.data) return root
Atas ialah kandungan terperinci Apakah kaedah untuk melaksanakan pepohon carian binari dalam python. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!