이번 글에서는 데이터 구조의 후위 순회(postorder traversal)에 대해 논의하겠습니다.
스택, 배열, 큐 등과 같은 선형 데이터 구조에는 데이터를 탐색하는 한 가지 방법만 있습니다. 그러나 다음과 같은 계층적 데이터 구조에서는 나무 , 데이터를 탐색하는 방법에는 여러 가지가 있습니다. 따라서 여기서는 트리 데이터 구조를 순회하는 또 다른 방법, 즉 우편 주문 순회 . 후위 순회는 트리의 노드를 방문하는 데 사용되는 순회 기술 중 하나입니다. 원칙을 따릅니다. LRN(왼쪽-오른쪽 노드) . 후위 순회는 트리의 후위 표현식을 얻는 데 사용됩니다.
후위 순회를 수행하는 데는 다음 단계가 사용됩니다.
- postorder 함수를 재귀적으로 호출하여 왼쪽 하위 트리를 탐색합니다.
- postorder 함수를 재귀적으로 호출하여 오른쪽 하위 트리를 탐색합니다.
- 현재 노드의 데이터 부분에 액세스합니다.
사후 주문 순회 기술은 다음과 같습니다. 왼쪽 오른쪽 루트 정책. 여기서 Left Right Root는 루트 노드의 왼쪽 하위 트리를 먼저 순회한 다음 오른쪽 하위 트리를 순회하고 마지막으로 루트 노드를 순회한다는 의미입니다. 여기서 Postorder 이름 자체는 트리의 루트 노드가 마침내 통과될 것임을 암시합니다.
자바 문자열을 배열로
연산
이제 후위 순회 알고리즘을 살펴보겠습니다.
Step 1: Repeat Steps 2 to 4 while TREE != NULL Step 2: POSTORDER(TREE -> LEFT) Step 3: POSTORDER(TREE -> RIGHT) Step 4: Write TREE -> DATA [END OF LOOP] Step 5: END
우편 주문 순회 예
이제 후위 순회(postorder traversal)의 예를 살펴보겠습니다. 예제를 사용하면 후주문 순회 과정을 더 쉽게 이해할 수 있습니다.
노란색으로 표시된 노드는 아직 방문하지 않았습니다. 이제 후위 순회를 사용하여 위 트리의 노드를 순회하겠습니다.
- 여기서 40은 루트 노드입니다. 먼저 40의 왼쪽 하위 트리, 즉 30을 방문합니다. 노드 30도 후순으로 순회합니다. 25는 30의 왼쪽 서브트리이므로 후위순으로도 순회한다. 그러면 15는 25의 왼쪽 하위 트리입니다. 그러나 15에는 하위 트리가 없으므로 인쇄 15 25의 오른쪽 하위 트리를 향해 이동합니다.
- 28은 25의 오른쪽 하위 트리이고 자식이 없습니다. 그래서, 인쇄 28 .
- 지금, 인쇄 25 , 그리고 25 은 끝났어.
- 다음으로, 30의 오른쪽 하위 트리를 향해 이동합니다. 35는 30의 오른쪽 하위 트리이고 자식이 없습니다. 그래서, 인쇄 35 .
- 이후, 30을 인쇄하다 , 그리고 30 은 끝났어. 따라서 주어진 이진 트리의 왼쪽 하위 트리를 탐색합니다.
- 이제 40의 오른쪽 하위 트리인 50을 향해 이동하면 역시 후순으로 순회하게 됩니다. 45는 50의 왼쪽 하위 트리이며 자식이 없습니다. 그래서, 인쇄 45 50의 오른쪽 하위 트리를 향해 이동합니다.
- 60은 50의 오른쪽 하위 트리이며 역시 후순으로 탐색됩니다. 55는 자식이 없는 60의 왼쪽 하위 트리입니다. 그래서, 인쇄 55 .
- 지금, 70을 인쇄하고, 이는 60의 오른쪽 하위 트리입니다.
- 지금, 60을 인쇄하고, 60에 대한 사후 주문 순회가 완료됩니다.
- 지금, 50을 인쇄하고, 50에 대한 사후 주문 순회가 완료됩니다.
- 마침내, 40을 인쇄하고, 이는 주어진 이진 트리의 루트 노드이고 노드 40에 대한 사후 순서 탐색이 완료됩니다.
주문 후 순회 후 얻을 수 있는 최종 출력은 다음과 같습니다.
자바 while 조건
{15, 28, 25, 35, 30, 45, 55, 70, 60, 50, 40}
우편 주문 탐색의 복잡성
후순위 탐색의 시간복잡도는 다음과 같습니다. 에) , 여기서 'n'은 이진 트리의 크기입니다.
반면, 후위 순회(postorder traversal)의 공간 복잡도는 다음과 같습니다. 오(1) , 함수 호출의 스택 크기를 고려하지 않는 경우. 그렇지 않으면 후위 순회(postorder traversal)의 공간 복잡도는 다음과 같습니다. 오) , 여기서 'h'는 트리의 높이입니다.
우편 주문 순회 구현
이제 다양한 프로그래밍 언어에서 후위순회 구현을 살펴보겠습니다.
프로그램: C 언어로 후위순회를 구현하는 프로그램을 작성하세요.
리틱 로샨 나이
#include #include struct node { s 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 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(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 Postorder traversal of given binary tree is -
'); traversePostorder(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 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 postorder traversal of given binary tree is -
'; traversepostorder(root); return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/85/postorder-traversal-14.webp" alt="Postorder Traversal"> <p> <strong>Program:</strong> Write a program to implement postorder 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 traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); Console.Write(node.value + ' '); } 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 Postorder traversal of given binary tree is - '); bt.traversePostorder(); } } </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/85/postorder-traversal-15.webp" alt="Postorder Traversal"> <p> <strong>Program:</strong> Write a program to implement postorder traversal in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PostorderTraversal { Node root; PostorderTraversal() { root = null; } void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); System.out.print(node.value + ' '); } void traversePostorder() { traversePostorder(root); } public static void main(String args[]) { PostorderTraversal pt = new PostorderTraversal(); 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 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/85/postorder-traversal-16.webp" alt="Postorder Traversal"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></'
></'> 산출
setinterval 자바스크립트
위 코드를 실행한 후 출력은 다음과 같습니다.
프로그램: Java에서 후위순회를 구현하는 프로그램을 작성하세요.
class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PostorderTraversal { Node root; PostorderTraversal() { root = null; } void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); System.out.print(node.value + ' '); } void traversePostorder() { traversePostorder(root); } public static void main(String args[]) { PostorderTraversal pt = new PostorderTraversal(); 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 Postorder traversal of given binary tree is - '); pt.traversePostorder(); System.out.println(); } } 산출
위 코드를 실행한 후 출력은 다음과 같습니다.
이것이 기사의 전부입니다. 이 기사가 귀하에게 도움이 되고 유익한 정보가 되기를 바랍니다.