이번 글에서는 데이터 구조의 트리 순회에 대해 설명하겠습니다. '트리 순회'라는 용어는 트리의 각 노드를 순회하거나 방문하는 것을 의미합니다. 연결리스트, 큐, 스택과 같은 선형 데이터 구조를 순회하는 방법은 한 가지뿐입니다. 반면에 다음과 같이 트리를 탐색하는 여러 가지 방법이 있습니다.
- 선주문 순회
- 중위순회
- 우편 주문 순회
따라서 이 기사에서는 위에 나열된 트리 순회 기술에 대해 논의하겠습니다. 이제 트리 순회 방법에 대해 논의해 보겠습니다.
선주문 순회
이 기술은 '루트 왼쪽 오른쪽' 정책을 따릅니다. 즉, 왼쪽 하위 트리를 재귀적으로 순회한 후 첫 번째 루트 노드를 방문하고 마지막으로 오른쪽 하위 트리를 재귀적으로 순회한다는 의미입니다. 루트 노드가 왼쪽 및 오른쪽 하위 트리 이전(또는 사전)을 순회하므로 이를 선순 순회라고 합니다.
따라서 선주문 순회에서는 각 노드가 두 하위 트리보다 먼저 방문됩니다.
선주문 순회 애플리케이션에는 다음이 포함됩니다.
- 트리의 복사본을 만드는 데 사용됩니다.
- 표현식 트리의 접두사 표현식을 가져오는 데에도 사용할 수 있습니다.
연산
Until all nodes of the tree are not visited Step 1 - Visit the root node Step 2 - Traverse the left subtree recursively. Step 3 - Traverse the right subtree recursively.
예
이제 선주문 순회 기법의 예를 살펴보겠습니다.
이제 위의 트리에 선주문 순회를 적용하기 시작합니다. 먼저 루트 노드를 순회합니다. ㅏ; 그 후 왼쪽 하위 트리로 이동 비 , 이는 선주문에서도 통과됩니다.
따라서 왼쪽 하위 트리 B의 경우 먼저 루트 노드 비 자체적으로 탐색됩니다. 그 후, 왼쪽 하위 트리 디 통과됩니다. 노드 이후 디 자식이 없으면 오른쪽 하위 트리로 이동합니다. 그리고 . 노드 E에도 자식이 없으므로 루트 노드 A의 왼쪽 하위 트리 순회가 완료됩니다.
C++ 프로토타입 함수
이제 루트 노드 A의 오른쪽 하위 트리인 C를 향해 이동합니다. 따라서 오른쪽 하위 트리 C의 경우 먼저 루트 노드 씨 자체적으로 통과했습니다. 그 후, 왼쪽 하위 트리 에프 통과됩니다. 노드 이후 에프 자식이 없으면 오른쪽 하위 트리로 이동합니다. G . 노드 G에도 자식이 없으므로 루트 노드 A의 오른쪽 하위 트리 순회가 완료됩니다.
따라서 트리의 모든 노드를 순회합니다. 따라서 위 트리의 선주문 순회 결과는 다음과 같습니다.
A → B → D → E → C → F → G
자바스크립트 문자열 교체
데이터 구조의 선주문 순회에 대해 자세히 알아보려면 링크를 따라가세요. 선주문 순회 .
우편 주문 순회
이 기술은 '왼쪽-오른쪽 루트' 정책을 따릅니다. 이는 루트 노드의 첫 번째 왼쪽 하위 트리를 순회한 후 오른쪽 하위 트리를 재귀적으로 순회하고 마지막으로 루트 노드를 순회하는 것을 의미합니다. 루트 노드가 왼쪽 및 오른쪽 하위 트리 이후(또는 포스트)를 순회하므로 이를 후위 순회라고 합니다.
따라서 후위 순회에서 각 노드는 두 하위 트리 모두 다음에 방문됩니다.
후위순회 애플리케이션에는 다음이 포함됩니다.
- 트리를 삭제하는 데 사용됩니다.
- 표현식 트리의 후위 표현식을 가져오는 데에도 사용할 수 있습니다.
연산
Until all nodes of the tree are not visited Step 1 - Traverse the left subtree recursively. Step 2 - Traverse the right subtree recursively. Step 3 - Visit the root node.
예
이제 후위 순회 기법의 예를 살펴보겠습니다.
이제 위의 트리에 후위순회 적용을 시작합니다. 먼저 후위순으로 순회할 왼쪽 하위 트리 B를 순회합니다. 그런 다음 오른쪽 하위 트리를 탐색합니다. 씨 후순으로. 그리고 마지막으로 위 트리의 루트 노드, 즉 ㅏ , 통과됩니다.
따라서 왼쪽 하위 트리 B의 경우 먼저 왼쪽 하위 트리 디 통과됩니다. 노드 이후 디 자식이 없으면 오른쪽 하위 트리를 탐색합니다. 그리고 . E 노드에도 자식이 없으므로 루트 노드로 이동 비. 노드를 순회한 후 비, 루트 노드 A의 왼쪽 하위 트리 순회가 완료됩니다.
이제 루트 노드 A의 오른쪽 하위 트리인 C를 향해 이동합니다. 따라서 오른쪽 하위 트리 C의 경우 먼저 왼쪽 하위 트리입니다. 에프 통과됩니다. 노드 이후 에프 자식이 없으면 오른쪽 하위 트리를 탐색합니다. G . 노드 G에도 자식이 없으므로 마지막으로 오른쪽 하위 트리의 루트 노드, 즉 씨, 통과됩니다. 루트 노드 A의 오른쪽 하위 트리 순회가 완료됩니다.
마지막으로 주어진 트리의 루트 노드를 탐색합니다. 즉, ㅏ . 루트 노드를 순회한 후 해당 트리의 후위 순회가 완료됩니다.
따라서 트리의 모든 노드를 순회합니다. 따라서 위 트리의 후위순회 결과는 다음과 같습니다.
D → E → B → F → G → C → A
데이터 구조의 후위 순회에 대해 자세히 알아보려면 링크를 따라가세요. 우편 주문 순회 .
중위순회
이 기술은 '왼쪽 루트 오른쪽' 정책을 따릅니다. 이는 해당 루트 노드를 순회한 후 첫 번째 왼쪽 하위 트리를 방문하고 마지막으로 오른쪽 하위 트리를 순회한다는 의미입니다. 루트 노드가 왼쪽 하위 트리와 오른쪽 하위 트리 사이를 순회하므로 이를 중위 순회라고 합니다.
따라서 중위 순회에서는 각 노드가 하위 트리 사이에서 방문됩니다.
중위 순회 애플리케이션에는 다음이 포함됩니다.
stlc
- BST 노드를 오름차순으로 가져오는 데 사용됩니다.
- 표현식 트리의 접두사 표현식을 가져오는 데에도 사용할 수 있습니다.
연산
Until all nodes of the tree are not visited Step 1 - Traverse the left subtree recursively. Step 2 - Visit the root node. Step 3 - Traverse the right subtree recursively.
예
이제 중위 순회 기법의 예를 살펴보겠습니다.
이제 위의 트리에 중위 순회를 적용해 보세요. 먼저 왼쪽 하위 트리를 순회합니다. 비 순서대로 통과됩니다. 그 후 루트 노드를 순회합니다. ㅏ . 그리고 마지막으로 오른쪽 하위 트리 씨 순서대로 통과됩니다.
따라서 왼쪽 하위 트리의 경우 비 , 먼저 왼쪽 하위 트리 디 통과됩니다. 노드 이후 디 자식이 없으므로 순회한 후 노드 비 탐색되고 마지막으로 노드 B의 오른쪽 하위 트리, 즉 그리고 , 통과됩니다. 노드 E에는 자식도 없습니다. 따라서 루트 노드 A의 왼쪽 하위 트리 순회가 완료됩니다.
그 후, 주어진 트리의 루트 노드를 탐색합니다. 즉, ㅏ .
마지막으로 루트 노드 A의 오른쪽 하위 트리인 C를 향해 이동합니다. 따라서 오른쪽 하위 트리 C의 경우; 첫째, 왼쪽 하위 트리 에프 통과됩니다. 노드 이후 에프 자식 노드가 없습니다. 씨 탐색되고 마지막으로 노드 C의 오른쪽 하위 트리, 즉 G , 통과됩니다. 노드 G에는 자식도 없습니다. 따라서 루트 노드 A의 오른쪽 하위 트리 순회가 완료됩니다.
트리의 모든 노드를 순회하면 해당 트리의 중위 순회가 완료됩니다. 위 트리의 중위 순회 출력은 다음과 같습니다.
D → B → E → A → F → C → G
jfx 자바 튜토리얼
데이터 구조의 중위 순회에 대해 자세히 알아보려면 링크를 따라가세요. 중위순회 .
트리 순회 기술의 복잡성
위에서 논의한 트리 순회 기술의 시간 복잡도는 다음과 같습니다. 에) , 어디 'N' 이진 트리의 크기입니다.
위에서 논의한 트리 순회 기술의 공간 복잡도는 다음과 같습니다. 오(1) 함수 호출의 스택 크기를 고려하지 않는 경우. 그렇지 않으면 이러한 기술의 공간 복잡도는 다음과 같습니다. 오) , 어디 '시간' 나무의 높이입니다.
트리 순회 구현
이제 다양한 프로그래밍 언어를 사용하여 위에서 논의한 기술을 구현하는 방법을 살펴보겠습니다.
프로그램: 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 preorder*/ void traversePreorder(struct node* root) { if (root == NULL) return; printf(' %d ', root->element); traversePreorder(root->left); traversePreorder(root->right); } /*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); } /*function to traverse the nodes of binary tree in postorder*/ void traversePostorder(struct node* root) { if (root == NULL) return; traversePostorder(root->left); traversePostorder(root->right); printf(' %d ', root->element); } int main() { struct node* root = createNode(36); root->left = createNode(26); root->right = createNode(46); root->left->left = createNode(21); root->left->right = createNode(31); root->left->left->left = createNode(11); root->left->left->right = createNode(24); root->right->left = createNode(41); root->right->right = createNode(56); root->right->right->left = createNode(51); root->right->right->right = createNode(66); printf('
The Preorder traversal of given binary tree is -
'); traversePreorder(root); printf('
The Inorder traversal of given binary tree is -
'); traverseInorder(root); printf('
The Postorder traversal of given binary tree is -
'); traversePostorder(root); return 0; } 산출
프로그램: C#에서 트리 순회 기술을 구현하는 프로그램을 작성합니다.
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 traversePreorder(Node node) { if (node == null) return; Console.Write(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); Console.Write(node.value + ' '); traverseInorder(node.right); } void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); Console.Write(node.value + ' '); } void traversePreorder() { traversePreorder(root); } void traverseInorder() { traverseInorder(root); } void traversePostorder() { traversePostorder(root); } static void Main() { BinaryTree bt = new BinaryTree(); bt.root = new Node(37); bt.root.left = new Node(27); bt.root.right = new Node(47); bt.root.left.left = new Node(22); bt.root.left.right = new Node(32); bt.root.left.left.left = new Node(12); bt.root.left.left.right = new Node(25); bt.root.right.left = new Node(42); bt.root.right.right = new Node(57); bt.root.right.right.left = new Node(52); bt.root.right.right.right = new Node(67); Console.WriteLine('The Preorder traversal of given binary tree is - '); bt.traversePreorder(); Console.WriteLine(); Console.WriteLine('The Inorder traversal of given binary tree is - '); bt.traverseInorder(); Console.WriteLine(); Console.WriteLine('The Postorder traversal of given binary tree is - '); bt.traversePostorder(); } } 산출
프로그램: 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 preorder*/ void traversePreorder(struct node* root) { if (root == NULL) return; cout<<' '<element<left); traversepreorder(root->right); } /*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); } *function to traverse the nodes of binary tree in postorder* void traversepostorder(struct node* root) { if (root="=" null) return; traversepostorder(root->left); traversePostorder(root->right); cout<<' '<element<left="createNode(28);" root->right = createNode(48); root->left->left = createNode(23); root->left->right = createNode(33); root->left->left->left = createNode(13); root->left->left->right = createNode(26); root->right->left = createNode(43); root->right->right = createNode(58); root->right->right->left = createNode(53); root->right->right->right = createNode(68); cout<<'
the preorder traversal of given binary tree is -
'; traversepreorder(root); cout<<'
inorder traverseinorder(root); postorder traversepostorder(root); return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/17/tree-traversal-inorder-6.webp" alt="Tree Traversal"> <p> <strong>Program:</strong> Write a program to implement tree traversal techniques in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class Tree { Node root; /* root of the tree */ Tree() { root = null; } /*function to print the nodes of given binary in Preorder*/ void traversePreorder(Node node) { if (node == null) return; System.out.print(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } /*function to print the nodes of given binary in Inorder*/ void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); System.out.print(node.value + ' '); traverseInorder(node.right); } /*function to print the nodes of given binary in Postorder*/ void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); System.out.print(node.value + ' '); } void traversePreorder() { traversePreorder(root); } void traverseInorder() { traverseInorder(root); } void traversePostorder() { traversePostorder(root); } public static void main(String args[]) { Tree pt = new Tree(); pt.root = new Node(36); pt.root.left = new Node(26); pt.root.right = new Node(46); pt.root.left.left = new Node(21); pt.root.left.right = new Node(31); pt.root.left.left.left = new Node(11); pt.root.left.left.right = new Node(24); pt.root.right.left = new Node(41); pt.root.right.right = new Node(56); pt.root.right.right.left = new Node(51); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println('The Preorder traversal of given binary tree is - '); pt.traversePreorder(); System.out.println('
'); System.out.println('The Inorder traversal of given binary tree is - '); pt.traverseInorder(); System.out.println('
'); System.out.println('The Postorder traversal of given binary tree is - '); pt.traversePostorder(); System.out.println(); } } </pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/17/tree-traversal-inorder-7.webp" alt="Tree Traversal"> <h2>Conclusion</h2> <p>In this article, we have discussed the different types of tree traversal techniques: preorder traversal, inorder traversal, and postorder traversal. We have seen these techniques along with algorithm, example, complexity, and implementation in C, C++, C#, and java.</p> <p>So, that's all about the article. Hope it will be helpful and informative to you.</p> <hr></'
></'></'></'> 산출
위 코드를 실행한 후 출력은 다음과 같습니다.
결론
이 기사에서는 다양한 유형의 트리 순회 기술인 선순 순회, 중순 순회, 후순 순회에 대해 설명했습니다. 우리는 C, C++, C# 및 Java의 알고리즘, 예제, 복잡성 및 구현과 함께 이러한 기술을 살펴보았습니다.
이것이 기사의 전부입니다. 여러분에게 도움이 되고 유익한 정보가 되기를 바랍니다.