이 글에서는 데이터 구조의 선주문 순회에 대해 설명합니다. 스택, 배열, 큐 등과 같은 선형 데이터 구조에는 데이터를 탐색하는 한 가지 방법만 있습니다. 그러나 다음과 같은 계층적 데이터 구조에서는 나무 , 데이터를 탐색하는 방법에는 여러 가지가 있습니다.
선주문 순회에서는 먼저 루트 노드를 방문한 다음 왼쪽 하위 트리를 방문하고 그 후 오른쪽 하위 트리를 방문합니다. 선주문 순회 프로세스는 다음과 같이 나타낼 수 있습니다.
root → left → right
루트 노드는 선순 순회에서는 항상 가장 먼저 순회되고, 후순 순회에서는 마지막 항목이 됩니다. 선주문 순회는 트리의 접두사 표현식을 얻는 데 사용됩니다.
선주문 순회를 수행하는 단계는 다음과 같습니다.
- 먼저 루트 노드를 방문합니다.
- 그런 다음 왼쪽 하위 트리를 방문합니다.
- 마지막으로 오른쪽 하위 트리를 방문합니다.
선주문 순회 기술은 다음과 같습니다. 루트 왼쪽 오른쪽 정책. 사전 주문이라는 이름 자체는 루트 노드가 먼저 통과된다는 것을 암시합니다.
연산
이제 선주문 순회 알고리즘을 살펴보겠습니다.
Step 1: Repeat Steps 2 to 4 while TREE != NULL Step 2: Write TREE -> DATA Step 3: PREORDER(TREE -> LEFT) Step 4: PREORDER(TREE -> RIGHT) [END OF LOOP] Step 5: END
선주문 순회 예시
이제 선주문 탐색의 예를 살펴보겠습니다. 예시를 통해 선주문 순회 과정을 이해하는 것이 더 쉬울 것입니다.
노란색으로 표시된 노드는 아직 방문하지 않았습니다. 이제 선주문 순회를 사용하여 위 트리의 노드를 순회하겠습니다.
- 루트 노드 40부터 시작합니다. 먼저, 인쇄 40 그런 다음 왼쪽 하위 트리를 재귀적으로 탐색합니다.
- 이제 왼쪽 하위 트리로 이동합니다. 왼쪽 하위 트리의 경우 루트 노드는 30입니다. 30을 인쇄하세요 , 30의 왼쪽 하위 트리를 향해 이동합니다.
- 30의 왼쪽 하위 트리에는 요소 25가 있으므로 인쇄 25 , 25의 왼쪽 하위 트리를 탐색합니다.
- 25의 왼쪽 하위 트리에는 요소 15가 있고 15에는 하위 트리가 없습니다. 그래서, 인쇄 15 , 25의 오른쪽 하위 트리로 이동합니다.
- 25의 오른쪽 하위 트리에는 28개가 있고, 28에는 하위 트리가 없습니다. 그래서, 인쇄 28 , 30의 오른쪽 하위 트리로 이동합니다.
- 30개의 오른쪽 하위 트리에는 하위 트리가 없는 35개가 있습니다. 그래서 인쇄 35 , 40의 오른쪽 하위 트리를 탐색합니다.
- 40의 오른쪽 하위 트리에는 50이 있습니다. 50을 인쇄하세요 , 50의 왼쪽 하위 트리를 탐색합니다.
- 50의 왼쪽 하위 트리에는 자식이 없는 45개가 있습니다. 그래서, 인쇄 45 , 50의 오른쪽 하위 트리를 탐색합니다.
- 50의 오른쪽 하위 트리에는 60이 있습니다. 60을 인쇄하세요 60의 왼쪽 하위 트리를 탐색합니다.
- 60개의 왼쪽 하위 트리에는 자식이 없는 55개가 있습니다. 그래서, 인쇄 55 60의 오른쪽 하위 트리로 이동합니다.
- 60의 오른쪽 하위 트리에는 자식이 없는 70이 있습니다. 그래서, 70을 인쇄하다 프로세스를 중지합니다.
선주문 순회가 완료된 후 최종 출력은 다음과 같습니다.
40, 30, 25, 15, 28, 35, 50, 45, 60, 55, 70
선주문 순회 복잡성
선주문 탐색의 시간 복잡도는 다음과 같습니다. 에) , 여기서 'n'은 이진 트리의 크기입니다.
반면, 선주문 탐색의 공간 복잡도는 오(1) , 함수 호출의 스택 크기를 고려하지 않는 경우. 그렇지 않으면 선주문 탐색의 공간 복잡도는 다음과 같습니다. 오) , 여기서 '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 preorder*/ void traversePreorder(struct node* root) { if (root == NULL) return; printf(' %d ', root->element); traversePreorder(root->left); traversePreorder(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 Preorder traversal of given binary tree is -
'); traversePreorder(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 preorder*/ void traversePreorder(struct node* root) { if (root == NULL) return; cout<<' '<element<left); traversepreorder(root->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 preorder traversal of given binary tree is -
'; traversepreorder(root); return 0; } < 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/25/preorder-traversal-14.webp" alt="Preorder Traversal"> <p> <strong>Program:</strong> Write a program to implement preorder 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 traversePreorder(Node node) { if (node == null) return; Console.Write(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traversePreorder() { traversePreorder(root); } static void Main() { BinaryTree bt = new BinaryTree(); bt.root = new Node(38); bt.root.left = new Node(28); bt.root.right = new Node(48); bt.root.left.left = new Node(23); bt.root.left.right = new Node(33); bt.root.left.left.left = new Node(13); bt.root.left.left.right = new Node(26); bt.root.right.left = new Node(43); bt.root.right.right = new Node(58); bt.root.right.right.left = new Node(53); bt.root.right.right.right = new Node(68); Console.WriteLine('Preorder traversal of given binary tree is - '); bt.traversePreorder(); } } </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/25/preorder-traversal-15.webp" alt="Preorder Traversal"> <p> <strong>Program:</strong> Write a program to implement preorder traversal in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PreorderTraversal { Node root; PreorderTraversal() { root = null; } void traversePreorder(Node node) { if (node == null) return; System.out.print(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traversePreorder() { traversePreorder(root); } public static void main(String args[]) { PreorderTraversal pt = new PreorderTraversal(); pt.root = new Node(37); pt.root.left = new Node(27); pt.root.right = new Node(47); pt.root.left.left = new Node(22); pt.root.left.right = new Node(32); pt.root.left.left.left = new Node(12); pt.root.left.left.right = new Node(25); pt.root.right.left = new Node(42); pt.root.right.right = new Node(57); pt.root.right.right.left = new Node(52); pt.root.right.right.right = new Node(67); System.out.println(); System.out.println('Preorder traversal of given binary tree is - '); pt.traversePreorder(); 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/25/preorder-traversal-16.webp" alt="Preorder 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 PreorderTraversal { Node root; PreorderTraversal() { root = null; } void traversePreorder(Node node) { if (node == null) return; System.out.print(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traversePreorder() { traversePreorder(root); } public static void main(String args[]) { PreorderTraversal pt = new PreorderTraversal(); pt.root = new Node(37); pt.root.left = new Node(27); pt.root.right = new Node(47); pt.root.left.left = new Node(22); pt.root.left.right = new Node(32); pt.root.left.left.left = new Node(12); pt.root.left.left.right = new Node(25); pt.root.right.left = new Node(42); pt.root.right.right = new Node(57); pt.root.right.right.left = new Node(52); pt.root.right.right.right = new Node(67); System.out.println(); System.out.println('Preorder traversal of given binary tree is - '); pt.traversePreorder(); System.out.println(); } } 산출
위 코드를 실행한 후 출력은 다음과 같습니다.
이것이 기사의 전부입니다. 이 기사가 귀하에게 도움이 되고 유익한 정보가 되기를 바랍니다.