Artikel ini menjelaskan traversal kedalaman dan algoritma traversal pertama yang menerapkan pohon biner di Java. Bagikan untuk referensi Anda, sebagai berikut:
1. Analisis
Praktik umum dari non-rekursif dari traversal pohon biner yang kedalaman adalah untuk mengadopsi tumpukan, dan praktik umum non-rekursif traversal yang luas adalah mengadopsi antrian.
Traversal kedalaman-pertama : Setiap jalur cabang yang mungkin dapat ditembus sampai tidak dapat lebih dalam, dan setiap node hanya dapat diakses sekali. Perlu dicatat bahwa traversal kedalaman pohon biner cukup istimewa dan dapat dibagi lagi menjadi traversal preorder, traversal menengah, dan traversal berikutnya. Deskripsi spesifiknya adalah sebagai berikut:
Pesanan Pertama Traversal : Untuk subtree apa pun, pertama -tama akses root, lalu lintasi subtree kirinya, dan akhirnya melintasi subtree kanannya.
Traversal Urutan Tengah : Untuk subtree apa pun, pertama -tama melintasi subtree kirinya, lalu mengakses root, dan akhirnya melintasi subtree kanannya.
Post-order Traversal : Untuk subtree apa pun, pertama-tama melintasi subtree kirinya, lalu melintasi subtree kanannya, dan akhirnya mengakses root.
TRAVERSAL LUAR BIASA : Juga dikenal sebagai hierarki, mengakses setiap lapisan dari atas ke bawah secara bergantian. Di setiap lapisan, akses node dari kiri ke kanan (atau dari kanan ke kiri). Setelah mengakses satu lapisan, Anda akan memasukkan lapisan berikutnya sampai tidak ada node yang dapat diakses.
2. Berikan contoh
Pohon penyortiran biner yang ditunjukkan pada gambar di bawah ini membutuhkan penggunaan traversal preorder (rekursif, non-rekursif), traversal in-order (rekursif, non-rekursif), traversal postorder (rekursif, non-rekursif), dan traversal yang luas.
① Kode referensi
Paket BinaryTreetraversetest; impor java.util.linkedlist; impor java.util.queue;/** * prioritas kedalaman traversal dan prioritas lebarnya traversal pohon biner * @author fantasy * @Version 1.0 2016/05 - 2016/10/07 */Kelas publik Binertreet Binary Binary Binerrav {Binary Publicer BinerRav {Public Class Binary {2016/05 - 2016/10/07 */Kelas Publik Binary Binary Binary Publicer Binary Public BinarySorttree <Integer> pohon = BinarySorttree baru <Integer> (); Tree.insertnode (35); Tree.insertnode (20); Tree.insertnode (15); Tree.insertnode (16); Tree.insertnode (29); Tree.insertnode (28); Tree.insertnode (30); Tree.insertnode (40); Tree.insertnode (50); Tree.insertnode (45); Tree.insertnode (55); System.out.print ("Preorder Traversal (Recursive):"); Tree.preoRderTraverse (Tree.getroot ()); System.out.println (); System.out.print ("In-order Traversal (Recursive):"); Tree.InorDerTraverse (Tree.getroot ()); System.out.println (); System.out.println (); System.out.print ("Pasca-orde Traversal (Rekursif):"); Tree.PostOrderTraverse (Tree.getroot ()); System.out.println (); System.out.print ("Traversal Prekursif (Non-Recursive):"); Tree.PreerDtraversenorecursion (Tree.getroot ()); System.out.println (); System.out.print ("In-order Traversal (Non-Recursive):"); Tree.InorDerTraversenorecursion (Tree.getroot ()); System.out.println (); System.out.println (); System.out.print ("Pasca-orde Traversal (Non-Recursive):"); Tree.PostOrderTraversenorecursion (Tree.getroot ()); System.out.println (); System.out.print ("Traversal Luas:"); tree.breadthfirsttraverse (tree.getroot ()); }}/*** node*/class node <e memperluas sebanding <e>> {nilai e; Simpul <e> kiri; Node <e> benar; Node (nilai e) {this.value = nilai; kiri = null; kanan = null; }}/** * Gunakan urutan preseden untuk membangun pohon penyortiran biner (juga dikenal sebagai pohon pencarian biner) */kelas BinarySorttree <e memperluas yang sebanding <e>> {node pribadi <e> root; BinarySorttree () {root = null; } public void insertNode (nilai e) {if (root == null) {root = nod node <E> (value); kembali; } Node <E> currentNode = root; while (true) {if (value.compareto (currentNode.Value)> 0) {if (currentNode.Right == null) {currentNode.Right = node baru <E> (value); merusak; } currentNode = currentNode.Right; } else {if (currentNode.left == null) {currentNode.left = node new <e> (value); merusak; } currentNode = currentNode.Left; }}} node publik <E> getRoot () {return root; } / ** * Pre-order Traversal dari pohon biner (rekursif) * @param node * / public void preordertraverse (node <e> node) {System.out.print (node.value + ""); if (node.left! = null) preordertraverse (node.left); if (node.right! = null) preordertraverse (node.right); } / ** * traversal in-order dari pohon biner (rekursif) * @param node * / public void inordertraverse (node <e> node) {if (node.left! = Null) inordertraverse (node.left); System.out.print (Node.Value + ""); if (node.right! = null) inordertraverse (node.right); } / ** * Post-order Traversal dari Binary Tree (Recursive) * @param node * / public void postordertraverse (node <E> node) {if (node.left! = Null) postordertraverse (node.left); if (node.right! = null) postordertraverse (node.right); System.out.print (Node.Value + ""); } / ** * Pre-order Traversal dari pohon biner (non-rekursif) * @param root * / public void preordertraversenorecursion (node <e> root) {LinkedList <node <e>> stack = new LinkedList <node <e>> (); Node <e> currentNode = null; stack.push (root); while (! stack.isempty ()) {currentNode = stack.pop (); System.out.print (currentNode.Value + ""); if (currentNode.right! = null) stack.push (currentNode.Right); if (currentNode.left! = null) stack.push (currentNode.Left); }} / ** * Traversal in-order dari pohon biner (non-rekursif) * @param root * / public void inordertraversenorecursion (node <e> root) {LinkedList <node <e>> stack = new LinkedList <node <E>> (); Node <e> currentNode = root; while (currentNode! = null ||! stack.isempty ()) {// loop sampai simpul daun paling kiri pada pohon penyortiran biner (currentNode adalah null) while (currentNode! = null) {stack.push (currentNode); currentNode = currentNode.Left; } currentNode = stack.pop (); System.out.print (currentNode.Value + ""); currentNode = currentNode.Right; }} / ** * Traversal pasca-order dari pohon biner (non-rekursif) * @param root * / public void posterDerTraversenoRecursion (node <e> root) {LinkedList <node <e>> stack = new LinkedList <Node <E> () (); Node <e> currentNode = root; Node <E> rightNode = null; while (currentNode! = null ||! stack.isempty ()) {// loop sampai simpul daun di ujung paling kiri dari pohon penyortiran biner (currentNode adalah null) sementara (currentNode! = null) {stack.push (currentNode); currentNode = currentNode.Left; } currentNode = stack.pop (); // Node saat ini tidak memiliki simpul kanan atau simpul sebelumnya (simpul yang telah output) adalah simpul kanan dari simpul saat ini, maka node saat ini adalah output sementara (currentNode.right == null || curetnode.right == rightNode) {System.out.print (currentNode.Value + ""); rightNode = currentNode; if (stack.isempty ()) {return; // output root, ujung traversal} currentNode = stack.pop (); } stack.push (currentNode); // Masih ada simpul yang tepat yang tidak melintasi lancar = currentNode.Right; }} / *** Tree Binary Lebaran-First-First, juga dikenal sebagai pohon biner traversal hierarkis* @param node* / public void lughfirsttraverse (node <e> root) {queue <node <e>> quue = new LinkedList <node <e> (); Node <e> currentNode = null; antrian.offer (root); while (! queue.isempty ()) {currentNode = queue.poll (); System.out.print (currentNode.Value + ""); if (currentNode.left! = null) queue.offer (currentNode.Left); if (currentNode.right! = null) queue.offer (currentNode.Right); }}}② Hasil output
Preorder Traversal (Rekursif): 35 20 15 16 29 28 30 40 50 45 55
Traversal in-order (rekursi): 15 16 20 28 29 30 35 40 45 50 55
Postorder Traversal (Rekursi): 16 15 28 30 29 20 45 55 50 40 35
Preorder Traversal (Non-Recursive): 35 20 15 16 29 28 30 40 50 45 55
Traversal in-order (non-rekursif): 15 16 20 28 29 30 35 40 45 50 55
Postorder Traversal (Non-Recursive): 16 15 28 30 29 20 45 55 50 40 35
Prioritas luas Traversal: 35 20 40 15 29 50 16 28 30 45 55
Untuk informasi lebih lanjut tentang algoritma java, pembaca yang tertarik dengan situs ini dapat melihat topik: "struktur data java dan tutorial algoritma", "ringkasan tips node dom java", "ringkasan file operasi java dan direktori" dan "ringkasan tip operasi java cache" tips java "tips java" Tips "Java Cache Tips"
Saya harap artikel ini akan membantu pemrograman Java semua orang.