[자료구조] #15 Tree(2)

• 이진 트리의 순회

 

순회는 자료구조 내의 데이터를 특정 순서대로 방문하는 것을 의미한다.

 

선형 자료구조에서의 순회

선형적인 순서로 조회한다.

이진 트리에서의 순회

트리는 비선형 자료구조이기 때문에 여러가지 순서로 노드를 방문할 수 있다.

 

• 이진 트리의 순회 방법

 

전위 순회(pre-order traversal)

루트 출력 → 왼쪽 서브트리 → 오른쪽 서브트리

def preorder(node):
    if node is not NULL:            # 현재 노드가 NULL이 아닌 경우에만 수행
        print(node.data)            # 현재 노드의 데이터를 출력
        preorder(node.left)         # 왼쪽 자식 노드를 전위 순회
        preorder(node.right)        # 오른쪽 자식 노드를 전위 순회

 

중위 순회(in-order traversal)

왼쪽 서브트리 → 루트 출력 → 오른쪽 서브트리

def inorder(node):
    if node is not NULL:             # 현재 노드가 NULL이 아닌 경우에만 수행
        inorder(node.left)           # 왼쪽 자식 노드를 중위 순회
        print(node.data)             # 현재 노드의 데이터를 출력
        inorder(node.right)          # 오른쪽 자식 노드를 중위 순회

 

후위 순회(post-order traversal)

왼쪽 서브트리 → 오른쪽 서브트리 → 루트 출력

def postorder(node):
    if node is not NULL:              # 현재 노드가 NULL이 아닌 경우에만 수행
        postorder(node.left)          # 왼쪽 자식 노드를 후위 순회
        postorder(node.right)         # 오른쪽 자식 노드를 후위 순회
        print(node.data)              # 현재 노드의 데이터를 출력

 

레벨 순회(level-order traversal)

레벨 순서로 노드를 방문한다.

 

Root(A)를 시작점으로 BFS(너비 우선 탐색)을 하면 된다.

BFS를 위해서 큐를 사용해야 한다.

def levelorder():
    initialize Q;                      # 큐 Q를 초기화
    Q.enqueue(root);                   # 루트 노드를 큐에 추가
    while Q is not empty:              # 큐가 비어 있지 않는 동안 반복
        cur_node = Q.dequeue();        # 큐의 맨 앞 노드를 제거하여 현재 노드로 설정
        if cur_node is not NULL:       # 현재 노드가 NULL이 아닌 경우에만 수행
            print(cur_node.data)       # 현재 노드의 데이터를 출력
            Q.enqueue(cur_node.left);  # 왼쪽 자식 노드를 큐에 추가
            Q.enqueue(cur_node.right); # 오른쪽 자식 노드를 큐에 추가

 

• 순회를 이용한 이진 트리의 연산

 

후위 순회를 응용한 소멸자

왼쪽/오른쪽 서브 트리의 노드들이 동적해제가 먼저되고 현재 노드를 해제해야 한다.

// BinaryTree 클래스의 소멸자
BinaryTree::~BinaryTree(){
    removesNodes(this->root);  // 루트 노드부터 시작하여 모든 노드를 제거
}

// 트리의 모든 노드를 후위 순회 방식으로 제거하는 재귀 함수
void BinaryTree::removeNodes(BinaryNode* node){
    if(node != nullptr){          // 현재 노드가 nullptr이 아닌 경우에만 수행
        removesNodes(node->getLeft());   // 왼쪽 자식 노드를 재귀적으로 제거
        removesNodes(node->getRight());  // 오른쪽 자식 노드를 재귀적으로 제거
        delete node;                     // 현재 노드를 삭제하여 메모리 해제
    }
}

 

getCount : 노드 개수 세기

각 서브 트리의 노드의 수와 자기 자신을 합하고 반환한다.

// BinaryTree 클래스의 노드 개수를 반환하는 함수
int BinaryTree::getCount() {
    return (this->empty()) ? 0 : getCount(this->root);  
// 트리가 비어 있으면 0을 반환, 그렇지 않으면 루트 노드에서 시작
}

// 특정 노드에서 시작하여 모든 하위 노드의 개수를 세는 재귀 함수
int BinaryTree::getCount(BinaryNode* node) {
    if (node == nullptr) return 0;      // 현재 노드가 nullptr이면 0을 반환
    int cnt = getCount(node->getLeft());  // 왼쪽 하위 트리의 노드 수를 셈
    cnt += 1;                            // 현재 노드를 포함하여 1 증가
    cnt += getCount(node->getRight());   // 오른쪽 하위 트리의 노드 수를 셈
    return cnt;                          // 전체 하위 트리의 노드 수를 반환
}

 

getLeafCount : 리프 노드 개수 세기

1. 전역변수를 두고 순회를 하면서 만나는 노드가 리프인지를 카운트한다.

2. 각 서브트리의 리프 노드의 수를 합하고 반환한다.

 

// BinaryTree 클래스의 리프 노드 개수를 반환하는 함수
int BinaryTree::getLeafCount() {
    return (this->empty()) ? 0 : getLeafCount(this->root);  
// 트리가 비어 있으면 0을 반환, 그렇지 않으면 루트 노드에서 시작
}

// 특정 노드에서 시작하여 모든 하위 노드의 리프 노드 개수를 세는 재귀 함수
int BinaryTree::getLeafCount(BinaryNode* node) {
    if (node == nullptr) return 0;      // 현재 노드가 nullptr이면 0을 반환
    if (node->isLeaf()) return 1;       // 현재 노드가 리프 노드이면 1을 반환
    // 왼쪽 하위 트리와 오른쪽 하위 트리의 리프 노드 수를 합산하여 반환
    return getLeafCount(node->getLeft()) + getLeafCount(node->getRight());
}

 

getHeight : 트리의 높이

트리의 높이는 서브 트리의 최대 높이 + 1이다.

// BinaryTree 클래스의 트리 높이를 반환하는 함수
int BinaryTree::getHeight() {
    return getHeight(root);  // 루트 노드에서 시작하여 높이를 계산
}

// 특정 노드에서 시작하여 하위 트리의 높이를 계산하는 재귀 함수
int BinaryTree::getHeight(BinaryNode *node) {
    if (node == nullptr) return -1;      // 현재 노드가 nullptr이면 -1 반환 (빈 트리의 높이)
    int hLeft = getHeight(node->getLeft());  // 왼쪽 하위 트리의 높이 계산
    int hRight = getHeight(node->getRight());  // 오른쪽 하위 트리의 높이 계산
    return 1 + max(hLeft, hRight);       // 더 큰 높이에 1을 더하여 반환 (현재 노드를 포함)
}