트리의 중위 순회는 트리의 각 노드를 가장 왼쪽 노드를 먼저 방문한 다음 루트, 마지막으로 가장 오른쪽 노드를 차례로 방문하는 방법입니다. 순회는 주어진 데이터 구조의 값의 각 요소를 방문하는 방식입니다. 각 선형 데이터 구조에는 해당 요소를 탐색할 수 있는 방법이 하나만 있습니다. 선형 데이터 구조에는 배열, 스택, 큐 및 연결 목록이 있습니다. 그러나 트리와 같은 비선형 데이터 구조의 경우 노드를 방문할 수 있는 방법과 순서는 여러 가지가 있습니다. 기본 주문순회 방식은 순서, 선주문, 후주문 순회 방식 3가지가 있습니다.
무료 소프트웨어 개발 과정 시작
웹 개발, 프로그래밍 언어, 소프트웨어 테스팅 등
이 글에서는 순차 순회 방법과 그것이 이진 트리에서 어떻게 작동하는지 알아보겠습니다. 또한 C 프로그래밍 언어를 사용하여 순서대로 순회를 구현하는 방법에 대한 예 중 하나를 살펴보겠습니다.
중위 순회를 사용하여 트리를 순회할 때 사용되는 알고리즘이나 단계는 다음과 같습니다.
그림과 같이 노드가 있는 트리를 생각해 보세요 –
위의 트리 예에서 순회는 먼저 식물의 가장 왼쪽 노드 또는 잎인 3에서 시작한 다음 주요 직계 부모인 6을 순회합니다. 그 후에 우리는 다음으로 이동합니다. 오른쪽 자식을 검색하지만, 6개 노드의 오른쪽 자식이 없다는 것을 볼 수 있으므로 이제 6번째 노드의 직계 부모인 12를 방문하고 이러한 방식으로 탐색 여정을 계속할 것입니다. 마지막으로 결과 순회 순서는 아래와 같습니다 –
3 -> 6 -> 12 -> 13 -> 14 -> 15 -> 20 -> 17 -> 23 -> 27
중위 순회는 주로 이진 검색 트리에서 사용됩니다. 중위순회(inorder traversal)의 역방향 알고리즘은 노드 값의 비증가 순서를 얻는 데 사용됩니다. 비감소 형식으로 노드를 검색하려는 경우 중위순회 변형을 사용할 필요가 없습니다. 위에서 설명한 것과 동일한 중위 순회 방법을 사용하여 이진 트리의 감소하지 않는 값을 얻을 수 있습니다.
중위순회 흐름과 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!