[C++] 삼항 트리를 이중 연결된 목록으로 변환

삼항 트리가 주어지면, 제자리에서 이중 연결된 목록으로 변환한다. 삼항 트리는 각 노드가 왼쪽, 중간, 오른쪽으로 구분되는 세 개의 자식 노드를 갖는 트리 데이터 구조다.

변환은 삼항 트리 노드의 왼쪽 자식 포인터가 이중 연결된 목록 노드의 이전 포인터 역할을 하고 오른쪽 자식 포인터가 이중 연결된 목록 노드의 다음 포인터 역할을 하고 중간 트리 노드가 자식 포인터는 아무 것도 가리키지 않아야 한다. 변환은 이중 연결된 목록의 노드에 추가 메모리를 할당하지 않고 삼항 트리 노드 포인터만 교환하여 수행해야 한다.

Input: Ternary Tree
 
            1
          / | \
        /   |   \
      /     |     \
     2      9      12
   / | \   / \     |  \
  3  6  8 10  11   13  16
  |   \           / \  |
  4    7         14 15 17
   \
    5
 
Output: Doubly Linked List
 
1 —> 2 —> 3 —> 4 —> 5 —> 6 —> 7 —> 8 —> 9 —> 10 —> 11 —> 12 —> 13 —> 14 —> 15 —> 16 —> 17 —> nullptr

위의 예에서 분명히 알 수 있듯이 삼항 트리의 루트 노드는 이중 연결된 목록의 자식보다 먼저 푸시된다. 모든 노드는 왼쪽 자식, 중간 자식, 오른쪽 자식을 순서대로 루트로 하는 하위 트리에서 이를 재귀적으로적으로 따른다.

아이디어는 역순으로 수행하는 것이다 포스트 오더 순회 삼항 나무에. 역 후위 순회에서는 삼항 트리 노드를 처리하기 전에 오른쪽 자식이 먼저 처리되고 중간 및 왼쪽 자식이 뒤따른다. 삼항 트리 노드의 모든 자식을 탐색한 후 이중 연결된 목록 앞에 노드를 삽입한다. 역 후위 순회는 이중 연결된 목록에서 올바른 삽입 순서를 보장하는 데 사용된다.

#include <iostream>
#include <string>
#include <utility>
using namespace std;
 
// 삼항 트리 노드를 저장할 데이터 구조
struct Node
{
    int data;
    Node *left, *mid, *right;
 
    Node() {}
    Node(int data): data(data) {}
};
 
// 이중 연결된 목록의 맨 앞에 트리 노드 삽입
void push(Node* node, Node* &headRef)
{
    // 이중 연결된 목록의 맨 앞에 주어진 노드를 삽입
    headRef->left = node;
    node->right = headRef;
 
    // 왼쪽 및 중간 자식 포인터를 null로 업데이트
    node->left = node->mid = nullptr;
 
    // 주어진 노드를 가리키도록 `head` 포인터를 업데이트
    headRef = node;
}
 
// 삼항 트리를 다음을 사용하여 이중 연결된 목록으로 변환
// 역순 포스트오더 순회
void ternaryTreeToDoublyLinkedList(Node* root, Node* &headRef)
{
    // 기본 케이스: 빈 트리
    if (root == nullptr) {
        return;
    }
 
    // 오른쪽, 중간, 왼쪽 자식에 대해 반복
    ternaryTreeToDoublyLinkedList(root->right, headRef);
    ternaryTreeToDoublyLinkedList(root->mid, headRef);
    ternaryTreeToDoublyLinkedList(root->left, headRef);
 
    // 이중 연결된 목록의 헤드 포인터 초기화
    if (headRef == nullptr) {
        headRef = root;
    }
    else {
        // 이중 연결된 목록의 맨 앞에 있는 현재 노드를 푸시
        push(root, headRef);
    }
}
 
// 이중 연결된 목록를 출력하는 도우미 함수
void printDoublyLinkedList(Node* ptr)
{
    while (ptr)
    {
        cout << ptr->data << " —> ";
        ptr = ptr->right;
    }
    cout << "nullptr";
}
 
int main()
{
    /* 다음 삼항 트리 생성
                  1
                / | \
              /   |   \
            /     |     \
           2      9      12
         / | \   / \     |  \
        3  6  8 10  11  13   16
        |   \          /  \   |
        4    7        14  15  17
         \
          5
    */
 
    Node* root = new Node(1);
 
    root->left = new Node(2);
    root->mid = new Node(9);
    root->right = new Node(12);
 
    root->left->left = new Node(3);
    root->left->mid = new Node(6);
    root->left->right = new Node(8);
 
    root->mid->left = new Node(10);
    root->mid->right = new Node(11);
 
    root->right->mid = new Node(13);
    root->right->right = new Node(16);
 
    root->left->left->mid = new Node(4);
    root->left->left->mid->right = new Node(5);
    root->left->mid->right = new Node(7);
 
    root->right->mid->left = new Node(14);
    root->right->mid->right = new Node(15);
    root->right->right->mid = new Node(17);
 
    Node* head = nullptr;
    ternaryTreeToDoublyLinkedList(root, head);
    printDoublyLinkedList(root);
 
    return 0;
}

 

 

삼항 트리를 이중 연결 목록으로 변환 (techiedelight.com)