C++에서 이진 트리를 순환 이중 연결 목록으로 변환

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

이를 위해 바이너리 트리가 제공됩니다. 우리의 작업은 왼쪽 및 오른쪽 노드를 각각 왼쪽 및 오른쪽 요소로 변환하는 것입니다. 그리고 이진 트리의 순서를 순환 연결 리스트의 순서로 취하십시오.

예시

#include<iostream>
using namespace std;
//node structure of the binary tree
struct Node{
   struct Node *left, *right;
   int data;
};
//appending rightlist to the end of leftlist
Node *concatenate(Node *leftList, Node *rightList){
   //if one list is empty return the other list
   if (leftList == NULL)
      return rightList;
   if (rightList == NULL)
      return leftList;
   Node *leftLast = leftList->left;
   Node *rightLast = rightList->left;
   //connecting leftlist to rightlist
   leftLast->right = rightList;
   rightList->left = leftLast;
   leftList->left = rightLast;
   rightLast->right = leftList;
   return leftList;
}
//converting to circular linked list and returning the head
Node *bTreeToCList(Node *root){
   if (root == NULL)
      return NULL;
   Node *left = bTreeToCList(root->left);
   Node *right = bTreeToCList(root->right);
   root->left = root->right = root;
   return concatenate(concatenate(left, root), right);
}
//displaying circular linked list
void print_Clist(Node *head){
   cout << "Circular Linked List is :\n";
   Node *itr = head;
   do{
      cout << itr->data <<" ";
      itr = itr->right;
   }
   while (head!=itr);
      cout << "\n";
}
//creating new node and returning address
Node *newNode(int data){
   Node *temp = new Node();
   temp->data = data;
   temp->left = temp->right = NULL;
   return temp;
}
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 = bTreeToCList(root);
   print_Clist(head);
   return 0;
}

출력

Circular Linked List is :
25 12 30 10 36 15