C++로 구현하는 이진 트리 대각선 순회(Diagonal Traversal)

이진 트리의 대각선 순회(Diagonal Traversal)는 기울기가 -1인 직선들을 기준으로, 같은 대각선 위에 놓인 노드들을 하나의 그룹으로 묶어 차례대로 탐색하고 출력하는 방식입니다. 루트에서 오른쪽 자식으로만 이어지는 경로가 첫 번째 대각선을 이루고, 왼쪽 자식으로 내려갈 때마다 다음 대각선으로 넘어간다고 생각하면 개념을 쉽게 이해할 수 있습니다.

트리 노드 구조체 정의

먼저 데이터와 왼쪽·오른쪽 자식 포인터를 가지는 트리 노드를 표현하는 구조체를 정의합니다. 최초로 생성되는 노드는 루트(root) 노드가 되고, 이후 생성되는 노드들은 자식 노드로 연결됩니다.

struct Node {
    int data;
    struct Node *leftChild, *rightChild;
};

노드 생성 함수 작성

다음으로 정수 값을 받아 새 노드의 data 멤버에 저장하고, 생성된 노드의 포인터를 반환하는 createNode(int data) 함수를 작성합니다. 새로 만들어진 노드의 왼쪽과 오른쪽 자식은 모두 NULL로 초기화됩니다.

struct Node* createNode(int data){
    struct Node* node = new Node();
    node->data = data;
    node->leftChild = node->rightChild = NULL;
    return node;
}

대각선 순회 함수 구현

traverseDiagonal(Node* root, int depth, map<int, vector<int>> &myMap) 함수는 루트 노드, 현재 깊이(depth), 그리고 int를 키로 int 벡터를 값으로 가지는 맵을 인자로 받습니다. 맵은 참조(&)로 전달되므로 함수 내부에서 직접 갱신됩니다.

함수는 먼저 현재 노드가 NULL인지 확인하고, NULL이 아니라면 해당 노드의 데이터를 현재 depth에 해당하는 벡터 끝에 추가합니다.

void traverseDiagonal(Node* root, int depth, map<int, vector<int>> &myMap){
    if(root){
        myMap[depth].push_back(root->data);

이후 재귀적으로 트리를 순회하면서 대각선 거리를 추적합니다. 왼쪽 자식으로 이동할 때는 depth에 1을 더하고, 오른쪽 자식으로 이동할 때는 depth를 그대로 유지합니다. 이렇게 하면 같은 대각선상에 있는 노드들이 동일한 depth 키 아래에 함께 저장됩니다.

traverseDiagonal(root->leftChild, depth+1, myMap);
traverseDiagonal(root->rightChild, depth, myMap);

메인 함수에서 트리 생성

main 함수에서는 createNode(data) 함수를 사용해 다음과 같이 트리를 구성합니다.

Node *root = createNode(10);
    root->leftChild = createNode(5);
    root->rightChild = createNode(15);
    root->leftChild->leftChild = createNode(4);
    root->leftChild->rightChild = createNode(6);
    root->rightChild->rightChild = createNode(17);
    root->rightChild->rightChild->leftChild = createNode(16);

그다음 int를 키로, int 벡터를 값으로 가지는 맵 myMap을 선언하고, 루트 노드와 초기 깊이 0과 함께 traverseDiagonal 함수에 전달합니다.

map<int, vector<int>> myMap;
traverseDiagonal(root, 0, myMap);

맵이 모두 채워지면 범위 기반 for문(range-based for loop)으로 순회하면서 각 대각선에 속한 값들을 출력합니다.

for(auto k : myMap){
    for(auto node : k.second)
        cout<<node<<" ";
    cout<<endl;
}

전체 예제 코드

아래는 이진 트리의 대각선 순회를 수행하는 전체 구현 예제입니다.

#include <iostream>
#include <map>
#include <vector>
using namespace std;

struct Node {
    int data;
    Node *leftChild, *rightChild;
};

Node* createNode(int data){
    Node* node = new Node();
    node->data = data;
    node->leftChild = node->rightChild = NULL;
    return node;
}

void traverseDiagonal(Node* root, int depth, map<int, vector<int>> &myMap){
    if(root){
        myMap[depth].push_back(root->data);
        traverseDiagonal(root->leftChild, depth+1, myMap);
        traverseDiagonal(root->rightChild, depth, myMap);
    }
}

int main(){
    Node *root = createNode(10);
    root->leftChild = createNode(5);
    root->rightChild = createNode(15);
    root->leftChild->leftChild = createNode(4);
    root->leftChild->rightChild = createNode(6);
    root->rightChild->rightChild = createNode(17);
    root->rightChild->rightChild->leftChild = createNode(16);

    map<int, vector<int>> myMap;
    traverseDiagonal(root, 0, myMap);

    for(auto k : myMap){
        for(auto node : k.second)
            cout << node << " ";
        cout << endl;
    }
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

10 15 17
5 6 16
4

첫 번째 줄은 루트에서 오른쪽으로만 이동하는 첫 번째 대각선에 속한 노드들(10, 15, 17), 두 번째 줄은 두 번째 대각선의 노드들(5, 6, 16), 세 번째 줄은 세 번째 대각선의 노드(4)를 나타냅니다. 이처럼 맵의 키인 depth 값이 곧 대각선 번호 역할을 하므로, 결과가 대각선 순서대로 정렬되어 출력됩니다.