C++에서 주어진 이진 트리를 이중 연결 목록(세트 1)으로 변환

이 자습서에서는 이진 트리를 이중 연결 목록으로 변환하는 프로그램에 대해 설명합니다.

이를 위해 이진 트리가 제공됩니다. 우리의 임무는 왼쪽 및 오른쪽 포인터가 이전 및 다음 포인터가 되도록 이중 연결 목록으로 변환하는 것입니다. 또한 이중 연결 목록의 순차 순서는 이진 트리의 중위 순회와 같아야 합니다.

이를 위해 우리는 매우 직접적인 접근 방식을 취하고 있습니다. 이중 연결 리스트의 노드를 순서대로 이진 트리를 순회하고 마지막으로 왼쪽과 오른쪽을 각각 이전 노드와 다음 노드로 만듭니다.

예시

#include <iostream>
using namespace std;
//node structure of binary tree
struct node{
   int data;
   node* left;
   node* right;
};
//traversing and making nodes for
//doubly linked list
void binarytodll(node *root, node **head){
   if (root == NULL)
      return;
   static node* prev = NULL;
   //converting left subtree
   binarytodll(root->left, head);
   if (prev == NULL)
      *head = root;
   else {
      root->left = prev;
      prev->right = root;
   }
   prev = root;
   //converting right subtree
   binarytodll(root->right, head);
}
//allocating a new node
node* newNode(int data) {
   node* new_node = new node;
   new_node->data = data;
   new_node->left = new_node->right = NULL;
   return (new_node);
}
//printing nodes of doubly linked list
void print_dll(node *node){
   while (node!=NULL) {
      cout << node->data << " ";
      node = node->right;
   }
}
int main(){
   node *root = newNode(10);
   root->left = newNode(12);
   root->right = newNode(15);
   root->left->left = newNode(25);
   root->left->right = newNode(30);
   root->right->left = newNode(36);
   node *head = NULL;
   binarytodll(root, &head);
   print_dll(head);
   return 0;
}

출력

25 12 30 10 36 15