중위 순회 Java

트리의 중위 순회는 트리의 각 노드를 가장 왼쪽 노드를 먼저 방문한 다음 루트, 마지막으로 가장 오른쪽 노드를 차례로 방문하는 방법입니다. 순회는 주어진 데이터 구조의 값의 각 요소를 방문하는 방식입니다. 각 선형 데이터 구조에는 해당 요소를 탐색할 수 있는 방법이 하나만 있습니다. 선형 데이터 구조에는 배열, 스택, 큐 및 연결 목록이 있습니다. 그러나 트리와 같은 비선형 데이터 구조의 경우 노드를 방문할 수 있는 방법과 순서는 여러 가지가 있습니다. 기본 주문순회 방식은 순서, 선주문, 후주문 순회 방식 3가지가 있습니다.

무료 소프트웨어 개발 과정 시작

웹 개발, 프로그래밍 언어, 소프트웨어 테스팅 등

이 글에서는 순차 순회 방법과 그것이 이진 트리에서 어떻게 작동하는지 알아보겠습니다. 또한 C 프로그래밍 언어를 사용하여 순서대로 순회를 구현하는 방법에 대한 예 중 하나를 살펴보겠습니다.

중위 순회 작업

중위 순회를 사용하여 트리를 순회할 때 사용되는 알고리즘이나 단계는 다음과 같습니다.

• 가장 먼저 해야 할 일은 첫 번째 왼쪽 노드를 방문한 다음 메인 노드, 오른쪽 노드를 차례로 방문하는 방식으로 왼쪽 하위 트리의 모든 노드를 순회하는 것입니다.
• 이제 트리의 루트 노드를 방문하세요.
• 왼쪽 하위 트리 순회와 루트 방문을 거쳐 오른쪽 하위 트리를 방문할 차례입니다.

그림과 같이 노드가 있는 트리를 생각해 보세요 –

위의 트리 예에서 순회는 먼저 식물의 가장 왼쪽 노드 또는 잎인 3에서 시작한 다음 주요 직계 부모인 6을 순회합니다. 그 후에 우리는 다음으로 이동합니다. 오른쪽 자식을 검색하지만, 6개 노드의 오른쪽 자식이 없다는 것을 볼 수 있으므로 이제 6번째 노드의 직계 부모인 12를 방문하고 이러한 방식으로 탐색 여정을 계속할 것입니다. 마지막으로 결과 순회 순서는 아래와 같습니다 –
3 -> 6 -> 12 -> 13 -> 14 -> 15 -> 20 -> 17 -> 23 -> 27

중위순회 응용

중위 순회는 주로 이진 검색 트리에서 사용됩니다. 중위순회(inorder traversal)의 역방향 알고리즘은 노드 값의 비증가 순서를 얻는 데 사용됩니다. 비감소 형식으로 노드를 검색하려는 경우 중위순회 변형을 사용할 필요가 없습니다. 위에서 설명한 것과 동일한 중위 순회 방법을 사용하여 이진 트리의 감소하지 않는 값을 얻을 수 있습니다.

Java에서 중위순회 구현

중위순회 흐름과 Java 프로그래밍 언어의 구현을 이해하려면 Java 메소드와 클래스, 객체 개념을 알아야 합니다. 다음 프로그램은 루트 노드를 방문한 후 왼쪽 하위 트리에 대해 먼저 중위 순회 방법에 대한 재귀 호출을 사용하고 오른쪽 하위 트리에 대해 재귀 호출을 사용합니다. 순회에서 각 노드를 방문하는 동안 프로그램은 방문한 동일한 노드의 값을 인쇄합니다. 따라서 출력에서 ​​모든 노드가 어떻게 방문되었는지, 어떤 순서로 방문되었는지 확인할 수 있습니다.

예

코드:

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;
}
}

출력:

위 프로그램 실행 결과는 아래와 같습니다.

결론

중위 순회는 깊이 우선 순회 방법 중 하나로, 왼쪽 노드를 먼저 순회한 다음 루트, 오른쪽 하위 트리를 순회하는 방식으로 모든 노드를 순회합니다. 트리의 가장 왼쪽 잎은 방문할 첫 번째 노드이고, 가장 오른쪽 잎은 중위순회에서 탐색할 마지막 노드입니다. 중위 순회 방법은 비감소 또는 비증가 순서의 값을 얻기 위해 이진 검색 트리에서 광범위하게 사용됩니다. Java 구현은 재귀 형식 또는 반복 형식으로 수행될 수 있습니다. 여기서는 중위순회를 구현하기 위해 동일한 메소드를 계속해서 호출하는 구현을 위해 재귀 메소드를 사용합니다.

위 내용은 중위 순회 Java의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!