Satu, definisi pohon penyortiran biner
1. Definisi pohon penyortiran biner <br /> pohon sortir biner (pohon sortir biner), juga dikenal sebagai pohon pencarian biner. Ini didefinisikan sebagai: pohon penyortiran biner atau pohon kosong, atau pohon biner yang memenuhi sifat -sifat berikut:
① Jika subtree kirinya tidak kosong, nilai semua node pada subtree kiri lebih kecil dari nilai node root;
② Jika subtree kanannya tidak kosong, nilai semua node pada subtree kanan lebih besar dari nilai node root;
Subtree Kidal dan kanan sendiri masing -masing adalah pohon penyortiran biner.
Properti di atas disebut sebagai properti pohon penyortiran biner (properti BST), sehingga pohon penyortiran biner sebenarnya adalah pohon biner yang memenuhi properti BST.
2. Properti Pohon Penyortiran Biner <BR /> Transfer pohon penyortiran biner di orde menengah, dan urutan traversal orde menengah yang dihasilkan adalah urutan yang dipesan secara tambahan.
3. Masukkan pohon penyortiran biner <BR /> Masukkan simpul baru ke dalam pohon penyortiran biner, untuk memastikan bahwa pohon biner yang dimasukkan masih memenuhi definisi pohon penyortiran biner.
Sisipkan proses:
Jika pohon penyortiran biner kosong, node *akan dimasukkan ke dalam pohon kosong sebagai simpul akar;
Ketika tidak kosong, bandingkan kata kunci s-> tombol untuk dimasukkan dengan kata kunci root pohon t-> tombol. Jika s-> key = t-> key, tidak perlu memasukkannya. Jika tombol S-> <t->, itu dimasukkan ke dalam subtree kiri root. Jika S-> Key> T-> Key, itu dimasukkan ke dalam subtree kanan root. Proses penyisipan dalam subtree sama dengan proses penyisipan di pohon. Ini berlanjut sampai simpul *dimasukkan ke dalam pohon penyortiran biner sebagai daun baru, atau sampai pohon ditemukan memiliki node dengan kata kunci yang sama.
4. Cari pohon penyortiran biner <BR /> dengan asumsi bahwa penunjuk akar pohon penyortiran biner adalah akar dan nilai kata kunci yang diberikan adalah k, algoritma pencarian dapat digambarkan sebagai:
① Tetapkan nilai awal: q = root;
② Jika k = q -> key, pencarian berhasil dan algoritma berakhir;
③ Jika tidak, jika K <Q －＞ kunci dan subtree kiri Q tidak kosong, subtree kiri Q dikirim ke Q dan kemudian langkah ②; Kalau tidak, pencarian gagal dan algoritma berakhir;
④ Jika tidak, jika K ＞ Q －＞ kunci, dan subtree yang tepat dari Q tidak kosong, subtree yang tepat dari Q dikirim ke Q dan kemudian langkah ②; Kalau tidak, pencarian gagal dan algoritma berakhir.
5. Penghapusan pohon penyortiran biner <BR /> Misalkan simpul yang dihapus adalah *P dan orang tua adalah *F, yang tidak hilang secara umum. Asumsikan bahwa *P adalah anak kiri *F, berikut ini dibagi menjadi tiga situasi:
⑴ Jika simpul *P adalah simpul daun, Anda hanya perlu memodifikasi pointer dari simpul induknya *f.
⑵ Jika simpul *P hanya memiliki subtree PL kiri atau hanya sub Subtree Kanan, maka cukup buat PL atau PR subtree kiri dari simpul induknya.
⑶ Jika subtree node kiri dan kanan *P tidak kosong, pertama -tama temukan node pendahulunya yang lebih rendah (atau penerus) *S dari *p (perhatikan bahwa *s adalah simpul paling kanan bawah di subtree kiri *P, dan domain rantai kanannya adalah rantai kiri), dan kemudian ada dua cara: ① Biarkan subtree kiri *P. ke rantai kanan node pendahuluan urutan tengah *P. ② Ganti *P dengan node pendahulu urutan tengah *s dari *p (yaitu, salin data *s ke *p), dan rantai subtree kiri *s ke rantai kiri (atau kanan) dari node induk *q dari *s.
6. Traversal dari pohon biner <br /> Ada tiga cara untuk melintasi pohon biner, sebagai berikut:
(1) Pre-order Traversal (DLR), pertama mengakses node root, kemudian melintasi subtree kiri, dan akhirnya melintasi subtree kanan. Root Singkat - Kiri - Kanan.
(2) In-order Traversal (LDR), Traversal Pertama Subtree kiri, kemudian mengakses node root, dan akhirnya melintasi subtree kanan. Catatan Singkat: Right-Right Kiri.
(3) Pasca-orde Traversal (LRD), pertama-tama melintasi subtree kiri, kemudian melintasi subtree kanan, dan akhirnya mengakses node root. Root-right-root-root yang disingkat.
2. Menulis kode
1. Definisi Kelas Node Pohon 0
paket com.lin; / ** * Ringkasan fungsi: */ kelas publik TreeNode {data integer publik; /* Simpul induk dari simpul ini*/ Public Treeenode Parent; /*Node anak kiri dari simpul ini*/ Treeenode publik kiri; /*Simpul anak yang tepat dari simpul ini*/ Treeenode publik kanan; public treenode (data integer) {this.data = data; } @Override Public String ToString () {return "TreeNode [data =" + data + "]"; }} 2. Definisi pohon penyortiran biner
paket com.lin; /*** Ringkasan Fungsi: Pohon Biner Sortir/Balanced*/Public Class SearchTree {public treenode root; Ukuran Panjang Publik; / ** * Tambahkan node ke pohon * @param data * @return Boolean Insertion Mengembalikan true */ public boolean addtreenode (data integer) {if (null == root) {root = new treenode (data); System.out.println ("Data berhasil dimasukkan ke dalam pohon biner seimbang"); Kembali Benar; } Treenode treenode = new treenode (data); // data yang akan dimasukkan treenode currentNode = root; Treeenode ParentNode; while (true) {parentNode = currentNode; // simpan node induk // data yang dimasukkan lebih kecil dari node induk if (currentNode.data> data) {currentNode = currentNode.left; // simpul anak kiri dari simpul induk saat ini kosong jika (null == currentNode) {parentNode.left = treenode; treenode.parent = parentNode; System.out.println ("Data berhasil dimasukkan ke dalam pohon pencarian biner"); ukuran ++; Kembali Benar; } // Data yang dimasukkan lebih besar dari node induk} lain jika (currentNode.data <data) {currentNode = currentNode.Right; // simpul anak yang tepat dari simpul induk saat ini kosong jika (null == currentNode) {parentNode.right = treenode; treenode.parent = parentNode; System.out.println ("Data berhasil dimasukkan ke dalam pohon pencarian biner"); ukuran ++; Kembali Benar; }} else {System.out.println ("Data input sama dengan data node"); mengembalikan false; }}} / ** * @param data * @return treenode * / public treenode findtreenode (data integer) {if (null == root) {return null; } Treenode arus = root; while (current! = null) {if (current.data> data) {current = current.left; } else if (current.data <data) {current = current.right; } else {return arus; }} return null; }} Berikut adalah metode penambahan dan pencarian
3. Traversal depan, tengah dan belakang
paket com.lin; impor java.util.stack; / *** Ringkasan Fungsi:*/ TreeOrder kelas publik {/ *** Implementasi rekursif traversal preorder* @author linbingwen* @since 29 Agustus 2015* @param treenode*/ public static void preorderMethodone (treenode treenode) {if (null! = Treenode) {treeNode. if (null! = treenode.left) {preorderMethodone (treenode.left); } if (null! = treenode.right) {preorderMethodone (treenode.right); }}} / *** Looping untuk mengimplementasikan preorder traversal* @param treenode* / public static void preorderMethodTwo (treenode treenode) {if (null! = Treenode) {stack <tack <tack> stack = stack baru <treeenode> (); stack.push (treenode); while (! stack.isempty ()) {treenode tempnode = stack.pop (); System.out.print (tempnode.data + ""); // simpul anak yang tepat bukan nol, masukkan simpul anak yang tepat di if (null! = Tempnode.right) {stack.push (tempnode.right); } // Setelah meletakkan simpul anak yang tepat, letakkan simpul anak kiri, dan ambil if (null! = Tempnode.left) {stack.push (tempnode.left); }}}} / *** Secara rekursif mengimplementasikan traversal in-order* @param treenode* / public static void MedorderMethodone (treenode treenode) {if (null! = Treenode) {if (null! = Treenode.left) {MedorderMethodone (treenode.left); } System.out.print (treenode.data + ""); if (null! = treenode.right) {MedorderMethodone (treenode.right); }}} / *** Implementasi loop In-order Traversal* @param treenode* / public static void MedorderMethodtwo (treenode treenode) {stack <treenode> stack = stack baru <treeNode> (); Treenode arus = treenode; while (saat ini! = null ||! stack.isempty ()) {while (saat ini! = null) {stack.push (saat ini); arus = arus.Left; } if (! stack.isempty ()) {current = stack.pop (); System.out.print (current.data+""); Current = Current.Right; }}} / *** secara rekursif mengimplementasikan traversal pasca-order* @param treenode* / public static void postorderMethodone (treenode treenode) {if (null! = Treenode) {if (null! = Treenode.left) {postorderMethodone (treenode.left); } if (null! = TreeNode.Right) {PostorderMethodone (TreeNode.Right); } System.out.print (treenode.data + ""); }} / *** Looping untuk mengimplementasikan traversal pasca-order* @param treenode* / public static void postorderMethodtwo (treenode treenode) {if (null! = Treenode) {stack <tack <tack> stack = stack baru <treeenode> (); Treenode arus = treenode; Treenode rightNode = null; while (saat ini! = null ||! stack.isempty ()) {while (saat ini! = null) {stack.push (saat ini); arus = arus.Left; } current = stack.pop (); while (current! = null && (current.right == null || current.right == rightNode)) {System.out.print (current.data + ""); rightNode = arus; if (stack.isempty ()) {System.out.println (); kembali; } current = stack.pop (); } stack.push (saat ini); Current = Current.Right; }}}} 4. Cara menggunakan
paket com.lin; / ** * Ringkasan Fungsi: */ kelas publik Searchtreetest {/ ** * @param args */ public static void main (string [] args) {searchtree tree = new Searchtree (); Tree.addtreenode (50); Tree.addtreenode (80); Tree.addtreenode (20); Tree.addtreenode (60); Tree.addtreenode (10); Tree.addtreenode (30); Tree.addtreenode (70); Tree.addtreenode (90); Tree.addtreenode (100); Tree.addtreenode (40); System.out.println ("============================================================================================================================================= ================================================================ ================================================================ ================================================================ ================================================================ ================================================================ ================================================================ System.out.println ("=============================================== ==================================================================== ==================================================================== ==================================================================== ==================================================================== ==================================================================== ==================================================================== ==================================================================== Treeorder.PostorderMethodone (Tree.root); System.out.println ("============================================================================================================================================= ================================================================ ================================================================= ================================================================ ================================================================= ================================================================ ================================================================= System.out.println ("=============================================== ==================================================================== ==================================================================== ==================================================================== ==================================================================== ==================================================================== ==================================================================== ==================================================================== Treeorder.MedorderMethodtwo (Tree.root);Hasil output:
Demikian pula, proses pencarian adalah sebagai berikut:
Node treenode = tree.findtreenode (100); System.out.println (node);
Hasilnya benar
Di atas adalah pengantar terperinci untuk pohon penyortiran biner Java. Saya harap ini akan membantu semua orang belajar pemrograman Java.