자료구조
자료구조 - 트리의 순회
tita
2024. 6. 9. 19:14
트리의 순회 방법은 주로 네 가지가 있습니다.
전위 순회, 중위 순회, 후위 순회, 레벨 순회가 있습니다.
[전위 순회(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;
}