Contents

조회 수 20895 댓글 5
Atachment
첨부 '9'
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄

이진트리(BinaryTree)
 - 일반적인 트리는 한 노드가 N개의 자식을 가질 수 있지만 이진트리의 경우 한 노드가 최대 2개의 자식만 가질 수 있다. 
 - 다양한 분야에 활용되는 자료구조이다. 수식을 트리 형태로 표현하여 계산하게 하는 수식 이진 트리(Expression Binary Tree),
   아주 빠른 데이터 검색을 가능케 하는 이진 탐색 트리(Binary Search Tree) 등등.
 - 이진트리의 종류 : 포화 이진 트리(Full Binary Tree), 완전 이진 트리(Complete Binary Tree),
                            높이 균형 트리(Height Balanced Tree), 완전 높이 균형 트리(Completely Height Balanced Tree)

tree01.png



포화 이진 트리(Full Binary Tree)
 - 모든 레벨의 노드가 꽉 차있는 이진 트리.
 - 단말 노드를 제외한 모든 노드의 차수가 2인 형태를 말한다.

tree02.png



완전 이진 트리(Complete Binary Tree)
 - 단말 노드들이 트리의 왼쪽부터 차곡차곡 채워진 형태. 
 - 무조건 왼쪽부터 채워져 있어야 한다.(왼쪽 하위 트리 중 하나라도 비워져있다면 해당 안됨)

tree03.png




트리 순회법
 - 트리 순회 방법에는 3가지가 있다.
 - 전위 순회(Preorder Traversal), 중위 순회(Inorder Traversal), 후위 순회(Postorder Traversal) 


전위 순회법(Preorder Traversal)
 1. 루트 노드부터 시작해서 아래로 내려 오면서
 2. 왼쪽 하위 트리를 방문하고 왼쪽 하위 트리의 방문이 끝나면
 3. 오른쪽 하위 트리를 방문하는 방식 

tree04.png



중위 순회법(Inorder Traversal)
 - 트리는 하위 트리의 집합이라고 할 수 있고 하위 트리 역시 또 다른 하위 트리의 집합이라고 할  수 있다.
 - 따라서 아래와 같은 방법으로 탐색할 수 있다.
 1. 왼쪽 하위 트리부터 시작해서
 2. 루트를 거쳐
 3. 오른쪽 하위 트리를 방문하는 방법

tree05.png

 - 응용 사례 : 수식 트리(Expression Tree), 중위 표기식
 - (1 * 2) + (7 - 8)을 수식 트리로 표현하면 다음 그림과 같이 나타낼 수 있다.

tree06.png



후위 순회법(Postorder Traversal)
 - 전위 순회의 반대
 1. 왼쪽 하위 트리부터 시작해서
 2. 오른쪽 형제 노드를 방문 후
 3. 루트 노드를 방문하는 방법.

tree07.png

 - 응용 사례 : 후위 표기식. 후위 순회법을 통해 출력되는 노드를 살펴보면 후위 표기식으로 나타난다.
 - 1 2 * 7 8 - +


tree09.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);
}

tree10.png




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


?

List of Articles
번호 분류 제목 글쓴이 날짜 조회 수
1173 Develop [ios] 아이폰용 앱 오픈 소스들 hooni 2013.04.23 464972
1172 Develop [ios] 언어, 지역, 국가 설정 가져오기 hooni 2014.05.12 268576
1171 Develop 자주 쓰는 Docker 명령어 alias hooni 2020.01.10 267055
1170 Etc 베지어 곡선 (Bezier curve) file hooni 2013.08.18 219312
1169 Develop [ios] Start developing your navigation app for CarPlay without enrollment file hooni 2020.02.22 124370
1168 Develop [android] 만화 어플 소스코드 file hooni 2013.04.23 92832
1167 Develop 레고 마인드스톰 NXT 수도쿠, 큐브 소스코드.. 20 file hooni 2013.04.23 81369
1166 Algorithm 디피헬만(Diffie-Hellman) 초간단 개념.. hooni 2013.04.23 81003
1165 Develop [c#] Hashtable <-> Json (dll 포함) file hooni 2013.04.23 80644
1164 Develop [C#] MD5, SHA1 해시 & 인코딩 hooni 2013.04.23 77849
1163 Develop [android] 점심 해결 앱 소스 코드 ㅋㅋ file hooni 2013.04.23 76390
1162 PPT [android] XML파서(XMLParser)의 종류와 성능 비교에 대한 발표 자료 file hooni 2013.04.23 75631
Board Pagination Prev 1 2 3 4 5 6 7 8 9 10 ... 98 Next
/ 98