Chuyển đổi cây nhị phân thành danh sách liên kết đôi hình tròn trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để chuyển đổi một cây nhị phân thành một danh sách được liên kết kép hình tròn.

Đối với điều này, chúng tôi sẽ được cung cấp một cây nhị phân. Nhiệm vụ của chúng ta sẽ là chuyển đổi các nút bên trái và nút bên phải thành các phần tử bên trái và bên phải tương ứng. Và lấy inorder của cây nhị phân làm thứ tự trình tự của danh sách liên kết vòng

Ví dụ

#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;
}

Đầu ra

Circular Linked List is :
25 12 30 10 36 15