给定一个二叉树（BT），将其转换为一个双链表（DLL）。在转换后的DLL中，节点中的左指针和右指针分别用作上一个和下一个指针。DLL中节点的顺序必须与给定二叉树的顺序相同。顺序遍历的第一个节点（BT中最左边的节点）必须是DLL的头节点。
null
下面讨论了三种不同的解决方案。 将给定的二叉树转换为双链表|集1 将给定的二叉树转换为双链表|集2 将给定的二叉树转换为双链表|集3 在下面的实现中，我们按顺序遍历树。我们在当前链表的开头添加节点，并使用指针对指针更新列表的开头。因为我们在开始插入，所以我们需要按相反的顺序处理叶子。对于相反的顺序，我们首先遍历右子树，然后遍历左子树。i、 e.按顺序进行反向遍历。
C++
// C++ program to convert a given Binary Tree to Doubly Linked List #include <bits/stdc++.h> // Structure for tree and linked list struct Node { int data; Node *left, *right; }; // Utility function for allocating node for Binary // Tree. Node* newNode( int data) { Node* node = new Node; node->data = data; node->left = node->right = NULL; return node; } // A simple recursive function to convert a given // Binary tree to Doubly Linked List // root --> Root of Binary Tree // head --> Pointer to head node of created doubly linked list void BToDLL(Node* root, Node*& head) { // Base cases if (root == NULL) return ; // Recursively convert right subtree BToDLL(root->right, head); // insert root into DLL root->right = head; // Change left pointer of previous head if (head != NULL) head->left = root; // Change head of Doubly linked list head = root; // Recursively convert left subtree BToDLL(root->left, head); } // Utility function for printing double linked list. void printList(Node* head) { printf ( "Extracted Double Linked list is:" ); while (head) { printf ( "%d " , head->data); head = head->right; } } // Driver program to test above function int main() { /* Constructing below tree 5 / 3 6 / 1 4 8 / / 0 2 7 9 */ 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; BToDLL(root, head); printList(head); return 0; } |
JAVA
// Java program to convert a given Binary Tree to Doubly Linked List /* Structure for tree and Linked List */ class Node { int data; Node left, right; public Node( int data) { this .data = data; left = right = null ; } } class BinaryTree { // root --> Root of Binary Tree Node root; // head --> Pointer to head node of created doubly linked list Node head; // A simple recursive function to convert a given // Binary tree to Doubly Linked List void BToDLL(Node root) { // Base cases if (root == null ) return ; // Recursively convert right subtree BToDLL(root.right); // insert root into DLL root.right = head; // Change left pointer of previous head if (head != null ) head.left = root; // Change head of Doubly linked list head = root; // Recursively convert left subtree BToDLL(root.left); } // Utility function for printing double linked list. void printList(Node head) { System.out.println( "Extracted Double Linked List is : " ); while (head != null ) { System.out.print(head.data + " " ); head = head.right; } } // Driver program to test the above functions public static void main(String[] args) { /* Constructing below tree 5 / 3 6 / 1 4 8 / / 0 2 7 9 */ BinaryTree tree = new BinaryTree(); tree.root = new Node( 5 ); tree.root.left = new Node( 3 ); tree.root.right = new Node( 6 ); tree.root.left.right = new Node( 4 ); tree.root.left.left = new Node( 1 ); tree.root.right.right = new Node( 8 ); tree.root.left.left.right = new Node( 2 ); tree.root.left.left.left = new Node( 0 ); tree.root.right.right.left = new Node( 7 ); tree.root.right.right.right = new Node( 9 ); tree.BToDLL(tree.root); tree.printList(tree.head); } } // This code has been contributed by Mayank Jaiswal(mayank_24) |
Python3
# Python3 program to convert a given Binary Tree to Doubly Linked List class Node: def __init__( self , data): self .data = data self .left = self .right = None class BinaryTree: # A simple recursive function to convert a given # Binary tree to Doubly Linked List # root --> Root of Binary Tree # head --> Pointer to head node of created doubly linked list root, head = None , None def BToDll( self , root: Node): if root is None : return # Recursively convert right subtree self .BToDll(root.right) # Insert root into doubly linked list root.right = self .head # Change left pointer of previous head if self .head is not None : self .head.left = root # Change head of doubly linked list self .head = root # Recursively convert left subtree self .BToDll(root.left) @staticmethod def print_list(head: Node): print ( 'Extracted Double Linked list is:' ) while head is not None : print (head.data, end = ' ' ) head = head.right # Driver program to test above function if __name__ = = '__main__' : """ Constructing below tree 5 // \ 3 6 // \ \ 1 4 8 // \ // \ 0 2 7 9 """ tree = BinaryTree() tree.root = Node( 5 ) tree.root.left = Node( 3 ) tree.root.right = Node( 6 ) tree.root.left.left = Node( 1 ) tree.root.left.right = Node( 4 ) tree.root.right.right = Node( 8 ) tree.root.left.left.left = Node( 0 ) tree.root.left.left.right = Node( 2 ) tree.root.right.right.left = Node( 7 ) tree.root.right.right.right = Node( 9 ) tree.BToDll(tree.root) tree.print_list(tree.head) # This code is contributed by Rajat Srivastava |
C#
// C# program to convert a given Binary Tree to Doubly Linked List using System; /* Structure for tree and Linked List */ public class Node { public int data; public Node left, right; public Node( int data) { this .data = data; left = right = null ; } } class GFG { // root --> Root of Binary Tree public Node root; // head --> Pointer to head node of created doubly linked list public Node head; // A simple recursive function to convert a given // Binary tree to Doubly Linked List public virtual void BToDLL(Node root) { // Base cases if (root == null ) return ; // Recursively convert right subtree BToDLL(root.right); // insert root into DLL root.right = head; // Change left pointer of previous head if (head != null ) head.left = root; // Change head of Doubly linked list head = root; // Recursively convert left subtree BToDLL(root.left); } // Utility function for printing double linked list. public virtual void printList(Node head) { Console.WriteLine( "Extracted Double " + "Linked List is : " ); while (head != null ) { Console.Write(head.data + " " ); head = head.right; } } // Driver program to test above function public static void Main( string [] args) { /* Constructing below tree 5 / 3 6 / 1 4 8 / / 0 2 7 9 */ GFG tree = new GFG(); tree.root = new Node(5); tree.root.left = new Node(3); tree.root.right = new Node(6); tree.root.left.right = new Node(4); tree.root.left.left = new Node(1); tree.root.right.right = new Node(8); tree.root.left.left.right = new Node(2); tree.root.left.left.left = new Node(0); tree.root.right.right.left = new Node(7); tree.root.right.right.right = new Node(9); tree.BToDLL(tree.root); tree.printList(tree.head); } } // This code is contributed by Shrikant13 |
Javascript
<script> // javascript program to convert a given // Binary Tree to Doubly Linked List /* Structure for tree and Linked List */ class Node { constructor(data) { this .data = data; this .left = this .right = null ; } } // root --> Root of Binary Tree var root; // head --> Pointer to head node of created doubly linked list var head; // A simple recursive function to convert a given // Binary tree to Doubly Linked List function BToDLL( root) { // Base cases if (root == null ) return ; // Recursively convert right subtree BToDLL(root.right); // insert root into DLL root.right = head; // Change left pointer of previous head if (head != null ) head.left = root; // Change head of Doubly linked list head = root; // Recursively convert left subtree BToDLL(root.left); } // Utility function for printing var linked list. function printList( head) { document.write( "Extracted Double Linked List is :<br/> " ); while (head != null ) { document.write(head.data + " " ); head = head.right; } } // Driver program to test the above functions /* Constructing below tree 5 / 3 6 / 1 4 8 / / 0 2 7 9 */ root = new Node(5); root.left = new Node(3); root.right = new Node(6); root.left.right = new Node(4); root.left.left = new Node(1); root.right.right = new Node(8); root.left.left.right = new Node(2); root.left.left.left = new Node(0); root.right.right.left = new Node(7); root.right.right.right = new Node(9); BToDLL(root); printList(head); // This code contributed by umadevi9616 </script> |
输出：
Extracted Double Linked list is:0 1 2 3 4 5 6 7 8 9
时间复杂性： O（n），因为解决方案只遍历给定的二叉树。
本文由 阿迪蒂亚·戈尔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
