[c] 이진트리/트리 순회법 코드(전위/중위/후위)

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

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

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

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