4주차 1번 문제
📌문제1. 트리 순회하기
문제) 이진 트리를 입력받아 전위 순회, 중위 순회, 후위 순회한 결과를 출력하는 프로그램을 작성
입력) 첫째 줄에는 이진 트리의 노드의 개수 N(1 < N < 26)이 주어짐. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그 왼족 자식 노드, 오른쪽 자식 노드가 주어짐.노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 됨. 자식 노드가 없는 경우에는 . 으로 표현함.
출력) 첫째 줄에는 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력함. 각 줄에 N개의 알파벳을 공백없이 출력한다.
⭐ 필수 사전 작업
- BinaryNode 클래스 설계하기
- BinaryTree 클래스 설계하기
3. preorder, inorder, postorder 함수 정의하기
⭐ 메인 함수, 슈드코드
입력 데이터 선언 N,p,left,right -- 변수 선언
BinaryNode 벡터 선언
BinaryTree 선언
데이터 N 입력 -- 데이터 입력
N 크기의 BinaryNode* 벡터 공간 확보
N개의 노드, 왼쪽 자식 노드, 오른족 자식 노드 데이터 입력
N개 BinaryNode 생성
N개의 노드간 링크 연결
BinaryTree 생성
BinaryTree의 루트 생성
BinaryTree에 대해서
preorder traversal
inorder traversal
postorder traversal
✔️ solution
✅ BinaryNode,Tree 클래스 설계하기
#include <iostream>
#include <vector>
using namespace std;
class BinaryNode
{
public:
char data;
BinaryNode* left;
BinaryNode* right;
BinaryNode(char val = 0, BinaryNode* l = NULL, BinaryNode* r = NULL)
: data(val), left(l), right(r) { }
~BinaryNode() { }
void setData(char val) { data = val; }
void setLeft(BinaryNode* l) { left = l; }
void setRight(BinaryNode* r) { right = r; }
char getData() { return data; }
BinaryNode* getLeft() { return left; }
BinaryNode* getRight() { return right; }
bool isLeaf() { return left == NULL && right == NULL; }
};
class BinaryTree {
BinaryNode* root;
public:
BinaryTree() : root(NULL) { }
~BinaryTree() { }
void setRoot(BinaryNode* node) { root = node; }
BinaryNode* getRoot() { return root; }
bool isEmpty() { return root == NULL; }
void inorder(BinaryNode* node);
void preorder(BinaryNode* node);
void postorder(BinaryNode* node);
};
⭐ Tree Traversal 함수 정의하기 --> 암기
void
BinaryTree::inorder(BinaryNode* node) {
if (node != NULL) {
if (node->getLeft() != NULL) inorder(node->getLeft());
cout << node->getData();
if (node->getRight() != NULL) inorder(node->getRight());
}
}
void
BinaryTree::preorder(BinaryNode* node) {
if (node != NULL) {
cout << node->getData();
if (node->getLeft() != NULL) preorder(node->getLeft());
if (node->getRight() != NULL) preorder(node->getRight());
}
}
void
BinaryTree::postorder(BinaryNode* node) {
if (node != NULL) {
if (node->getLeft() != NULL) postorder(node->getLeft());
if (node->getRight() != NULL) postorder(node->getRight());
cout << node->getData();
}
}
✅ 메인 함수 설계
int main(){
int N;
char p,left,right;
BinaryTree* tree;
vector <BinaryNode*> node;
cin >> N;
node.resize(N);
// 일단 먼저 A부터 A+N까지 노드를 생성을 먼저 해놓고
// 그 이후에 링크를 이용해서 연결을 해야함
for(int i = 0 ; i < N ; i ++){
node[i] = new BinaryNode('A' + i);
}
for(int i = 0 ; i < N ; i ++){
cin >> p >> left >> right;
// 노드 연결하는 과정
if(left != '.') node[p - 'A']->setLeft(node[left - 'A']);
if(right != '.') node[p - 'A']->setRight(node[right - 'A']);
}
tree = new BinaryTree();
tree->setRoot(node[0]);
// BinaryNode* root = tree->getRoot();
tree->preorder(tree->getRoot());cout << endl;
tree->inorder(tree->getRoot());cout << endl;
tree->postorder(tree->getRoot());cout << endl;
return 0;
}⭐ 테스트 케이스
⚠️ 주의할 점
1. 일단 BinaryNode를 먼저 생성 후에 링크간 연결을 해줌 --> for문 두 번 분리해서 작성하기
: 먼저 노드를 다 생성해야 left,right 링크를 이용해서 연결 가능
2. 왜 BinaryTree* tree 포인터 변수로 선언했는지, 객체로 선언하면 안되는지
: BinaryTree tree; 객체로 생성가능 (대신 -> 를 .으로 수정)
3. char형, 알파벳을 인덱스로 바꿀 때, 알파벳 간의 차이로 구함 (ASCII 코드 사용)
4. 왜 root라고 변수를 선언하고 싶으면BinaryNode* root = tree->getRoot();포인터 변수로 선언해야하는지
5. 처음에 BinaryTree* tree, 선언했는지 왜 뒤에tree = new BinaryTree();똑같이 tree로 선언했는지 ?
: BinaryTree tree는 그냥 포인터 변수를 선언하는 단계이고 실제로 메모리에 할당하려면 tree = new BinaryTree(); 를 해야함 --> 그냥 BinaryTree tree = new BinaryTree(); 인거임
