[c] 이진트리/트리 순회법 코드(전위/중위/후위)
Attachment '9' |
|
---|
이진트리(BinaryTree)
- 일반적인 트리는 한 노드가 N개의 자식을 가질 수 있지만 이진트리의 경우 한 노드가 최대 2개의 자식만 가질 수 있다.
- 다양한 분야에 활용되는 자료구조이다. 수식을 트리 형태로 표현하여 계산하게 하는 수식 이진 트리(Expression Binary Tree),
아주 빠른 데이터 검색을 가능케 하는 이진 탐색 트리(Binary Search Tree) 등등.
- 이진트리의 종류 : 포화 이진 트리(Full Binary Tree), 완전 이진 트리(Complete Binary Tree),
높이 균형 트리(Height Balanced Tree), 완전 높이 균형 트리(Completely Height Balanced Tree)
![tree01.png](https://www.hooni.net/xe/files/attach/images/207/487/066/83a2c76d9cb1901af3289476c7d6691d.png)
포화 이진 트리(Full Binary Tree)
- 모든 레벨의 노드가 꽉 차있는 이진 트리.
- 단말 노드를 제외한 모든 노드의 차수가 2인 형태를 말한다.
![tree02.png](https://www.hooni.net/xe/files/attach/images/207/487/066/4545da3753a2801f29ff5e5c2ad65e92.png)
완전 이진 트리(Complete Binary Tree)
- 단말 노드들이 트리의 왼쪽부터 차곡차곡 채워진 형태.
- 무조건 왼쪽부터 채워져 있어야 한다.(왼쪽 하위 트리 중 하나라도 비워져있다면 해당 안됨)
![tree03.png](https://www.hooni.net/xe/files/attach/images/207/487/066/f88f834ad6cf4573136b16621b6aac9f.png)
트리 순회법
- 트리 순회 방법에는 3가지가 있다.
- 전위 순회(Preorder Traversal), 중위 순회(Inorder Traversal), 후위 순회(Postorder Traversal)
전위 순회법(Preorder Traversal)
1. 루트 노드부터 시작해서 아래로 내려 오면서
2. 왼쪽 하위 트리를 방문하고 왼쪽 하위 트리의 방문이 끝나면
3. 오른쪽 하위 트리를 방문하는 방식
![tree04.png](https://www.hooni.net/xe/files/attach/images/207/487/066/298adc882d080e0825f112e13868ee34.png)
중위 순회법(Inorder Traversal)
- 트리는 하위 트리의 집합이라고 할 수 있고 하위 트리 역시 또 다른 하위 트리의 집합이라고 할 수 있다.
- 따라서 아래와 같은 방법으로 탐색할 수 있다.
1. 왼쪽 하위 트리부터 시작해서
2. 루트를 거쳐
3. 오른쪽 하위 트리를 방문하는 방법
![tree05.png](https://www.hooni.net/xe/files/attach/images/207/487/066/bca7a8d6cb5125e1a2c9489c2825e25f.png)
- 응용 사례 : 수식 트리(Expression Tree), 중위 표기식
- (1 * 2) + (7 - 8)을 수식 트리로 표현하면 다음 그림과 같이 나타낼 수 있다.
![tree06.png](https://www.hooni.net/xe/files/attach/images/207/487/066/653c0a508926eff5f331c344a87f0eea.png)
후위 순회법(Postorder Traversal)
- 전위 순회의 반대
1. 왼쪽 하위 트리부터 시작해서
2. 오른쪽 형제 노드를 방문 후
3. 루트 노드를 방문하는 방법.
![tree07.png](https://www.hooni.net/xe/files/attach/images/207/487/066/cc2da617be9fe8392ddbe6310f8385b9.png)
- 응용 사례 : 후위 표기식. 후위 순회법을 통해 출력되는 노드를 살펴보면 후위 표기식으로 나타난다.
- 1 2 * 7 8 - +
![tree09.png](https://www.hooni.net/xe/files/attach/images/207/487/066/9058f063830d596679059d693563e57a.png)
C로 구현한 이진트리/트리 순회법
BinaryTree.h
#ifndef BINARY_TREE_H #define BINARY_TREE_H #include <stdio.h> #include <stdlib.h> typedef char ElementType; typedef struct tagNode { struct tagNode* left; struct tagNode* right; ElementType data; } Node; Node* CreateNode(ElementType newData); void DestroyNode(Node* node); void DestroyTree(Node* root); void PreOrderPrintTree(Node* node); void InOrderPrintTree(Node* node); void PostOrderPrintTree(Node* node); #endif
BinaryTree.c
#include "BinaryTree.h" /* 노드 생성 */ Node* CreateNode(ElementType newData) { // 노드를 위한 메모리 할당 Node* newNode = (Node*) malloc(sizeof(Node)); newNode->left = NULL; newNode->right = NULL; newNode->data = newData; return newNode; } /* 노드 파괴 */ void DestroyNode(Node* node) { free(node); } /* 트리 파괴(후위 순회 활용) */ void DestroyTree(Node* root) { if(root == NULL) return; // 왼쪽 하위 트리 소멸 DestroyTree(root->left); // 오른쪽 하위 트리 소멸 DestroyTree(root->right); // 루트 노드 소멸 DestroyNode(root); } /* 전위 순회 */ void PreOrderPrintTree(Node* node) { if(node == NULL) return; // 부모 노드 출력 printf(" %c", node->data); // 왼쪽 하위 트리 출력 PreOrderPrintTree(node->left); // 오른쪽 하위 트리 출력 PreOrderPrintTree(node->right); } /* 중위 순회 */ void InOrderPrintTree(Node* node) { if(node == NULL) return; // 왼쪽 하위 트리 출력 InOrderPrintTree(node->left); // 부모 노드 출력 printf(" %c", node->data); // 오른쪽 하위 트리 출력 InOrderPrintTree(node->right); } /* 후위 순회 */ void PostOrderPrintTree(Node* node) { if(node == NULL) return; // 왼쪽 하위 트리 출력 PostOrderPrintTree(node->left); // 오른쪽 하위 트리 출력 PostOrderPrintTree(node->right); // 부모 노드 출력 printf(" %c", node->data); }
Test_BinaryTree.c
#include "BinaryTree.h" void main() { // 노드 생성 Node* A = CreateNode('A'); Node* B = CreateNode('B'); Node* C = CreateNode('C'); Node* D = CreateNode('D'); Node* E = CreateNode('E'); Node* F = CreateNode('F'); Node* G = CreateNode('G'); // 트리에 노드 추가 A->left = B; B->left = C; B->right = D; A->right = E; E->left = F; E->right = G; // 트리 출력 printf("PreOrder...\n"); PreOrderPrintTree(A); printf("\n\n"); printf("InOrder...\n"); InOrderPrintTree(A); printf("\n\n"); printf("PostOrder...\n"); PostOrderPrintTree(A); printf("\n"); // 소멸 DestroyTree(A); }
JAVA로 구현한 이진트리/트리 순회법
Node.java
public class Node { private char data; private Node left; private Node right; public Node(char data) { this.setData(data); } public void setData(char data) { this.data = data; } public char getData() { return data; } public void setLeft(Node left) { this.left = left; } public Node getLeft() { return left; } public void setRight(Node right) { this.right = right; } public Node getRight() { return right; } }
BinaryTree.java
public class BinaryTree { // 전위 순회 public static void preorderPrintTree(Node node) { if(node == null) return; // 부모 노드 출력 System.out.print(" " + node.getData()); // 왼쪽 하위 트리 출력 preorderPrintTree(node.getLeft()); // 오른쪽 하위 트리 출력 preorderPrintTree(node.getRight()); } // 중위 순회 public static void inorderPrintTree(Node node) { if(node == null) return; // 왼쪽 하위 트리 출력 inorderPrintTree(node.getLeft()); // 부모 노드 출력 System.out.print(" " + node.getData()); // 오른쪽 하위 트리 출력 inorderPrintTree(node.getRight()); } // 후위 순회 public static void postorderPrintTree(Node node) { if(node == null) return; // 왼쪽 하위 트리 출력 postorderPrintTree(node.getLeft()); // 오른쪽 하위 트리 출력 postorderPrintTree(node.getRight()); // 부모 노드 출력 System.out.print(" " + node.getData()); } }
Test_BinaryTree.java
public class Test_BinaryTree { public static void main(String[] args) { // 노드 생성 Node A = new Node('A'); Node B = new Node('B'); Node C = new Node('C'); Node D = new Node('D'); Node E = new Node('E'); Node F = new Node('F'); Node G = new Node('G'); // 트리에 노드 추가 A.setLeft(B); B.setLeft(C); B.setRight(D); A.setRight(E); E.setLeft(F); E.setRight(G); // 출력 System.out.println("Preorder..."); BinaryTree.preorderPrintTree(A); System.out.println("\n"); System.out.println("Inorder..."); BinaryTree.inorderPrintTree(A); System.out.println("\n"); System.out.println("Postorder..."); BinaryTree.postorderPrintTree(A); } }
결과)
Preorder...
A B C D E F G
Inorder...
C B D A F E G
Postorder...
C D B F G E A
[출처] http://warmz.tistory.com/619
No. | Category | Subject | Author | Date | Views |
---|---|---|---|---|---|
745 | Develop |
[php] 몽이가 준 ajax 채팅 소스 ㅋㅋ
![]() |
hooni | 2013.04.23 | 36212 |
744 | Develop |
[php] 메모장 - 웅지학원 ([c] mysql 백업프로그램 포함)
![]() |
hooni | 2003.04.23 | 7036 |
743 | Develop |
[php] 마시마로 캐릭터 방명록
![]() |
hooni | 2003.04.23 | 8277 |
742 | Develop | [php] 데이터를 엑셀,워드 형태로 변환할 때 헤더(ms-office) | hooni | 2013.04.23 | 7525 |
741 | Develop |
[php] 니우쪽지다.. 받아라~ ^^
![]() |
hooni | 2003.04.23 | 9874 |
740 | Develop |
[php] 논문 관리 프로그램.. ㅋㅋ
![]() |
hooni | 2013.04.23 | 7290 |
739 | Develop | [php] 날짜 정보 출력 (년,월,일,시,분,초) | hooni | 2013.04.23 | 10586 |
738 | Develop |
[php] 그래프 그리는 프로그램..
![]() |
hooni | 2013.04.23 | 8509 |
737 | Develop |
[php] XE에서 도메인 별로 광고 다르게 적용하기
![]() |
hooni | 2015.01.28 | 718 |
736 | Develop | [php] XE 에서 php 구문 사용하기 (XE 템플릿에서) | hooni | 2013.10.31 | 19546 |
735 | Develop |
[php] XE 스킨에서 특정 도메인 리다이렉션
![]() |
hooni | 2015.01.28 | 689 |
734 | Develop | [php] XE 관리자 IP대역 설정 오류 해결법 | hooni | 2014.02.10 | 10825 |
감사합니다
잘보고 가요