Melintasi pokok Jawa

Java tree traversal ditakrifkan sebagai algoritma yang dilaksanakan dalam bahasa pengaturcaraan Java, yang terdiri daripada pepohon sebagai struktur data dan menggabungkan asas melawati semua nod pepohon melalui pelaksanaan algoritma. Traversal dalam terminologi struktur data sains komputer menunjukkan bahawa semua nod dalam struktur data perlu dilawati untuk menyelesaikan tugas yang lebih besar di tangan. Komponen pokok ialah nod akar dan anak, sebahagian daripadanya berakhir pada nod tertentu itu dan dinamakan sebagai daun dan yang lain mencipta lebih banyak subpokok. Dalam artikel ini, kita akan melalui pelaksanaan traversal pokok di Jawa dan melihat kaedah berbeza yang boleh kita capai.

Mulakan Kursus Pembangunan Perisian Percuma Anda

Pembangunan web, bahasa pengaturcaraan, ujian perisian & lain-lain

Sintaks

Pengisytiharan kelas dalam Java:

class <class name> {
// List the fields (variables) for the class
// Define the methods of the class to perform the specified operations
}

Mentakrifkan kaedah dalam Java:

returnType <method name>() {
// Body of the method that constitutes the steps that will fulfill the assigned task
}

Mengisytiharkan nod dalam Java:

Node<{ Data Type }> <variable name> = new Node<{ Data Type }>(" <Value>");
Access the left of the node in Java:
<variable name>.left

Akses sebelah kanan nod dalam Java:

<variable name>.right

Bagaimana untuk melakukan traversal Pokok di Jawa?

Sebelum kita mula membincangkan cara yang berbeza untuk melintasi pokok di Jawa, pertama sekali kita perlu mengetahui cara pokok itu berstruktur kerana ini adalah salah satu komponen penting untuk membina pokok itu sebagai kelas di Jawa. Pokok mempunyai nod, dan oleh itu kami mentakrifkan kelas nod. Kelas ini akan mempunyai medan sebagai data yang mewakili data nod, penunjuk kiri yang menghala ke kiri nod dan satu lagi penunjuk yang menghala ke kanan nod. Semua medan ini membentuk kelas Node. Di bawah ialah skema rupa pokok:

Setelah kami menentukan kelas pokok yang membentuk nod dan penunjuk, kini tiba masanya untuk melihat 3 jenis traversal yang dilaksanakan di Jawa dan setiap satu daripadanya mempunyai tandatangan traversal sendiri:

1 Traversal Tertib

Cara traversal ini ditakrifkan ialah kita melawati elemen sub pokok kiri, diikuti dengan nod subtree, dan kemudian akhirnya melintasi subtree kanan. Pseudokod adalah seperti berikut:

• Panggil fungsi secara rekursif dengan melepasi nod kiri sehingga kita mencapai nod sebagai nol.
• Paparkan data
• Panggil fungsi secara rekursif dengan melepasi nod kanan sehingga kita mencapai nod sebagai nol.

Laluan traversal algoritma In-order ialah: Nod 1.1→Nod 1→Nod 1.2→Root→Nod 2.

2. Pra-pesanan Traversal

Cara traversal ini ditakrifkan adalah untuk melawati elemen nod akar, melintasi sub pokok kiri, dan kemudian akhirnya melintasi subtree kanan. Pseudokod adalah seperti berikut:

• Lintas nod akar dahulu.
• Panggil fungsi secara rekursif dengan melepasi nod kiri sehingga kita mencapai nod sebagai nol.
• Panggil fungsi secara rekursif dengan melepasi nod kanan sehingga kita mencapai nod sebagai nol.

Laluan traversal algoritma prapesanan ialah: Root→Nod 1→Nod 1.1→Nod 1.2→ Nod 2.

3. Pasca-pesanan Traversal

Cara traversal ini ditakrifkan ialah kita melawati elemen subtree kiri, diikuti subtree kanan, dan kemudian akhirnya melintasi nod subtree sehingga kita mencapai nod asas. Pseudokod adalah seperti berikut:

• Panggil fungsi secara rekursif dengan melepasi nod kiri sehingga kita mencapai nod sebagai nol.
• Panggil fungsi secara rekursif dengan melepasi nod kanan sehingga kita mencapai nod sebagai nol.
• Paparkan data

Laluan traversal algoritma pasca pesanan ialah: Nod 1.1→Nod 1.2→ Nod 1→Nod 2→ Root.

Contoh Java traversal Tree

Diberikan di bawah adalah contoh Java traversal Tree:

Contoh #1

Dalam urutan traversal menggunakan rekursi

Sintaks

class NodeClass {
int value;
NodeClass left, right;
public NodeClass(int key) {
value = key;
left = right = null;
}
}
class Tree {
NodeClass base;
Tree() {
base = null;
}
void inOrderFunc(NodeClass node) {
if (node == null)
return;
inOrderFunc(node.left);
System.out.print(node.value + "->");
inOrderFunc(node.right);
}
public static void main(String[] args) {
Tree tree = new Tree();
tree.base = new NodeClass(27);
tree.base.left = new NodeClass(9);
tree.base.right = new NodeClass(19);
tree.base.left.left = new NodeClass(91);
tree.base.left.right = new NodeClass(92);
System.out.println("In Order traversal");
tree.inOrderFunc(tree.base);
}
}

Output:

Contoh #2

Prepesan traversal menggunakan rekursi

Sintaks

class NodeClass {
int item;
NodeClass left, right;
public NodeClass(int key) {
item = key;
left = right = null;
}
}
class Tree {
NodeClass base;
Tree() {
base = null;
}
void preorderFunc(NodeClass node) {
if (node == null)
return;
//First the node:
System.out.print(node.item + "->");
//Recursively look at the left side of the tree
preorderFunc(node.left);
//Recursively look at the right side of the tree
preorderFunc(node.right);
}
public static void main(String[] args) {
Tree tree = new Tree();
tree.base = new NodeClass(27);
tree.base.left = new NodeClass(9);
tree.base.right = new NodeClass(19);
tree.base.left.left = new NodeClass(91);
tree.base.left.right = new NodeClass(92);
// preorderFunc tree traversal
System.out.println("Preorder traversal: ");
tree.preorderFunc(tree.base);
}
}

Output:

Contoh #3

Perjalanan pospesanan melalui rekursi

Sintaks

class NodeClass {
int item;
NodeClass left, right;
public NodeClass(int key) {
item = key;
left = right = null;
}
}
class Tree {
NodeClass base;
Tree() {
base = null;
}
void postorderFunc(NodeClass node) {
if (node == null)
return;
postorderFunc(node.left);
postorderFunc(node.right);
System.out.print(node.item + "->");
}
public static void main(String[] args) {
Tree tree = new Tree();
tree.base = new NodeClass(27);
tree.base.left = new NodeClass(9);
tree.base.right = new NodeClass(19);
tree.base.left.left = new NodeClass(91);
tree.base.left.right = new NodeClass(92);
System.out.println("Postorder traversal: ");
tree.postorderFunc(tree.base);
}
}

Output:

Kesimpulan

Artikel ini melihat semua pelbagai cara untuk melaksanakan traversal pokok di Jawa, bersama-sama dengan contoh dari dunia sebenar. Pembaca digalakkan untuk melihat traversal dengan menambahkan lebih banyak nod ke dalam kod dan melihat hasil traversal!

Atas ialah kandungan terperinci Melintasi pokok Jawa. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!