与えられた二分木を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