在C ++中将给定的二叉树转换为双链表（Set 2）

Z时代
2024-01-10
分类：综合

在本教程中，我们将讨论将二进制树转换为双向链表的程序。

为此，我们将提供一个二叉树。我们的任务是将其转换为双向链接列表，以使左右指针成为前一个指针和下一个指针。同样，双向链表的顺序必须等于二叉树的顺序遍历。

为此，我们采用了不同的方法。我们将以相反的顺序遍历二叉树。我们将与之一起创建新节点并将头指针移至最新节点；这将从头到尾创建双向链表。

示例

#include <stdio.h>
#include <stdlib.h>
//树的节点结构
struct Node{
   int data;
   Node *left, *right;
};
//将二叉树转换为
//双链表
void binary_todll(Node* root, Node** head_ref){
   if (root == NULL)
      return;
   //转换右子树
   binary_todll(root->right, head_ref);
   //将根值插入
   //双链表
   root->right = *head_ref;
   //移动头指针
   if (*head_ref != NULL)
      (*head_ref)->left = root;
   *head_ref = root;
   //转换左子树
   binary_todll(root->left, head_ref);
}
//allocating new node for 双链表
Node* newNode(int data){
   Node* node = new Node;
   node->data = data;
   node->left = node->right = NULL;
      return node;
}
//printing 双链表
void print_dll(Node* head){
   printf("双链表:\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;
}