📌이진트리 개념

--> 손필기 확인

📌이진트리 구현

✅BinaryTree 클래스

class BinaryTree {
BinaryNode* root;

public:
BinaryTree() : root(NULL) { }
~BinaryTree() { }

void setRoot(BinaryNode* node) { root = node; }
BinaryNode* getRoot() { return root; }
bool isEmpty() { return root == NULL; }

// Tree Operation
int getCount();		// 노드 개수
int getLeafCount();	// 단말 노드 개수
int getHeight();	// 트리의 높이
bool isFull();		// full binary tree인지 
int calcLevel(int n);  	// 데이터가 n인 노드의 레벨

int getCount(BinaryNode* node);
int getLeafCount(BinaryNode* node);
int getHeight(BinaryNode* node);
bool isFull(BinaryNode* node);
        int calcLevel(BinaryNode* node, int n, int level);
};

📢 외부에서는 파라미터 없이 호출하고, 내부에서는 파라미터가 있는 함수로 재귀적으로 호출하는 구조

• 파라미터가 없는 함수 = 외부 인터페이스 역할
• 파라미터가 있는 함수 = 재귀 호출로 실제 작업 수행
  --> 각 노드를 기준으로 좌우, 자식 노드를 순회하면서 원하는 작업을 처리
  🌟 파라미터가 없는 함수와 파라미터가 있는 함수의 관계

// 외부에서 호출되는 함수
// 루트 노드를 기준으로 재귀적 작업 시작
int getCount() {
    return getCount(root); 
}
// 실제로 재귀적으로 작업을 수행하는 함수
int getCount(BinaryNode* node) {
    // Base case: 노드가 없으면 0을 반환
    if (node == NULL) return 0;  
    return 1 + getCount(node->left)
             + getCount(node->right);

✅노드 개수 getCount()

트리의 노드 개수
= root 1개 + 왼쪽 서브 트리 노드 개수 + 오른쪽 서브 트리 노드 개수
⭐ 재귀를 사용하는 이유
= 재귀 호출을 통해 트리의 모든 노드를 방문하기 위해서 (트리의 구조가 동일하기 때문에)

// 트리의 노드 개수를 구하는 함수 --> 전체 트리 개수 
int BinaryTree::getCount() {
     return isEmpty() ? 0 : getCount(root);
} ''' (1) 

// 어떤 node를 루트로 하는 서브트리의 노드 개수를 구하는 함수 
// 서브 트리 안에서도 노드 개수를 구할 수 있음
if (node == NULL) return 0; '''(2) 
else
    return 1 + getCount(node -> getLeft())
             + getCount(node -> getRight()); '''(3)

🏷️ 코드 설명

(1) 전체 트리의 노드 개수를 구하는 함수

• isEmpty()가 true인 경우 --> 0을 반환
• isEmpty()가 false인 경우 --> 트리에 노드가 있으므로 루트 노드부터 시작해서 노드 개수를 세어야함.
  (2) 재귀 함수의 종료 조건(Base Case)
• 재귀함수에서 전달된 node가 NULL인지 확인
• 노드가 NULL인 경우(리프 노드의 자식 노드에 도달했을 때 발생) --> 0 반환
  (3) 현재 노드와 왼/오 서브트리의 노드 개수를 합산하는 부분 (재귀적으로 처리)
• getCount(node->getLeft())를 호출해 왼쪽 서브트리의 노드 개수를 구함
• getCount(node->getRight())를 호출하여 오른쪽 서브트리의 노드 개수를 구한다

<예시 트리>

• 루트 기준 왼쪽 서브트리 노드 갯수 계산
  
• 루트 기준 오른쪽 서브트리 노드 갯수 계산
  

✅단말노드 개수 getLeafCount()

트리의 단말 노드 개수
= 왼쪽 트리의 단말 노드 개수 + 오른쪽 트리의 단말 노드 개수

// 트리의 단말 노드의 개수를 구하는 함수
int BinaryTree::getLeafCount() { 
    return isEmpty() ? 0 : getLeafCount(root); }

// 임의의 노드 하부에 있는 단말 노드의 개수를 구하는 함수
int
BinaryTree::getLeafCount(BinaryNode* node) {
if (node == NULL) return 0;
if (node->isLeaf()) return 1;
else 
      return getLeafCount(node->getLeft()) 
            +getLeafCount(node->getRight());
}

✅ Test : node를 생성, 연결하여 트리 만들기

// 앞에 BinaryNode, Binary Tree class 설계해주기

// 메인 함수
int main(){
  BinaryTree tree;
  BinaryNode *d = new BinaryNode('D', NULL, NULL);
  BinaryNode *e = new BinaryNode('E', Null, Null);
  BinaryNode *b = new BinaryNode('B', d, e );
	BinaryNode *f = new BinaryNode('F', NULL, NULL );
	BinaryNode *g = new BinaryNode('G', NULL, NULL );
	BinaryNode *c = new BinaryNode('C', f, g );
    BinaryNode *a = new BinaryNode('A', b, c);
    tree.setRoot(a);
    // 일단 D,E를 먼저 만들어놔야 B가 생성 가능, 
    B는 왼/오 자식 링크를 d,e로 받고 있기 때문에. 
    같은 이유로 루트A는 B,C가 먼저 생성돼야 해서 
    맨 마지막에 루트를 설정해줌 
    
    cout << " 노드의 개수 = " << tree.getCount() << endl;
	cout << " 단말의 개수 = " << tree.getLeafCount() << endl;
	cout << " 트리의 높이 = " << tree.getHeight() << endl;
}

📌이진트리 순회 Tree Traversal

• preorder(전위 순회) : 루트 -> 왼쪽 자식 -> 오른쪽 자식)
• inorder(중위 순회) : 왼쪽 자식 -> 루트 -> 오른쪽 자식
• postorder(후위 순회) : 왼쪽 자식 -> 오른쪽 자식 -> 루트
  

✅Preorder

루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리
ex) 구조화된 문서출력

🏷️ pseudo code

📢 재귀함수에서 중요한 조건 2가지
1. 종결 조건을 잘 줘야함
2. 파라미터의 범위가 점점 수렴하는 방향으로 파라미터를 줘야함
(왼쪽 서브트리 -> 오른쪽 서브트리-> 왼 -> 오 ... 이런식으로)

✅Inorder

왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리

🏷️ pseudo code

✅Postorder

왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트
ex) 폴더 용량 계산

🏷️ pseudo code

✅ Tree Traversal 구현

🏷️ BinaryTree 클래스의 멤버 함수로 구현

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 멤버 함수 정의

- inorder --> 이후에 이진 탐색 트리할 때 주로 사용됨

void
BinaryTree::inorder(BinaryNode* node) { '''(1)
if (node != NULL) { '''(2)
   if (node->getLeft() != NULL) inorder(node->getLeft()); '''(3)
   cout << "[" << node->getData() << "] "; '''(4)
   if (node->getRight() != NULL) inorder(node->getRight());} '''(5)
}

📢 코드 설명

(1) 파라미터로는 현재 순회 중인 트리의 노드를 가리키는 포인터
(2) 현재 노드가 NULL인지 확인, 재귀 호출 종료 조건

• 리프 노드일 경우 순회를 멈춤
• 만약 node가 NULL이 아니라면, 이 노드를 처리한다.
  (3) 왼쪽 자식 노드로 재귀 호출
• 만약 node의 왼쪽 자식이 NULL이 아니라면, 그 왼쪽 자식을 중위 순회함 --> inorder(node->getLeft());
• 중위 순회에선 왼쪽 자식을 먼저 방문하므로, 왼쪽 자식이 있을 때 재귀적으로 내려감
  (4) 현재 노드의 데이터 출력
• 왼쪽 서브트리들을 모두 순회한 후, 현재 노드의 데이터를 출력
  (5) 오른쪽 자식 노드로 재귀 호출
• 만약 node의 오른쪽 자식이 NULL이 아니라면, 그 오른쪽 자식을 중위 순회

📢 재귀 과정

초기단계) inorder(root)가 호출되어 루트노드에서 시작
재귀단계) 재귀호출로 왼쪽 자식 node->getLeft()나 오른쪽 자식 node->getRight()로 전달되며, 이 과정에서 파라미터가 점점 수렴이 됨
종료단계) 최종적으로 node==NULL 종료조건이 만족되면, 재귀 호출 종료
** 파라미터가 점점 수렴하면서 종료 조건에 도달하는 과정

<중위 순회 코드 실행 예시>

• 중위 순회 출력 과정
  

- preorder

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());}
}

- postorder

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() << "] ";}
}