자료구조 - 트리의 순회

트리의 순회 방법은 주로 네 가지가 있습니다.

전위 순회, 중위 순회, 후위 순회, 레벨 순회가 있습니다.

 

 

[전위 순회(Preorder Traversal)]

전위 순회는 "루트 -> 왼쪽 -> 오른쪽" 순서로 노드를 방문합니다.

알고리즘:
1. 현재 노드를 방문한다.
2. 왼쪽 서브트리를 전위 순회한다.
3. 오른쪽 서브트리를 전위 순회한다.

 

 

전위 순회 구현

#include <iostream>
using namespace std;

// 노드 구조 정의
struct TreeNode 
{
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) 
    {
        data = val;
        left = nullptr;
        right = nullptr;
    }
};

// 이진 트리 클래스 정의
class BinaryTree 
{
    public:
        TreeNode* root;

        BinaryTree() 
        {
            root = nullptr;
        }

        void insert(int value) 
        {
            if (root == nullptr)
            {
                root = new TreeNode(value);
           } 
            else 
            {
                insertHelper(root, value);
            }
        }

        void insertHelper(TreeNode* node, int value) 
        {
            if (value < node->data) 
            {
                if (node->left == nullptr)
                {
                    node->left = new TreeNode(value);
                }
                else 
                {
                    insertHelper(node->left, value);
                }
            }
            else 
            {
                if (node->right == nullptr)
                {
                    node->right = new TreeNode(value);
                } 
                else 
                {
                    insertHelper(node->right, value);
                }
            }
        }

       // 전위 순회 메서드
        void preorder(TreeNode* node) 
        {
            if (node == nullptr) return;
            cout << node->data << " ";  // 현재 노드 방문
            preorder(node->left);       // 왼쪽 서브트리 전위 순회
            preorder(node->right);      // 오른쪽 서브트리 전위 순회
        }

        void displayPreorder()
        {
            preorder(root);
            cout << endl;
        }
};

int main() 
{
    BinaryTree bt;
    bt.insert(5);
    bt.insert(3);
    bt.insert(7);
    bt.insert(2);
    bt.insert(4);
    bt.insert(6);
    bt.insert(8);

    // 전위 순회 출력
    cout << "Preorder Traversal: ";
    bt.displayPreorder();  // 출력: 5 3 2 4 7 6 8

    return 0;
}

 

 

 

 

 

[중위 순회 (Inorder Traversal)]

중위 순회는 "왼쪽 -> 루트 -> 오른쪽" 순서로 노드를 방문합니다.

알고리즘:
1. 왼쪽 서브트리를 중위 순회한다.
2. 현재 노드를 방문한다.
3. 오른쪽 서브트리를 중위 순회한다.

 

 

중위 순회 구현

#include <iostream>
using namespace std;

// 노드 구조 정의
struct TreeNode 
{
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) 
    {
        data = val;
        left = nullptr;
        right = nullptr;
    }
};

// 이진 트리 클래스 정의
class BinaryTree 
{
    public:
        TreeNode* root;

        BinaryTree() 
        {
            root = nullptr;
        }

        void insert(int value) 
        {
            if (root == nullptr) 
            {
                root = new TreeNode(value);
            }
            else 
            {
                insertHelper(root, value);
            }
        }

        void insertHelper(TreeNode* node, int value) 
        {
            if (value < node->data)
            {
                if (node->left == nullptr) 
                {
                    node->left = new TreeNode(value);
                } 
                else
                {
                    insertHelper(node->left, value);
                }
            }
            else
            {
                if (node->right == nullptr) 
                {
                    node->right = new TreeNode(value);
                }
                else
                {
                    insertHelper(node->right, value);
                }
            }
        }

        // 중위 순회 메서드
        void inorder(TreeNode* node) 
        {
            if (node == nullptr) return;
            inorder(node->left);        // 왼쪽 서브트리 중위 순회
            cout << node->data << " ";  // 현재 노드 방문
            inorder(node->right);       // 오른쪽 서브트리 중위 순회
        }

        void displayInorder()
        {
            inorder(root);
            cout << endl;
        }
};

int main() 
{
    BinaryTree bt;
    bt.insert(5);
    bt.insert(3);
    bt.insert(7);
    bt.insert(2);
    bt.insert(4);
    bt.insert(6);
    bt.insert(8);

    // 중위 순회 출력
    cout << "Inorder Traversal: ";
    bt.displayInorder();  // 출력: 2 3 4 5 6 7 8

    return 0;
}

 

 

 

 

[후위 순회(Postorder Traversal)]

후위 순회는 "왼쪽 -> 오른쪽 -> 루트" 순서로 노드를 방문합니다.

알고리즘:
1. 왼쪽 서브트리를 후위 순회한다.
2. 오른쪽 서브트리를 후위 순회한다.
3. 현재 노드를 방문한다.

 

 

후위 순회 구현

#include <iostream>
using namespace std;

// 노드 구조 정의
struct TreeNode 

    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) 
    {
        data = val;
        left = nullptr;
        right = nullptr;
    }
};

// 이진 트리 클래스 정의
class BinaryTree 
{
    public:
        TreeNode* root;

        BinaryTree() 
        {
            root = nullptr;
        }

        void insert(int value)
        {
            if (root == nullptr) 
            {
                root = new TreeNode(value);
            } 
            else 
            {
                insertHelper(root, value);
            }
        }

        void insertHelper(TreeNode* node, int value)
        {
            if (value < node->data) 
            {
                if (node->left == nullptr) 
                {
                    node->left = new TreeNode(value);
                }
                else
                {
                    insertHelper(node->left, value);
                }
            }
            else
            {
                if (node->right == nullptr) 
                {
                    node->right = new TreeNode(value);
                } 
                else 
                {
                    insertHelper(node->right, value);
                }
            }
        }

        // 후위 순회 메서드
        void postorder(TreeNode* node)
        {
            if (node == nullptr) return;
            postorder(node->left);      // 왼쪽 서브트리 후위 순회
            postorder(node->right);     // 오른쪽 서브트리 후위 순회
            cout << node->data << " ";  // 현재 노드 방문
        }

        void displayPostorder() 
        {
            postorder(root);
            cout << endl;
        }
};

int main() 
{
    BinaryTree bt;
    bt.insert(5);
    bt.insert(3);
    bt.insert(7);
    bt.insert(2);
    bt.insert(4);
    bt.insert(6);
    bt.insert(8);

    // 후위 순회 출력
    cout << "Postorder Traversal: ";
    bt.displayPostorder();  // 출력: 2 4 3 6 8 7 5

    return 0;
}

 

 

 

[레벨 순회(Level Order Traversal)]

레벨 순회는 트리의 노드를 레벨별로 방문합니다. 큐를 사용하여 구현할 수 있습니다.

 

위와 같은 순서로 노드를 검사합니다.

알고리즘:
1. 루트 노드를 큐에 삽입한다.
2. 큐가 비어있지 않은 동안 다음을 반복한다:
    2-1. 큐에서 노드를 꺼내 방문한다.
    2-2. 그 노드의 왼쪽 자식을 큐에 삽입한다.
    2-3. 그 노드의 오른쪽 자식을 큐에 삽입한다.

 

 

레벨 순회 구현

#include <iostream>
#include <queue>
using namespace std;

// 노드 구조 정의
struct TreeNode 
{
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val)
    {
        data = val;
        left = nullptr;
        right = nullptr;
    }
};

// 이진 트리 클래스 정의
class BinaryTree
{
    public:
        TreeNode* root;

        BinaryTree()
        {
            root = nullptr;
        }

        void insert(int value) 
        {
            if (root == nullptr) 
            {
                root = new TreeNode(value);
            } 
            else 
            {
                insertHelper(root, value);
            }
        }

        void insertHelper(TreeNode* node, int value) 
        {
            if (value < node->data) 
            {
                if (node->left == nullptr)
                {
                    node->left = new TreeNode(value);
                }
                else 
                {
                    insertHelper(node->left, value);
                }
            } 
            else 
            {
                if (node->right == nullptr) 
                {
                    node->right = new TreeNode(value);
                }
                else 
                {
                    insertHelper(node->right, value);
                }
            }
        }

        // 레벨 순회 메서드
        void levelOrder() 
        {
            if (root == nullptr) return;
            queue<TreeNode*> q;
            q.push(root);
            while (!q.empty())
            {
                TreeNode* current = q.front();
                q.pop();
                cout << current->data << " ";  // 현재 노드 방문
                if (current->left != nullptr) 
                {
                    q.push(current->left);    // 왼쪽 자식을 큐에 삽입
                }
                if (current->right != nullptr)
                {
                    q.push(current->right);   // 오른쪽 자식을 큐에 삽입
                }
            }
            cout << endl;
        }
};

int main()
{
    BinaryTree bt;
    bt.insert(5);
    bt.insert(3);
    bt.insert(7);
    bt.insert(2);
    bt.insert(4);
    bt.insert(6);
    bt.insert(8);

    // 레벨 순회 출력
    cout << "Level Order Traversal: ";
    bt.levelOrder();  // 출력: 5 3 7 2 4 6 8

    return 0;
}

 

 

 

 

 

[트리의 응용 : 수식 트리 처리]

수식	a + b	a - (b x c)	(a < b) or (c < d)
전위순회	+ a b	- a x b c	or < a b < c d
중위순회	a + b	a - (b x c)	(a < b) or (c < d)
후위순회	a b +	a b c x -	a b < c d < or

 

 

수식 트리 처리 코드

    #include <iostream>
#include <stack>
#include <string>
using namespace std;

// 수식 트리 노드 구조체
struct TreeNode 
{
    string data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(string val)
    {
        data = val;
        left = nullptr;
        right = nullptr;
    }
};

// 수식 트리 클래스
class ExpressionTree 
{
    private:
        TreeNode* root;
    
        // 수식 토큰 분리 함수
        vector<string> tokenize(string expression)
        {
            vector<string> tokens;
            string token;
            for (char& c : expression) 
            {
                if (c == ' ')
                {
                    if (!token.empty())
                    {
                        tokens.push_back(token);
                        token.clear();
                    }
                } else
                {
                    token += c;
                }
            }
            if (!token.empty()) 
            {
                tokens.push_back(token);
            }
            return tokens;
        }

        // 연산자 우선순위 확인 함수
        int precedence(string op) 
        {
            if (op == "+" || op == "-") return 1;
            if (op == "*" || op == "/") return 2;
            return 0;
        }
    
        // 수식 토큰을 이용하여 수식 트리 생성 함수 (재귀적)
        TreeNode* buildTree(vector<string>& tokens, int start, int end)
        {
            if (start > end) return nullptr;
    
            int minPrecedence = INT_MAX;
            int minPrecedenceIndex = -1;
    
            int parenthesesCount = 0;
            for (int i = start; i <= end; ++i)
            {
                if (tokens[i] == "(") 
                {
                    parenthesesCount++;
                } 
                else if (tokens[i] == ")") 
                {
                    parenthesesCount--;
                }
    
                if (parenthesesCount == 0 && (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/"))
                {
                    int currPrecedence = precedence(tokens[i]);
                    if (currPrecedence <= minPrecedence)
                    {
                        minPrecedence = currPrecedence;
                        minPrecedenceIndex = i;
                    }
                }
            }
    
            if (minPrecedenceIndex != -1)
            {
                TreeNode* node = new TreeNode(tokens[minPrecedenceIndex]);
                node->left = buildTree(tokens, start, minPrecedenceIndex - 1);
                node->right = buildTree(tokens, minPrecedenceIndex + 1, end);
                return node;
            }
            else 
            {
                // 피연산자인 경우
                return new TreeNode(tokens[start]);
            }
        }
    
        // 후위 순회 함수 (재귀적)
        void postorderTraversal(TreeNode* node) 
        {
            if (node == nullptr) return;
            postorderTraversal(node->left);
            postorderTraversal(node->right);
            cout << node->data << " ";
        }

    public:
        ExpressionTree()
        {
            root = nullptr;
        }

        // 수식 트리 생성 함수
        void buildExpressionTree(string expression)
        {
            vector<string> tokens = tokenize(expression);
            root = buildTree(tokens, 0, tokens.size() - 1);
        }

        // 후위 표기법으로 수식 출력 함수
        void printPostorderExpression() 
        {
            postorderTraversal(root);
            cout << endl;
        }
};

int main() 
{
    string expression = "( A + B ) * ( C - D )";
    ExpressionTree et;
    et.buildExpressionTree(expression);
    cout << "Postfix Expression: ";
    et.printPostorderExpression();  // 출력: A B + C D - *
    return 0;
}