Java mengimplementasikan pohon pencarian biner dan mengimplementasikan operasi pencarian, masukkan, dan hapus pada pohon (gabungkan dan hapus, salin dan hapus)
Pertama -tama, kita perlu memiliki ide pengkodean, secara kasar sebagai berikut:
1. Pencarian: Menurut karakteristik data pohon pencarian biner, kita dapat mewujudkan pencarian berdasarkan perbandingan nilai node. Ketika nilai pencarian lebih besar dari simpul saat ini, pergi ke kanan, dan sebaliknya!
2. Masukkan: Kita harus tahu bahwa semua yang dimasukkan adalah node daun, jadi kita perlu menemukan lokasi simpul daun yang akan dimasukkan, dan ide penyisipan konsisten dengan ide pencarian.
3. Hapus:
1) Gabungkan dan hapus: Secara umum, situasi berikut akan ditemui. Node yang dihapus memiliki subtree kiri tetapi tidak ada subtree kanan. Pada saat ini, simpul induk dari simpul saat ini harus menunjuk ke subtree kiri dari simpul saat ini; Ketika simpul yang dihapus memiliki subtree kanan tetapi tidak ada subtree kiri, simpul induk dari simpul saat ini harus menunjuk ke subtree kanan; Ketika simpul yang dihapus memiliki subtree kiri dan subtree kanan, kita dapat menemukan simpul paling kanan dari subtree kiri dari simpul yang dihapus, dan kemudian membiarkan "pointer" kanan atau kiri dari node ini ke subtree kanan dari simpul yang dihapus
2) Salin dan Penghapusan: Salin dan Penghapusan adalah operasi penghapusan yang relatif sederhana dan juga operasi penghapusan yang paling umum digunakan. Ada sekitar tiga situasi: ketika simpul saat ini tidak memiliki subtree kiri dan memiliki subtree kanan, biarkan simpul root dari subtree kanan saat ini mengganti simpul yang dihapus; Ketika simpul saat ini tidak memiliki subtree kanan dan memiliki subtree kiri, biarkan simpul root dari subtree kiri saat ini dan ganti node yang dihapus; when the currently deleted node has both a left subtree and a right subtree, we need to find the subtree of the deleted node, and find the rightmost node in the left subtree and assign the value of this node to the deleted node, and then don't forget to let the "pointer" of the parent node pointing to the subtree is empty (in fact, it doesn't matter in Java, and there is a garbage disposal mechanism to automatically memprosesnya). Anda juga dapat mengimplementasikan proses ini sebagai simpul yang berdiri sendiri pada simpul paling kiri dari subtree kanan dari simpul yang saat ini dihapus.
Selanjutnya, mari kita tambahkan kode.
Pertama -tama, ## Binary Search Tree Node Class ##
Paket SearchBinaryTree; Public Class SearchBinaryTreeNode <T> {t Data; Pencarian UmumBinaryTreeNode <T> LeftChild; Pencarian UmumBinaryTreeNode <T> RightChild; pencarian publik () {this.data = null; this.leftchild = this.rightchild = null; } public SearchBinaryTeNode (t da) {this.data = da; this.leftchild = this.rightchild = null; } public SearchBinaryTeNode (t da) {this.data = da; this.leftchild = this.rightchild = null; } Public SearchBinaryTreeNode (T DA, SearchBinaryTreeNode <T> Kiri, SearchBinaryTreeNode <T> kanan) {this.data = da; this.leftchild = kiri; this.rightchild = benar; } public t getData () {data pengembalian; } public void setData (data T) {this.data = data; } public SearchBinaryTeNode <T> getLeftChild () {return leftChild; } public void setleftchild (SearchBinaryTreeNode <T> LeftChild) {this.LeftChild = LeftChild; } public SearchBinaryTeNode <T> getRightChild () {return rightChild; } public void setRightChild (SearchBinaryTreeNode <T> RightChild) {this.rightChild = rightChild; } public boolean isleaf () {if (this.leftchild == null && this.rightchild == null) {return true; } return false; }}Menerapkan pohon pencarian biner
Paket SearchBinaryTree; Public Class SearchBinaryTree <T> {SearchBinaryTreeNode <T> root; public boolean isEmpty () {if (root == null) {return true; } return false; } kunjungan public void (SearchBinaryTreeNode <T> root) {if (root == null) {System.out.println ("Pohon ini kosong!"); } System.out.println (root.getData ()); } public SearchBinaryTeNode <T> getRoT () {if (root == null) {root = new SearchBinaryTreeNode <T> (); } return root; } public SearchBinaryTree () {this.root = null; } /** Buat pohon biner* / public void createTree (pencarianBinaryTreeNode <T> node, data t) {if (root == null) {root = new SearchBinaryTreeNode <T> (); } else {if (math.random ()> 0.5) {// Buat pohon biner dengan cara acak if (node.leftchild == null) {node.leftchild = new SearchBinaryTreeNode <T> (data); } else {createTree (node.leftchild, data); }} else {if (node.rightchild == null) {node.rightchild = new SearchBinaryTreeNode <T> (data); } else {createTree (node.rightchild, data); }}}}} /** Cari di pohon pencarian pencarian kedua* / pencarian publik. while ((root! = null) && (current.getData ()! = value)) {// Perlu dicatat bahwa generik di java tidak dapat membandingkan ukuran. Dalam penggunaan aktual, kita dapat menggunakan tipe data umum untuk menggantikan generik ini, sehingga tidak akan ada kesalahan. Current = (value <current.getData ()? Search (current.LeftChild, value): search (current.rightchild, value)); } return arus; } public SearchBinaryTeNode <T> InsertNode (nilai t) {SearchBinaryTeNode <T> p = root, pre = null; while (p! = null) {pre = p; // Perlu dicatat bahwa obat generik di Java tidak dapat membandingkan ukuran. Dalam penggunaan aktual, kita dapat menggunakan tipe data umum untuk menggantikan generik ini, sehingga tidak akan ada kesalahan jika (p.getData () <value) {p = p.rightchild; } else {p = p.leftchild; }} if (root == null) {root = new SearchBinaryTreeNode <T> (value); } else if (pre.getData () <value) {pre.rightchild = new SearchBinaryTreeNode <T> (value); } else {pre.leftchild = new SearchBinaryTreeNode <T> (value); }} /** Gabungkan dan hapus* / public void deleteByMerging (pencarianBinaryTreeNode <T> node) {SearchBinaryTreeNode <T> Temp = node; if (node! = null) {// Jika node yang dihapus tidak memiliki subtree kanan, gunakan node root dari subtree kirinya untuk mengganti node yang dihapus if (node.rightchild! = null) {node = node.LeftChild; } lain jika (node.leftchild == null) {// Jika node yang dihapus tidak memiliki subtree kiri, gunakan simpul paling kiri dengan jumlah kata alih -alih simpul yang dihapus node = node.rightchild; } else {// Jika subtree kiri dan kanan dari node yang dihapus memiliki temp = node.leftchild; while (temp.rightchild! = null) {temp = temp.rightchild; // Mengikuti node kanan subtree kiri} // Tetapkan pointer kanan dari node yang ditemukan ke akar subtree kanan dari simpul yang dihapus temp. Temp = node; node = node.leftchild; } temp = null; }} / * * Salin dan hapus * / public void deleteByCoping (pencarianBinaryTeNode <T> node) {SearchBinaryTreeNode <T> pre = null; SearchBinaryTeenode <T> Temp = node; // Jika node yang dihapus tidak memiliki subtree kanan, gunakan node root dari subtree kiri untuk mengganti node yang dihapus if (node.rightchild == null) {node = node.leftchild; } else if (node.leftchild == null) {node = node.rightchild; } else {// Jika subtree kiri dan kanan dari node yang dihapus memiliki temp = node.leftchild; pre = node; while (temp.rightchild! = null) {pre = temp; temp = temp.rightchild; // bepergian untuk menemukan simpul paling kanan dari subtree kiri} node.data = temp.data; // Lakukan operasi penugasan jika (pre == node) {pre.leftchild = node.leftchild; } else {pre.rightchild = node.rightchild; }} temp = null; }}Kelas tes
Paket SearchBinaryTree; Public Class SearchBinaryTreetest {public static void main (string [] args) {SearchBinaryTree <Integer> Tree = new SearchBinaryTree <Integer> (); untuk (int i = 1; i <10; i ++) {tree.createTree (new SearchBinaryTreeNode <Integer> (), i); } // Cari Tree.search (Tree.root, 7); // gabungkan dan hapus pohon. // salin dan hapus pohon.deletebycoping (new SearchBinaryTreeNode <Integer> (6)); }}Oke, itu saja!
Artikel di atas Java membuat Contoh Pencarian Biner dan mengimplementasikan Contoh Pencarian, Penyisipan, dan Penghapusan adalah semua konten yang saya bagikan dengan Anda. Saya harap Anda dapat memberi Anda referensi dan saya harap Anda dapat mendukung wulin.com lebih lanjut.