1. Konsep
Pohon pencarian biner juga menjadi pohon penyortiran biner. Ini memiliki karakteristik bahwa jika sebuah node memiliki dua node anak, itu harus dipenuhi. Nilai simpul anak kiri harus lebih kecil dari nilai simpul, dan nilai simpul anak yang tepat harus lebih besar dari nilai node. Untuk perbandingan tipe non-basic, antarmuka pembanding dapat diimplementasikan. Dalam artikel ini, data tipe int digunakan untuk operasi.
Untuk mengimplementasikan pohon biner, Anda harus mulai dengan peningkatannya. Hanya dengan membangun pohon Anda dapat menggunakan operasi lain.
2. Konstruksi pohon pencarian biner
Saat berbicara tentang peningkatan pohon biner, pertama -tama kita harus membangun kelas yang mewakili sebuah node. Kelas node memiliki beberapa atribut, nilai node, simpul induk, simpul kiri, dan simpul kanan node. Kodenya adalah sebagai berikut
node kelas statis {node induk; Node Leftchild; Node RightChild; int val; node publik (node induk, node kiri, simpul kanan, int val) {super (); this.parent = Parent; this.leftchild = LeftChild; this.rightchild = rightChild; this.val = val; } node publik (int val) {this (null, null, null, val); } node publik (simpul simpul, int val) {this (node, null, null, val); }}Di sini kami menggunakan metode penulisan kelas internal. Setelah membangun nilai simpul, kami akan membangun seluruh pohon. Sebuah pohon pertama -tama harus memiliki simpul root, dan kemudian memperpanjang ke node anak yang tersisa. Di pohon ini, ada juga beberapa atribut, seperti akar simpul akar dasar, dan ukuran elemen di pohon. Jika kedua atribut ini digunakan, atribut pembanding dapat ditambahkan, atau implementasi default dapat disediakan. Kode spesifiknya adalah sebagai berikut
Public Class SearchBinaryTree {private node root; ukuran int pribadi; pencarian publik () {super (); }}3. Tambahkan
Saat menambahkan elemen, Anda harus mempertimbangkan inisialisasi simpul root. Secara umum, ada dua jenis: Ketika konstruktor kelas ini diinisialisasi, akar simpul akar akan diinisialisasi. Yang kedua adalah menambahkan simpul root saat elemen pertama ditambahkan. Keduanya bekerja secara teori, tetapi biasanya menggunakan bentuk pemuatan malas kedua.
Saat menambahkan elemen, ada beberapa situasi yang perlu dipertimbangkan
1. Saat menambahkan, tentukan apakah root diinisialisasi. Jika tidak diinisialisasi, itu akan diinisialisasi. Tetapkan nilai ke simpul root dan tambahkan satu ukuran.
2. Karena pohon pencarian pohon biner memenuhi bahwa nilai simpul akar lebih besar dari simpul kiri dan lebih kecil dari simpul kanan, nilai yang dimasukkan perlu dibandingkan dengan node akar terlebih dahulu. Jika besar, cari di subtree kanan. Jika kecil, cari di subtree kiri. Sampai simpul anak.
Implementasi penyisipan di sini dapat mengadopsi dua jenis: satu, rekursi, dua, iteratif (mis. Melalui mode loop).
3.1. Penyisipan Versi Rekursif
public boolean add (int val) {if (root == null) {root = new node (val); ukuran ++; Kembali Benar; } Node node = getAdapternode (root, val); Node newNode = node baru (val); if (node.val> val) {node.leftchild = newNode; newnode.parent = node; } else if (node.val <val) {node.rightchild = newNode; newnode.parent = node; } else {// tidak ada pemrosesan untuk saat ini} ukuran ++; 19 return true; } /*** Dapatkan simpul induk dari node untuk dimasukkan. Node induk memenuhi salah satu dari keadaan berikut* 1. Node induk adalah simpul anak* 2. Nilai simpul penyisipan lebih kecil dari simpul induk, tetapi simpul induk tidak memiliki simpul anak kiri* 3. Nilai simpul penyisipan lebih besar dari simpul induk, tetapi simpul induk tidak memiliki node anak kanan* 4. Nilai nilai sisipan tersebut, tetapi node induk tidak memiliki node anak kanan* 4. Nilai nilai sisipan dari sarang induk, tetapi node induk tidak memiliki node anak kanan* 4. Nilai nilai sisipan sisipan tersebut, tetapi node induk tidak memiliki node anak kanan* 4. Nilai nilai sisipan The Node The Node. * 5. Node induk kosong* Jika salah satu dari 5 kasus di atas terpenuhi, itu akan berhenti secara rekursif. * @param node * @param val * @return */ node private getAdapternode (simpul node, int val) {if (node == null) {return node; } // Masukkan ke dalam subtree kiri tetapi tidak ada subtree kiri, if (node.val> val && node.LeftChild == null) {return node; } // Masukkan ke dalam subtree kanan tetapi tidak ada subtree kanan, juga kembalikan if (node.val <val && node.rightchild == null) {return node; } // Masukkan ke dalam subtree kanan tetapi tidak ada subtree kanan, juga kembalikan if (node.val <val && node.rightchild == null) {return node; } // Masukkan ke dalam subtree kanan tetapi tidak ada subtree kanan, juga kembalikan if (node.val <val && node.rightchild == null) {return node; } // Masukkan ke dalam subtree kanan tetapi tidak ada subtree kanan, juga kembalikan if (node.LeftChild == null && node.rightchild == null) {return node; } if (node.val> val && node.leftchild! = null) {return getAdapTarnode (node.leftchild, val); } else if (node.val <val && node.rightchild! = null) {return getAdapTarnode (node.rightchild, val); } else {return node; }}Gunakan rekursi, pertama temukan titik akhir rekursi, dan kemudian ubah seluruh masalah menjadi sub-masalah. Dalam kode di atas, logikanya kira -kira seperti ini: pertama -tama tentukan apakah simpul root diinisialisasi, dan jika tidak diinisialisasi, ia diinisialisasi, dan setelah selesai, ia kembali, dan kemudian menggunakan fungsi untuk mendapatkan simpul yang diadaptasi. Lalu masukkan nilainya.
3.2. Versi berulang
public boolean put (int val) {return putval (root, val); } private boolean putval (simpul simpul, int val) {if (node == null) {// menginisialisasi simpul root node = node baru (val); root = node; ukuran ++; Kembali Benar; } Node temp = node; Simpul p; int t; / ** * Dapatkan simpul terbaik melalui do wily loop iteration, */ do {p = temp; t = temp.val-val; if (t> 0) {temp = temp.leftchild; } else if (t <0) {temp = temp.rightchild; } else {temp.val = val; mengembalikan false; }} while (temp! = null); Node newnode = node baru (p, val); if (t> 0) {p.leftchild = newNode; } else if (t <0) {p.rightchild = newNode; } ukuran ++; Kembali Benar; }Prinsipnya sebenarnya sama dengan rekursi, yaitu untuk mendapatkan simpul terbaik dan beroperasi pada simpul itu.
Dalam hal kinerja, ini jelas merupakan versi iteratif terbaik, jadi secara umum, ini adalah versi iteratif untuk beroperasi pada data.
4. Hapus
Dapat dikatakan bahwa dalam pengoperasian pohon pencarian biner, penghapusan adalah yang paling rumit, dan ada banyak situasi yang perlu dipertimbangkan. Dengan cara konvensional, jika Anda menghapus simpul di pohon pencarian biner, Anda pasti akan memikirkan empat situasi berikut.
1. Node yang akan dihapus tidak memiliki node anak kiri dan kanan, seperti yang ditunjukkan pada node D, E, dan G pada gambar di atas
2. Node yang akan dihapus hanyalah simpul anak kiri, seperti simpul B
3. Node yang akan dihapus hanyalah simpul anak yang tepat, seperti node f
4. Node yang akan dihapus memiliki node anak kiri dan node anak kanan, seperti node A dan C
Untuk tiga situasi pertama, dapat dikatakan bahwa itu relatif sederhana, sedangkan yang keempat rumit. Mari kita analisis yang pertama
Jika ini masalahnya, misalnya, jika simpul D dihapus, simpul anak kiri simpul B dapat diatur ke nol, dan jika simpul G dihapus, simpul anak yang tepat dari simpul F dapat diatur ke nol. Sisi mana yang harus diatur, dan melihat sisi mana node yang dihapus berada.
Cara kedua untuk menghapus simpul B, Anda hanya perlu mengatur simpul kiri simpul A ke simpul D dan simpul induk dari simpul D ke A. Sisi mana yang diatur tergantung pada sisi mana dari simpul yang dihapus terletak di node induk.
Tipe ketiga sama dengan tipe kedua.
Tipe keempat, yang sedikit rumit seperti yang disebutkan sebelumnya, misalnya, untuk menghapus simpul C, atur simpul induk dari simpul F ke simpul A, atur simpul kiri simpul ke simpul E, atur simpul kanan A ke simpul F, node E TO NODE E TO NODE F (yaitu, ganti node f node f) node yang lain adalah node yang lain adalah node lain. Jadi mana yang harus digunakan? Jika simpul hapus adalah simpul root, bagaimana saya harus menghapusnya?
Untuk kasing keempat, Anda dapat memikirkannya seperti ini: temukan simpul penerus C atau node, hapus simpul penerus, dan atur nilai simpul penerus ke nilai C atau sebuah simpul. Mari kita suplemen pertama konsep node penerus.
Simpul penerus sebuah simpul di seluruh pohon harus dipenuhi. Node dengan nilai terkecil dalam set node yang sepadan dengan node adalah simpul penerus. Tentu saja, mungkin tidak ada node penerus.
Namun, untuk kasus keempat, simpul penerus harus ada dan harus berada di subtree kanannya, dan juga memenuhi salah satu kasus di mana hanya ada satu simpul anak atau tidak ada node anak. Alasan spesifik dapat dipikirkan ini, karena simpul penerus lebih besar dari simpul C, dan karena sub-bagian kiri dan kanan dari simpul C harus ada, itu harus ada di sub-bagian kiri di sub-pohon kanan. Misalnya, simpul penerus C adalah F, dan simpul penerus A adalah E.
Dengan analisis di atas, implementasinya relatif sederhana, kodenya adalah sebagai berikut
public boolean delete (int val) {node node = getNode (val); if (node == null) {return false; } Node induk = node.parent; Node leftchild = node.leftchild; Node rightChild = node.rightchild; // Semua node induk berikut kosong, itu berarti bahwa node yang dihapus adalah node root if (leftChild == null && rightChild == null) {// tidak ada node anak if (parent! = Null) {if (parent.leftchild == node) {parent.leftchild = null; } else if (parent.rightchild == node) {parent.RightChild = null; }} else {// node induk tidak ada, yang berarti bahwa simpul yang dihapus adalah node root root = null; } node = null; Kembali Benar; } lain if (leftchild == null && rightChild! = null) {// Hanya simpul kanan if (induk! = null && parent.val> val) {// Ada simpul induk, dan posisi simpul adalah sisi kiri dari node induk induk.leftchild = rightChild; } lain jika (induk! = null && parent.val <val) {// Ada node induk, dan posisi simpul adalah sisi kanan node induk induk.rightchild = rightChild; } else {root = rightChild; } node = null; Kembali Benar; } lain if (leftchild! = null && rightChild == null) {// Hanya simpul kiri if (induk! = null && parent.val> val) {// Ada node induk, dan posisi simpul adalah sisi kiri dari node induk induk.leftchild = kiri; } lain jika (induk! = null && parent.val <val) {// Ada node induk, dan posisi simpul adalah sisi kanan node induk induk.rightchild = leftchild; } else {root = LeftChild; } return true; } lain if (leftchild! = null && rightChild! = null) {// Kedua node anak memiliki simpul penerus node = getsuccessor (node); // Dalam hal ini, harus ada simpul node int int temp = penerus.val; boolean delete = delete (temp); if (hapus) {node.val = temp; } penerus = null; Kembali Benar; } return false; } /*** Temukan simpul penerus simpul node* 1. Pertama tentukan apakah simpul memiliki subtree yang tepat. Jika demikian, cari simpul penerus dari subtree kiri simpul kanan. Jika tidak, lanjutkan ke langkah berikutnya* 2. Temukan simpul induk dari node. Jika simpul yang tepat dari simpul induk sama dengan simpul, terus cari node induk * sampai simpul induk nol atau temukan simpul yang tepat yang tidak sama dengan node. * Alasan, simpul penerus harus lebih besar dari simpul. Jika ada subtree yang tepat, simpul penerus harus ada di subtree kanan. Ini adalah alasan untuk langkah pertama* jika tidak ada subtree yang benar, mungkin juga ada node kakek dari node (mis. Node induk dari simpul, atau simpul induk di atas simpul induk). * Secara iteratif cari, jika ada, ia mengembalikan node, dan jika tidak ada, ia mengembalikan null * @param node * @return */ node private getsuccessor (node node) {if (node.rightchild! = Null) {node rightchild = node.rightchild; while (rightchild.leftchild! = null) {rightChild = rightchild.LeftChild; } return rightChild; } Node induk = node.parent; while (Parent! = null && (node == Parent.RightChild)) {node = Parent; Parent = Parent.parent; } mengembalikan induk; }Untuk logika spesifik, silakan merujuk ke analisis di atas. Saya tidak akan menjelaskan teks di sini.
Selain implementasi ini, implementasi lain disediakan dalam pengantar algoritma.
hapus boolean publik (int val) {node node = getNode (val); if (node == null) {return false; } if (node.leftchild == null) {// 1. Node kiri tidak ada, simpul kanan mungkin ada, termasuk dua situasi. Kedua node tidak ada dan hanya node kanan yang ada transplantasi (node, node.rightchild); } else if (node.rightchild == null) {// 2. Anak kiri ada, dan simpul kanan tidak ada transplantasi (node, node.leftchild); } else {// 3. Kedua node memiliki node penerus = getsuccessor (node); // Dapatkan simpul simpul simpul if (sucker.parent! = node) {// simpul penerus ada di subtree kanan simpul. transplantasi (penerus, penerus.rightchild); // ganti penerus dengan simpul anak yang tepat dari penerus. langkah sebelumnya} transplantasi (node, penerus); penerus.leftchild = node.LeftChild; penerus.leftchild.parent = penerus; } return true; } /*** Ganti simpul anak dengan simpul simpul* @param root root node* @param simpul simpul node untuk menghapus* @param node node node anak node anak node anak node anak anak node anak void transplantasi (node node, node node. Langkah* 2. Tentukan bahwa simpul node adalah anak dari simpul induk (yaitu, tentukan apakah simpul adalah simpul kanan atau simpul kiri),* Setelah mendapatkan hasilnya, ganti simpul anak dengan simpul simpul, yaitu, jika simpul node kiri 3 node node juga node node kiri node kiri setelah diganti, node node kanan* node node 3 node node 3 node node node kiri node kiri node kiri setelah diganti, jika tidak, node kanan node* node node 3 node node node Parte juga akan node node kiri diganti, jika tidak ada node node* node node. node*/ if (node.parent == null) {this.root = anak; } else if (node.parent.leftchild == node) {node.parent.leftchild = anak; } else if (node.parent.rightchild == node) {node.parent.rightchild = anak; } if (child! = null) {child.parent = node.parent; }}5. Cari
Pencarian juga relatif sederhana, tetapi pada kenyataannya, telah diimplementasikan ketika ditambahkan. Dalam situasi yang sebenarnya, bagian ini dapat diekstraksi dari metode terpisah. Kodenya adalah sebagai berikut
node publik getNode (int val) {node temp = root; int t; do {t = temp.val-val; if (t> 0) {temp = temp.leftchild; } else if (t <0) {temp = temp.rightchild; } else {return temp; }} while (temp! = null); kembali nol; }6. Traversal Pohon Pencarian Biner
Setelah memahami sifat -sifat pohon pencarian biner, jelas bahwa traversal urutan menengah diatur secara berurutan dari kecil ke besar. Berikut adalah kode traversal pesanan menengah yang disediakan di sini
public void print () {print (root); } private void print (node root) {if (root! = null) {print (root.leftchild); System.out.println (root.val); // Jika posisinya di tengah, maka urutannya berada di tengah. Jika ada di depan, itu ada di preseden, jika tidak itu adalah cetakan berikutnya (root.rightchild); }} Meringkaskan
Di atas adalah implementasi Java dari fungsi pohon pencarian biner yang diperkenalkan oleh editor. Saya harap ini akan membantu semua orang. Jika Anda memiliki pertanyaan, silakan tinggalkan saya pesan. Editor akan membalas semua orang tepat waktu!