与えられた二分木をC++で二重リンクリスト（セット2）に変換します

このチュートリアルでは、バイナリツリーを二重リンクリストに変換するプログラムについて説明します。

このために、バイナリツリーが提供されます。私たちのタスクは、左右のポインターが前のポインターと次のポインターになるように、二重にリンクされたリストに変換することです。また、二重リンクリストの順序は、バイナリツリーの順序どおりの走査と同じである必要があります。

このために、私たちは異なるアプローチをとっています。二分木を逆の順序でトラバースします。それに加えて、新しいノードを作成し、ヘッドポインタを最新のノードに移動します。これにより、最後から最初まで二重にリンクされたリストが作成されます。

例

#include <stdio.h>
#include <stdlib.h>
//node structure for tree
struct Node{
   int data;
   Node *left, *right;
};
//converting the binary tree to
//doubly linked list
void binary_todll(Node* root, Node** head_ref){
   if (root == NULL)
      return;
   //converting right subtree
   binary_todll(root->right, head_ref);
   //inserting the root value to the
   //doubly linked list
   root->right = *head_ref;
   //moving the head pointer
   if (*head_ref != NULL)
      (*head_ref)->left = root;
   *head_ref = root;
   //converting left subtree
   binary_todll(root->left, head_ref);
}
//allocating new node for doubly linked list
Node* newNode(int data){
   Node* node = new Node;
   node->data = data;
   node->left = node->right = NULL;
      return node;
}
//printing doubly linked list
void print_dll(Node* head){
   printf("Doubly Linked list:\n");
   while (head) {
      printf("%d ", head->data);
      head = head->right;
   }
}
int main(){
   Node* root = newNode(5);
   root->left = newNode(3);
   root->right = newNode(6);
   root->left->left = newNode(1);
   root->left->right = newNode(4);
   root->right->right = newNode(8);
   root->left->left->left = newNode(0);
   root->left->left->right = newNode(2);
   root->right->right->left = newNode(7);
   root->right->right->right = newNode(9);
   Node* head = NULL;
   binary_todll(root, &head);
   print_dll(head);
   return 0;
}

出力

Doubly Linked list:
0 1 2 3 4 5 6 7 8 9