C++로 구현하는 이진 트리 이중 순회(Double Order Traversal) 프로그램

이 글에서는 이진 트리의 이중 순회(Double Order Traversal)를 구현하는 C++ 프로그램을 소개합니다.

이중 순회는 일반적인 전위·중위·후위 순회와 달리, 각 서브트리의 루트(부모) 노드를 두 번 방문하는 순회 방식입니다. 노드에 처음 도착할 때 한 번 방문하고, 왼쪽 서브트리를 모두 순회한 뒤 되돌아올 때 한 번 더 방문하는 것이 특징입니다.

알고리즘

시작
    BST 클래스는 다음 함수들을 가진다:
        insert() = 트리에 항목을 삽입한다.
            루트 노드를 먼저 설정한다.
            새 노드의 값이 현재 노드보다 크면 오른쪽 자식으로,
            작으면 왼쪽 자식으로 삽입한다.
        doubleOrder() = 이중 순회를 수행한다.
            루트가 NULL이면
                "트리가 비어 있습니다"를 출력한다.
            그렇지 않으면 다음을 수행한다.
                (서브)트리의 루트를 방문한다.
                왼쪽 서브트리를 순회한다.
                (서브)트리의 루트를 다시 방문한다.
                오른쪽 서브트리를 순회한다.
끝

예제 코드

# include <iostream>
# include <cstdlib>
using namespace std;

struct nod//노드 선언 {
    int info;
    struct nod *l;
    struct nod *r;
}*r;

class BST {
    public://함수 선언
    void insert(nod *, nod *);
    void doubleOrder(nod *);
    void show(nod *, int);
    BST() {
        r = NULL;
    }
};

void BST::insert(nod *tree, nod *newnode) {
    if (r == NULL) {
        r = new nod;
        r->info = newnode->info;
        r->l = NULL;
        r->r = NULL;
        cout<<"Root Node is Added"<<endl;
        return;
    }
    if (tree->info == newnode->info) {
        cout<<"Element already in the tree"<<endl;
        return;
    }
    if (tree->info >newnode->info) {
        if (tree->l != NULL) {
            insert(tree->l, newnode);
        } else {
            tree->l= newnode;
            (tree->l)->l = NULL;
            (tree->l)->r= NULL;
            cout<<"Node Added To Left"<<endl;
            return;
        }
    } else {
        if (tree->r != NULL) {
            insert(tree->r, newnode);
        } else {
            tree->r = newnode;
            (tree->r)->l= NULL;
            (tree->r)->r = NULL;
            cout<<"Node Added To Right"<<endl;
            return;
        }
    }
}

void BST::doubleOrder(nod *ptr) {
    if (r == NULL) {
        cout << "Tree is empty" << endl;
        return;
    }
    if (ptr != NULL) {
        cout << ptr->info << " ";
        doubleOrder(ptr->l);
        cout << ptr->info << " ";
        doubleOrder(ptr->r);
    }
}

void BST::show(nod *ptr, int level)//트리 출력 {
    int i;
    if (ptr != NULL) {
        show(ptr->r, level + 1);
        cout << endl;
        if (ptr == r)
            cout << "Root->: ";
        else {
            for (i = 0; i < level; i++)
                cout << " ";
        }
        cout << ptr->info;
        show(ptr->l, level + 1);
    }
}

int main() {
    int c, n;
    BST bst;
    nod *t;
    while (1)//메뉴 반복 처리 {
        cout << "1.Insert Element " << endl;
        cout << "2.Double-Order Traversal" << endl;
        cout << "3.Show" << endl;
        cout << "4.Quit" << endl;
        cout << "Enter your choice : ";
        cin >>c;
        switch (c)//선택에 따라 기능 수행 {
            case 1:
                t = new nod;
                cout << "Enter the number to be inserted : ";
                cin >>t->info;
                bst.insert(r, t);
            break;
            case 2:
                cout << "Double-Order Traversal of BST:" << endl;
                bst.doubleOrder(r);
                cout << endl;
            break;
            case 3:
                cout << "Print BST:" << endl;
                bst.show(r, 1);
                cout << endl;
            break;
            case 4:
                exit(1);
            default:
                cout << "Wrong choice" << endl;
        }
    }
}

실행 결과

1.Insert Element
2.Double-Order Traversal
3.Show
4.Quit
Enter your choice : 1
Enter the number to be inserted :
7
Root Node is Added
1.Insert Element
2.Double-Order Traversal
3.Show
4.Quit
Enter your choice : 1
Enter the number to be inserted : 6
Node Added To Left
1.Insert Element
2.Double-Order Traversal
3.Show
4.Quit
Enter your choice : 1
Enter the number to be inserted : 4
Node Added To Left
1.Insert Element
2.Double-Order Traversal
3.Show
4.Quit
Enter your choice : 1
Enter the number to be inserted : 2
Node Added To Left
1.Insert Element
2.Double-Order Traversal
3.Show
4.Quit
Enter your choice : 1
Enter the number to be inserted : 10
Node Added To Right
1.Insert Element
2.Double-Order Traversal
3.Show
4.Quit
Enter your choice : 3
Print BST:
10
Root->: 7
6
4
2
1.Insert Element
2.Double-Order Traversal
3.Show
4.Quit
Enter your choice : 2
Double-Order Traversal of BST:
7 6 4 2 2 4 6 7 10 10
1.Insert Element
2.Double-Order Traversal
3.Show
4.Quit
Enter your choice : 4

실행 결과를 보면 이중 순회의 결과가 7 6 4 2 2 4 6 7 10 10으로 출력됩니다. 각 노드가 정확히 두 번씩 방문되어, 왼쪽 서브트리를 지나갈 때와 되돌아올 때 루트 값이 한 번씩 출력되는 것을 확인할 수 있습니다.

참고 사항

이중 순회의 시간 복잡도는 노드 수를 n이라 할 때 O(n)입니다. 각 노드를 두 번 방문하지만 총 방문 횟수는 여전히 노드 수에 비례하기 때문입니다. 이러한 순회 방식은 트리 구조를 변환하거나, 노드 진입·탈출 시점을 모두 기록해야 하는 문제(예: Euler Tour 기법)에서 유용하게 활용됩니다.