在C ++中将给定的二叉树转换为双链表（Set 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