이번 글에서는 데이터 구조의 중위순회(inorder traversal)에 대해 알아보겠습니다.
컬렉션 자바
오름차순으로 노드를 순회하려면 중위 순회를 사용합니다. 중위 순회에 필요한 단계는 다음과 같습니다.
- 왼쪽 하위 트리의 모든 노드를 방문합니다.
- 루트 노드 방문
- 오른쪽 하위 트리의 모든 노드를 방문합니다.
스택, 배열, 큐 등과 같은 선형 데이터 구조에는 데이터를 탐색하는 한 가지 방법만 있습니다. 그러나 다음과 같은 계층적 데이터 구조에서는 나무, 데이터를 탐색하는 방법에는 여러 가지가 있습니다. 여기서는 트리 데이터 구조를 순회하는 또 다른 방법, 즉 중위순회에 대해 논의하겠습니다.
중위 순회에는 두 가지 접근 방식이 사용됩니다.
- 재귀를 이용한 중위 순회
- Iterative 방법을 사용한 중위 순회
중위 순회 기술은 다음과 같습니다. 왼쪽 루트 오른쪽 정책. 여기서 Left Root Right는 루트 노드의 왼쪽 하위 트리를 먼저 순회한 다음 루트 노드, 루트 노드의 오른쪽 하위 트리를 순회한다는 의미입니다. 여기서 inorder 이름 자체는 루트 노드가 왼쪽 하위 트리와 오른쪽 하위 트리 사이에 있음을 나타냅니다.
재귀 및 반복 기술을 모두 사용하여 중위 순회에 대해 논의합니다. 먼저 재귀를 사용한 중위 순회부터 시작해 보겠습니다.
재귀를 이용한 중위 순회
Step 1: Recursively traverse the left subtree Step 2: Now, visit the root Step 3: Traverse the right subtree recursively
중위순회 예시
이제 중위 순회(inorder traversal)의 예를 살펴보겠습니다. 예제를 통해 중순회 과정을 이해하는 것이 더 쉬울 것입니다.
노란색으로 표시된 노드는 아직 방문하지 않았습니다. 이제 중위 순회를 사용하여 위 트리의 노드를 순회하겠습니다.
- 여기서 40은 루트 노드입니다. 40의 왼쪽 하위 트리, 즉 30으로 이동하고 여기에도 하위 트리 25가 있으므로 다시 25의 왼쪽 하위 트리인 15로 이동합니다. 여기서 15에는 하위 트리가 없으므로 인쇄 15 상위 노드인 25를 향해 이동합니다.
- 지금, 인쇄 25 25의 오른쪽 하위 트리로 이동합니다.
- 지금, 인쇄 28 루트 노드 25, 즉 30으로 이동합니다.
- 따라서 30의 왼쪽 하위 트리를 방문합니다. 지금, 30을 인쇄하다 30의 오른쪽 자식으로 이동합니다.
- 지금, 인쇄 35 루트 노드 30으로 이동합니다.
- 지금, 루트 노드 40 인쇄 오른쪽 하위 트리로 이동합니다.
- 이제 40의 오른쪽 하위 트리인 50을 재귀적으로 순회합니다.
50에는 하위 트리가 있으므로 먼저 50의 왼쪽 하위 트리인 45를 순회합니다. 45에는 자식이 없으므로 인쇄 45 그리고 루트 노드로 이동합니다.
- 지금 50을 인쇄하세요 50의 오른쪽 하위 트리인 60으로 이동합니다.
- 이제 50의 오른쪽 하위 트리인 60을 재귀적으로 순회합니다. 60에는 하위 트리가 있으므로 먼저 60의 왼쪽 하위 트리인 55를 순회합니다. 55에는 자식이 없으므로 인쇄 55 그리고 루트 노드로 이동합니다.
- 지금 인쇄 60 60의 오른쪽 하위 트리인 70으로 이동합니다.
- 지금 70을 인쇄하세요.
중위 순회가 완료된 후 최종 출력은 다음과 같습니다.
{15, 25, 28, 30, 35, 40, 45, 50, 55, 60, 70}
중위순회 복잡성
중위 순회(Inorder Traversal)의 시간복잡도는 다음과 같습니다. 에), 여기서 'n'은 이진 트리의 크기입니다.
반면, 중위 순회(Inorder Traversal)의 공간 복잡도는 다음과 같습니다. 오(1), 함수 호출의 스택 크기를 고려하지 않는 경우. 그렇지 않으면 중위 순회(Inorder Traversal)의 공간 복잡도는 다음과 같습니다. 오), 여기서 'h'는 트리의 높이입니다.
중위 순회 구현
이제 다양한 프로그래밍 언어에서 중위순회 구현을 살펴보겠습니다.
프로그램: C 언어로 중위 순회를 구현하는 프로그램을 작성하세요.
#include #include struct node { int element; struct node* left; struct node* right; }; /*To create a new node*/ struct node* createNode(int val) { struct node* Node = (struct node*)malloc(sizeof(struct node)); Node->element = val; Node->left = NULL; Node->right = NULL; return (Node); } /*function to traverse the nodes of binary tree in Inorder*/ void traverseInorder(struct node* root) { if (root == NULL) return; traverseInorder(root->left); printf(' %d ', root->element); traverseInorder(root->right); } int main() { struct node* root = createNode(40); root->left = createNode(30); root->right = createNode(50); root->left->left = createNode(25); root->left->right = createNode(35); root->left->left->left = createNode(15); root->left->left->right = createNode(28); root->right->left = createNode(45); root->right->right = createNode(60); root->right->right->left = createNode(55); root->right->right->right = createNode(70); printf('
The Inorder traversal of given binary tree is -
'); traverseInorder(root); return 0; } 산출
프로그램: C++에서 중위순회를 구현하는 프로그램을 작성하세요.
#include using namespace std; struct node { int element; struct node* left; struct node* right; }; /*To create a new node*/ struct node* createNode(int val) { struct node* Node = (struct node*)malloc(sizeof(struct node)); Node->element = val; Node->left = NULL; Node->right = NULL; return (Node); } /*function to traverse the nodes of binary tree in Inorder*/ void traverseInorder(struct node* root) { if (root == NULL) return; traverseInorder(root->left); cout<<' '<element<right); } int main() { struct node* root="createNode(39);" root->left = createNode(29); root->right = createNode(49); root->left->left = createNode(24); root->left->right = createNode(34); root->left->left->left = createNode(14); root->left->left->right = createNode(27); root->right->left = createNode(44); root->right->right = createNode(59); root->right->right->left = createNode(54); root->right->right->right = createNode(69); cout<<'
the inorder traversal of given binary tree is -
'; traverseinorder(root); return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/15/inorder-traversal-14.webp" alt="Inorder Traversal"> <p> <strong>Program:</strong> Write a program to implement inorder traversal in C#.</p> <pre> using System; class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class BinaryTree { Node root; BinaryTree() { root = null; } void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); Console.Write(node.value + ' '); traverseInorder(node.right); } void traverseInorder() { traverseInorder(root); } static void Main() { BinaryTree bt = new BinaryTree(); bt.root = new Node(36); bt.root.left = new Node(26); bt.root.right = new Node(46); bt.root.left.left = new Node(21); bt.root.left.right = new Node(31); bt.root.left.left.left = new Node(11); bt.root.left.left.right = new Node(24); bt.root.right.left = new Node(41); bt.root.right.right = new Node(56); bt.root.right.right.left = new Node(51); bt.root.right.right.right = new Node(66); Console.WriteLine('The Inorder traversal of given binary tree is - '); bt.traverseInorder(); } } </pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/15/inorder-traversal-15.webp" alt="Inorder Traversal"> <p> <strong>Program:</strong> Write a program to implement inorder traversal in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class InorderTraversal { Node root; InorderTraversal() { root = null; } void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); System.out.print(node.value + ' '); traverseInorder(node.right); } void traverseInorder() { traverseInorder(root); } public static void main(String args[]) { InorderTraversal pt = new InorderTraversal(); pt.root = new Node(35); pt.root.left = new Node(25); pt.root.right = new Node(45); pt.root.left.left = new Node(20); pt.root.left.right = new Node(30); pt.root.left.left.left = new Node(10); pt.root.left.left.right = new Node(23); pt.root.right.left = new Node(40); pt.root.right.right = new Node(55); pt.root.right.right.left = new Node(50); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println('The Inorder traversal of given binary tree is - '); pt.traverseInorder(); System.out.println(); } } </pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/15/inorder-traversal-16.webp" alt="Inorder Traversal"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></'
></'> 산출
프로그램: Java에서 중위순회를 구현하는 프로그램을 작성하세요.
class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class InorderTraversal { Node root; InorderTraversal() { root = null; } void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); System.out.print(node.value + ' '); traverseInorder(node.right); } void traverseInorder() { traverseInorder(root); } public static void main(String args[]) { InorderTraversal pt = new InorderTraversal(); pt.root = new Node(35); pt.root.left = new Node(25); pt.root.right = new Node(45); pt.root.left.left = new Node(20); pt.root.left.right = new Node(30); pt.root.left.left.left = new Node(10); pt.root.left.left.right = new Node(23); pt.root.right.left = new Node(40); pt.root.right.right = new Node(55); pt.root.right.right.left = new Node(50); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println('The Inorder traversal of given binary tree is - '); pt.traverseInorder(); System.out.println(); } } 산출
이것이 기사의 전부입니다. 이 기사가 귀하에게 도움이 되고 유익한 정보가 되기를 바랍니다.