중위순회 의 유형으로 정의됩니다. 트리 순회 기술 이는 다음과 같이 왼쪽-루트-오른쪽 패턴을 따릅니다.
- 왼쪽 하위 트리가 먼저 탐색됩니다.
- 그런 다음 해당 하위 트리의 루트 노드를 순회합니다.
- 마지막으로 오른쪽 하위 트리를 순회합니다.
중위순회
이진 트리의 중위순회 알고리즘
중위 순회 알고리즘은 다음과 같습니다.
중위(루트):
- 루트 != NULL이 될 때까지 2~4단계를 따르세요.
- 중위(루트 -> 왼쪽)
- 루트 쓰기 -> 데이터
- 중위(루트 -> 오른쪽)
- 루프 종료
이진 트리의 중위순회는 어떻게 작동하나요?
다음 트리를 고려해보세요.
이진 트리의 예
이 이진 트리에서 중위 순회를 수행하면 순회는 다음과 같습니다.
1 단계: 순회는 1에서 왼쪽 하위 트리(예: 2)로 이동한 다음 2에서 왼쪽 하위 트리 루트(예: 4)로 이동합니다. 이제 4에는 왼쪽 하위 트리가 없으므로 방문하게 됩니다. 또한 올바른 하위 트리도 없습니다. 따라서 4에서 더 이상 순회하지 않습니다.
노드 4가 방문되었습니다.
2 단계: 2의 왼쪽 하위 트리를 완전히 방문했으므로 이제 오른쪽 하위 트리로 이동하기 전에 노드 2의 데이터를 읽습니다.
노드 2가 방문되었습니다.
3단계: 이제 2의 오른쪽 하위 트리가 순회됩니다. 즉, 노드 5로 이동합니다. 노드 5에는 왼쪽 하위 트리가 없으므로 방문하고 그 후에는 노드 5의 오른쪽 하위 트리가 없기 때문에 순회가 다시 돌아옵니다.
노드 5를 방문했습니다.
4단계: 노드 1의 왼쪽 하위 트리와 마찬가지로 루트 자체, 즉 노드 1을 방문하게 됩니다.
노드 1이 방문됨
5단계: 노드 1의 왼쪽 하위 트리와 노드 자체를 방문합니다. 이제 1의 오른쪽 하위 트리가 탐색됩니다. 즉, 노드 3으로 이동합니다. 노드 3에는 왼쪽 하위 트리가 없으므로 방문됩니다.
노드 3이 방문됨
6단계: 노드 3의 왼쪽 하위 트리와 노드 자체를 방문합니다. 따라서 오른쪽 하위 트리를 탐색하고 노드 6을 방문합니다. 이제 모든 노드를 탐색하면서 탐색이 종료됩니다.
전체 트리가 순회됩니다.
문자열에서 마지막 문자 제거따라서 노드 순회 순서는 다음과 같습니다. 4 -> 2 -> 5 -> 1 -> 3 -> 6 .
이진 트리의 중위 순회를 구현하는 프로그램:
다음은 중위 순회 코드 구현입니다.
C++
// C++ program for inorder traversals> #include> using> namespace> std;> // Structure of a Binary Tree Node> struct> Node {> >int> data;> >struct> Node *left, *right;> >Node(>int> v)> >{> >data = v;> >left = right = NULL;> >}> };> // Function to print inorder traversal> void> printInorder(>struct> Node* node)> {> >if> (node == NULL)> >return>;> >// First recur on left subtree> >printInorder(node->왼쪽);> >// Now deal with the node> >cout ' '; // Then recur on right subtree printInorder(node->오른쪽); } // 드라이버 코드 int main() { struct Node* root = new Node(1); 루트->왼쪽 = 새 노드(2); 루트->오른쪽 = new Node(3); 루트->왼쪽->왼쪽 = new Node(4); 루트->왼쪽->오른쪽 = new Node(5); 루트->오른쪽->오른쪽 = new Node(6); // 함수 호출 cout<< 'Inorder traversal of binary tree is:
'; printInorder(root); return 0; }> |
>
>
자바
// Java program for inorder traversals> import> java.util.*;> // Structure of a Binary Tree Node> class> Node {> >int> data;> >Node left, right;> >Node(>int> v)> >{> >data = v;> >left = right =>null>;> >}> }> // Main class> class> GFG {> >// Function to print inorder traversal> >public> static> void> printInorder(Node node)> >{> >if> (node ==>null>)> >return>;> >// First recur on left subtree> >printInorder(node.left);> >// Now deal with the node> >System.out.print(node.data +>' '>);> >// Then recur on right subtree> >printInorder(node.right);> >}> >// Driver code> >public> static> void> main(String[] args)> >{> >Node root =>new> Node(>1>);> >root.left =>new> Node(>2>);> >root.right =>new> Node(>3>);> >root.left.left =>new> Node(>4>);> >root.left.right =>new> Node(>5>);> >root.right.right =>new> Node(>6>);> >// Function call> >System.out.println(> >'Inorder traversal of binary tree is: '>);> >printInorder(root);> >}> }> // This code is contributed by prasad264> |
자바와 비교
>
>
파이썬3
# Structure of a Binary Tree Node> class> Node:> >def> __init__(>self>, v):> >self>.data>=> v> >self>.left>=> None> >self>.right>=> None> # Function to print inorder traversal> def> printInorder(node):> >if> node>is> None>:> >return> ># First recur on left subtree> >printInorder(node.left)> ># Now deal with the node> >print>(node.data, end>=>' '>)> ># Then recur on right subtree> >printInorder(node.right)> # Driver code> if> __name__>=>=> '__main__'>:> >root>=> Node(>1>)> >root.left>=> Node(>2>)> >root.right>=> Node(>3>)> >root.left.left>=> Node(>4>)> >root.left.right>=> Node(>5>)> >root.right.right>=> Node(>6>)> ># Function call> >print>(>'Inorder traversal of binary tree is:'>)> >printInorder(root)> |
>
>
씨#
Java 메소드의 배열
// C# program for inorder traversals> using> System;> // Structure of a Binary Tree Node> public> class> Node {> >public> int> data;> >public> Node left, right;> >public> Node(>int> v)> >{> >data = v;> >left = right =>null>;> >}> }> // Class to store and print inorder traversal> public> class> BinaryTree {> >// Function to print inorder traversal> >public> static> void> printInorder(Node node)> >{> >if> (node ==>null>)> >return>;> >// First recur on left subtree> >printInorder(node.left);> >// Now deal with the node> >Console.Write(node.data +>' '>);> >// Then recur on right subtree> >printInorder(node.right);> >}> >// Driver code> >public> static> void> Main()> >{> >Node root =>new> Node(1);> >root.left =>new> Node(2);> >root.right =>new> Node(3);> >root.left.left =>new> Node(4);> >root.left.right =>new> Node(5);> >root.right.right =>new> Node(6);> >// Function call> >Console.WriteLine(> >'Inorder traversal of binary tree is: '>);> >printInorder(root);> >}> }> |
>
메이크업 제품 이름
>
자바스크립트
// JavaScript program for inorder traversals> // Structure of a Binary Tree Node> class Node {> >constructor(v) {> >this>.data = v;> >this>.left =>null>;> >this>.right =>null>;> >}> }> // Function to print inorder traversal> function> printInorder(node) {> >if> (node ===>null>) {> >return>;> >}> > >// First recur on left subtree> >printInorder(node.left);> > >// Now deal with the node> >console.log(node.data);> > >// Then recur on right subtree> >printInorder(node.right);> }> // Driver code> const root =>new> Node(1);> root.left =>new> Node(2);> root.right =>new> Node(3);> root.left.left =>new> Node(4);> root.left.right =>new> Node(5);> root.right.right =>new> Node(6);> // Function call> console.log(>'Inorder traversal of binary tree is: '>);> printInorder(root);> |
>
>산출
Inorder traversal of binary tree is: 4 2 5 1 3 6>
설명:
중위 순회 작동 방식
복잡성 분석:
시간 복잡도: O(N) 여기서 N은 총 노드 수입니다. 왜냐하면 모든 노드를 적어도 한 번은 통과하기 때문입니다.
보조 공간: 재귀 스택 공간을 고려하지 않는 경우 O(1)입니다. 그렇지 않으면, O(h) 여기서 h는 트리의 높이입니다.
- 최악의 경우, 시간 와 같을 수 있다 N (나무가 기울어진 나무인 경우)
- 최선의 경우, 시간 와 같을 수 있다 침착한 (트리가 완전한 트리인 경우)
중위 순회 사용 사례:
BST(이진 검색 트리)의 경우 비감소 순서로 노드를 가져와야 하는 경우 가장 좋은 방법은 중위 순회를 구현하는 것입니다.
관련 기사:
- 트리 순회 유형
- 반복 중위순회
- 선순 및 중순 순회를 통해 이진 트리 구성
- 트리의 중위 순회를 위한 모리스 순회
- 재귀 없는 중위 순회