Pohon penyortiran biner juga disebut pohon pencarian biner. Ini adalah pohon kosong atau pohon biner dengan sifat -sifat berikut:
① Jika subtree kiri tidak kosong, maka nilai semua node pada subtree kiri lebih kecil dari nilai node akarnya;
②Jika Subtree kanan tidak kosong, maka nilai semua node pada subtree kanan lebih besar dari nilai node rootnya;
Subtree Subtree Kiri dan Kanan juga masing -masing adalah Binary Sorting Trees.
Kode berikut mengimplementasikan:
impor java.util.linkedlist; import java.util.queue; node kelas {data int publik; simpul publik kiri; Hak simpul publik; Public int leftmaxdistance; Publik int rightmaxdistance; node publik (data int) {this.data = data; this.left = null; this.right = null; }}/*** @Author ty* Menerapkan pohon penyortiran biner, termasuk penyisipan, traversal dalam urutan, traversal preorder, traversal pasca-order, dan menghitung jarak maksimum semua node*/BinerTree kelas publik {private node root; BinaryTree publik () {root = null; } public void Insert (int data) {node newNode = new node (data); if (root == null) root = newNode; else {node arus = root; Node Parent; while (true) {// Temukan Posisi Sisipkan Parent = saat ini; if (data <current.data) {current = current.left; if (current == null) {parent.left = newNode; kembali; }} else {current = current.right; if (current == null) {parent.right = newNode; kembali; }}}}}}} // Input Nilai Numerik untuk Membangun Pohon Biner Membatalkan Buildtree (int [] data) {untuk (int i = 0; i <data.length; i ++) {insert (data [i]); }}} // Metode traversal in-order secara rekursif mengimplementasikan public void inorder (node localroot) {if (localRoot! = Null) {inorder (localroot.left); System.out.print (localroot.data+""); inorder (localroot.right); }} public void inorder () {this.inorder (this.root); } // Metode traversal preorder secara rekursif mengimplementasikan preorder public void (node localroot) {if (localRoot! = Null) {System.out.print (localroot.data+""); preorder (localroot.left); preorder (localroot.right); }} public void preorder () {this.preorder (this.root); } // Metode traversal postorder secara rekursif mengimplementasikan postorder public void (node localroot) {if (localRoot! = Null) {postorder (localroot.left); postorder (localroot.right); System.out.print (localroot.data+""); }} public void postorder () {this.postorder (this.root); } /*** Pohon biner traversal sequence-sequence: Sekarang masukkan simpul root ke dalam antrian, dan kemudian ambil node dari antrian setiap kali untuk mencetak nilai node. * Jika simpul ini memiliki simpul anak, masukkan simpul anaknya ke dalam ekor antrian sampai antrian kosong*/ public void layerTranverse () {if (this.root == null) kembali; Antrian <node> q = new LinkedList <node> (); Q.Add (this.root); while (! q.isempty ()) {node n = q.poll (); System.out.print (n.data+""); if (n.left! = null) q.add (n.left); if (n.right! = null) q.add (n.right); }} private int maxlen = 0; private int max (int a, int b) {return a> b? a: b; } public void findMaxDistance (node root) {if (root == null) return; if (root.left == null) root.leftmaxdistance = 0; if (root.right == null) root.rightmaxdistance = 0; if (root.left! = null) findMaxDistance (root.left); if (root.right! = null) findMaxDistance (root.right); // Hitung jarak maksimum dari simpul root di pohon kata kiri if (root.left! = Null) root.LeftmaxDistance = max (root.left.leftmaxdistance, root.left.rightmaxdistance) +1; // Hitung jarak maksimum dari simpul root di pohon kata kanan jika (root.right! = Null) root.rightmaxdistance = max (root.right.leftmaxdistance, root.right.rightmaxdistance) +1; // Dapatkan jarak maksimum semua node dari pohon biner jika (root.leftmaxdistance+root.rightmaxdistance> maxlen) {maxlen = root.LeftmaxDistance+root.RightmaxDistance; }} public static void main (string [] args) {binertree bitree = binertree baru (); int [] data = {2,8,7,4,9,3,1,6,7,5}; bitree.buildtree (data); System.out.print ("Traversal in-order dari pohon biner:"); bitree.inorder (); System.out.println (); System.out.print ("Pre-order Traversal of Binary Tree:"); bitree.preorder (); System.out.println (); System.out.println (); System.out.println (); System.out.print ("Pasca-orde Traversal of Binary Tree:"); bitree.postorder (); System.out.println (); System.out.print ("Lapisan Lapisan Pohon Biner:"); bitree.layertranverse (); System.out.println (); bitree.findmaxdistance (bitree.root); System.out.println ("Jarak maksimum node di pohon biner:"+bitree.maxlen); }}Di atas adalah semua konten artikel ini. Saya berharap konten artikel ini akan membantu untuk belajar atau bekerja semua orang. Saya juga berharap untuk mendukung wulin.com lebih lanjut!