Inorder Traversal Java

Perjalanan tertib pokok ialah cara melawati setiap nod pokok mengikut urutan nod paling kiri dilawati dahulu kemudian akar dan akhir sekali nod paling kanan. Merentasi ialah cara kita melawati setiap elemen nilai struktur data yang diberikan. Setiap struktur data linear hanya mempunyai satu cara di mana unsur-unsurnya boleh dilalui. Struktur data linear ialah tatasusunan, tindanan, baris gilir dan senarai terpaut. Tetapi dalam kes struktur data bukan linear seperti pepohon, terdapat pelbagai cara dan susunan yang mungkin di mana nod boleh dilawati. Terdapat tiga kaedah urutan pesanan asas, prapesanan dan kaedah traversal pesanan selepas.

Mulakan Kursus Pembangunan Perisian Percuma Anda

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

Dalam artikel ini, kita akan mengkaji kaedah traversal tertib dan cara ia berfungsi dalam pokok binari. Kita juga akan melihat salah satu contoh bagaimana traversal tertib boleh dilaksanakan menggunakan bahasa pengaturcaraan C.

Kerja Inorder Traversal

Algoritma atau langkah yang digunakan semasa melintasi pokok menggunakan traversal tersusun adalah seperti yang disenaraikan di bawah –

• Perkara pertama yang perlu dilakukan ialah melintasi semua nod sub pokok kiri mengikut cara di mana nod kiri pertama dilawati kemudian nod utama dan kemudian nod kanan.
• Sekarang, lawati nod akar pokok.
• Sudah tiba masanya untuk melawati subpokok kanan selepas merentasi subpokok kiri dan melawat akar.

Pertimbangkan pokok di mana nodnya adalah seperti yang ditunjukkan dalam rajah –

Dalam contoh pokok yang diberikan di atas, penyeberangan akan mula-mula bermula dari nod atau daun paling kiri tumbuhan iaitu 3, dan kemudian kita akan melintasi induk utama utamanya iaitu 6. Selepas itu, kita akan pergi kerana mencari anak kanannya, tetapi, seperti yang kita dapat lihat tiada anak kanan daripada 6 nod, oleh itu, kini akan melawati ibu bapa terdekat 6 nod iaitu 12, dan dengan cara ini akan meneruskan perjalanan kami merentasi. Akhirnya, terhasil tertib traversal adalah seperti yang ditunjukkan di bawah –
3 -> 6 -> 12 -> 13 -> 14 -> 15 -> 20 -> 17 -> 23 -> 27

Aplikasi traversal tersusun

Traversal inorder kebanyakannya digunakan dalam pepohon carian binari. Algoritma terbalik bagi traversal tertib digunakan untuk mendapatkan susunan nilai nod yang tidak bertambah. Sekiranya kita mahu nod diambil dalam format tidak menurun maka tidak perlu menggunakan variasi traversal tertib. Kita boleh menggunakan kaedah traversal tertib yang sama yang dibincangkan di atas untuk mendapatkan nilai tidak menurun bagi pokok binari.

Pelaksanaan Inorder traversal di Java

Untuk memahami aliran traversal tertib dan pelaksanaannya dalam bahasa pengaturcaraan Java, anda perlu mengetahui kaedah dan kelas java serta konsep objek. Program berikut menggunakan panggilan rekursif kepada kaedah traversal tertib terlebih dahulu untuk subpokok sebelah kiri selepas itu melawati nod akar dan kemudian untuk subpokok sebelah kanan. Semasa melawati setiap nod dalam traversal program memastikan untuk mencetak nilai nod yang sama yang dilawati. Oleh itu, kita dapat melihat dalam output, bagaimana semua nod dilawati dan dalam susunan mana ia dilawati.

Contoh

Kod:

import java.util.Stack;
/*
* Implementation of inorder traversal of the binary tree.
* Inorder traversal involves travelling to he left most leaf or node of the
* tree and then the root node of the tree. The last node to be traversed is
* the rightmost node or leaf of the binary tree.
*
* input:
* 43
* / \
* 23 32
* / \ \
* 13 32 95
* / / \
* 3 49 67
*
* Resulting output: 3 13 23 32 43 32 95 49 67
*/
public class Main {
public static void main(String[] args) throws Exception {
// Firstly, we will create the binary tree as displayed in the comments
BinaryTreeToTraverse bt = BinaryTreeToTraverse.create();
// With the help of recursion that means calling the same function again and again,
// we will do inorder traversal of the binary tree
System.out
.println("Using recursion, display all the nodes of the binary tree that are resulted\n by following inorder traversal :- ");
bt.inOrderTraversal();
}
}
class BinaryTreeToTraverse {
static class binaryTreeNode {
String data;
binaryTreeNode leftNode, rightNode;
binaryTreeNode(String value) {
this.data = value;
leftNode = rightNode = null;
}
}
// Root node of the considered binary tree
binaryTreeNode rootNode;
/**
* Use the inorder algorithm for traversing through the nodes in binary tree
*/
public void inOrderTraversal() {
inOrderTraversal(rootNode);
}
private void inOrderTraversal(binaryTreeNode node) {
if (node == null) {
return;
}
inOrderTraversal(node.leftNode);
System.out.printf("%s ", node.data);
inOrderTraversal(node.rightNode);
}
/**
* Consider the sample data to test the order in which the nodes are traversed in Java program
*
* @return a sample binary binaryTree for testing
*/
public static BinaryTreeToTraverse create() {
BinaryTreeToTraverse binaryTree = new BinaryTreeToTraverse();
binaryTreeNode rootNode = new binaryTreeNode("43");
binaryTree.rootNode = rootNode;
binaryTree.rootNode.leftNode = new binaryTreeNode("23");
binaryTree.rootNode.leftNode.leftNode = new binaryTreeNode("13");
binaryTree.rootNode.leftNode.leftNode.leftNode = new binaryTreeNode("3");
binaryTree.rootNode.leftNode.rightNode = new binaryTreeNode("32");
binaryTree.rootNode.rightNode = new binaryTreeNode("32");
binaryTree.rootNode.rightNode.rightNode = new binaryTreeNode("95");
binaryTree.rootNode.leftNode.rightNode.leftNode = new binaryTreeNode("49");
binaryTree.rootNode.leftNode.rightNode.rightNode = new binaryTreeNode("67");
return binaryTree;
}
}

Output:

Output pelaksanaan program di atas adalah seperti yang ditunjukkan di bawah:

Kesimpulan

Traversal inorder ialah salah satu kaedah traversing depth-first di mana semua nod dilalui dengan cara di mana mula-mula nod kiri dilalui dan kemudian root dan kemudian subtree kanan dilalui. Daun paling kiri pokok adalah nod pertama yang dilawati manakala daun paling kanan adalah yang terakhir dilalui dalam traversal tersusun. Kaedah merentasi tertib digunakan secara meluas dalam pepohon carian binari untuk mendapatkan susunan nilai yang tidak menurun atau tidak meningkat. Pelaksanaan java boleh dilakukan sama ada dalam format rekursif atau format berulang. Kaedah rekursi digunakan di sini untuk pelaksanaan di mana kaedah yang sama dipanggil berulang kali untuk melaksanakan traversal tertib.

Atas ialah kandungan terperinci Inorder Traversal Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!