给定一个二叉树（BT），将其转换为一个双链表（DLL）。在转换后的DLL中，节点中的左指针和右指针分别用作上一个和下一个指针。DLL中的节点顺序必须与给定二叉树的顺序相同。按序遍历的第一个节点（BT中最左边的节点）必须是DLL的头节点。
null
针对这个问题，讨论了以下两种不同的解决方案。 将给定的二叉树转换为双链表|集1 将给定的二叉树转换为双链表|集2
在本文中，我们将讨论第三种解决方案，这似乎是最简单的解决方案。其思想是按顺序遍历二叉树。在进行有序遍历时，在变量中跟踪之前访问的节点，例如 上 .对于每个访问的节点，将其设置在 上 这个节点的前一个 上 . 感谢rahul、wishall和所有其他读者对上述两篇文章的有用评论。
以下是此解决方案的实现。
C++
// A C++ program for in-place conversion of Binary Tree to DLL #include <iostream> using namespace std; /* A binary tree node has data, and left and right pointers */ struct node { int data; node* left; node* right; }; // 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 BinaryTree2DoubleLinkedList(node *root, node **head) { // Base case if (root == NULL) return ; // Initialize previously visited node as NULL. This is // static so that the same value is accessible in all recursive // calls static node* prev = NULL; // Recursively convert left subtree BinaryTree2DoubleLinkedList(root->left, head); // Now convert this node if (prev == NULL) *head = root; else { root->left = prev; prev->right = root; } prev = root; // Finally convert right subtree BinaryTree2DoubleLinkedList(root->right, head); } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ node* newNode( int data) { node* new_node = new node; new_node->data = data; new_node->left = new_node->right = NULL; return (new_node); } /* Function to print nodes in a given doubly linked list */ void printList(node *node) { while (node!=NULL) { cout << node->data << " " ; node = node->right; } } /* Driver program to test above functions*/ int main() { // Let us create the tree shown in above diagram 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); // Convert to DLL node *head = NULL; BinaryTree2DoubleLinkedList(root, &head); // Print the converted list printList(head); return 0; } |
JAVA
// A Java program for in-place conversion of Binary Tree to DLL // A binary tree node has data, left pointers and right pointers class Node { int data; Node left, right; public Node( int data) { this .data = data; left = right = null ; } } class BinaryTree { Node root; // head --> Pointer to head node of created doubly linked list Node head; // Initialize previously visited node as NULL. This is // static so that the same value is accessible in all recursive // calls static Node prev = null ; // A simple recursive function to convert a given Binary tree // to Doubly Linked List // root --> Root of Binary Tree void BinaryTree2DoubleLinkedList(Node root) { // Base case if (root == null ) return ; // Recursively convert left subtree BinaryTree2DoubleLinkedList(root.left); // Now convert this node if (prev == null ) head = root; else { root.left = prev; prev.right = root; } prev = root; // Finally convert right subtree BinaryTree2DoubleLinkedList(root.right); } /* Function to print nodes in a given doubly linked list */ void printList(Node node) { while (node != null ) { System.out.print(node.data + " " ); node = node.right; } } // Driver program to test above functions public static void main(String[] args) { // Let us create the tree as shown in above diagram BinaryTree tree = new BinaryTree(); tree.root = new Node( 10 ); tree.root.left = new Node( 12 ); tree.root.right = new Node( 15 ); tree.root.left.left = new Node( 25 ); tree.root.left.right = new Node( 30 ); tree.root.right.left = new Node( 36 ); // convert to DLL tree.BinaryTree2DoubleLinkedList(tree.root); // Print the converted List tree.printList(tree.head); } } // This code has been contributed by Mayank Jaiswal(mayank_24) |
Python3
# Python program for conversion of # binary tree to doubly linked list. class Node: def __init__( self , val): self .right = None self .data = val self .left = None class BtoDll: def __init__( self ): self .head = None self .tail = None def convert( self , root): # Base case if root is None : return # Recursively convert left subtree self .convert(root.left) # Now convert this node node = root if self .head is None : self .head = node else : self .tail.right = node node.left = self .tail self .tail = node # Finally convert right subtree self .convert(root.right) return self .head def BinaryTree2DoubleLinkedList(root): ''' A simple recursive function to convert a given Binary tree to Doubly Linked List root --> Root of Binary Tree ''' converter = BtoDll() return converter.convert(root) def print_dll(head): '''Function to print nodes in given doubly linked list''' while head is not None : print (head.data, end = " " ) head = head.right # Driver program to test above functions if __name__ = = "__main__" : # Let us create the tree as # shown in above diagram root = Node( 10 ) root.left = Node( 12 ) root.right = Node( 15 ) root.left.left = Node( 25 ) root.left.right = Node( 30 ) root.right.left = Node( 36 ) # convert to DLL head = BinaryTree2DoubleLinkedList(root) # Print the converted list print_dll(head) # This code is contributed by codesankalp (SANKALP) |
C#
// A C# program for in-place conversion // of Binary Tree to DLL using System; // A binary tree node has data, left // pointers and right pointers public class Node { public int data; public Node left, right; public Node( int data) { this .data = data; left = right = null ; } } class GFG { public Node root; // head --> Pointer to head node of // created doubly linked list public Node head; // Initialize previously visited node // as NULL. This is static so that the // same value is accessible in all // recursive calls public static Node prev = null ; // A simple recursive function to // convert a given Binary tree // to Doubly Linked List // root --> Root of Binary Tree public virtual void BinaryTree2DoubleLinkedList(Node root) { // Base case if (root == null ) { return ; } // Recursively convert left subtree BinaryTree2DoubleLinkedList(root.left); // Now convert this node if (prev == null ) { head = root; } else { root.left = prev; prev.right = root; } prev = root; // Finally convert right subtree BinaryTree2DoubleLinkedList(root.right); } /* Function to print nodes in a given doubly linked list */ public virtual void printList(Node node) { while (node != null ) { Console.Write(node.data + " " ); node = node.right; } } // Driver Code public static void Main( string [] args) { // Let us create the tree as // shown in above diagram GFG tree = new GFG(); tree.root = new Node(10); tree.root.left = new Node(12); tree.root.right = new Node(15); tree.root.left.left = new Node(25); tree.root.left.right = new Node(30); tree.root.right.left = new Node(36); // convert to DLL tree.BinaryTree2DoubleLinkedList(tree.root); // Print the converted List tree.printList(tree.head); } } // This code is contributed by Shrikant13 |
Javascript
<script> // A javascript program for in-place conversion of Binary Tree to DLL // A binary tree node has data, left pointers and right pointers class Node { constructor(val) { this .data = val; this .left = null ; this .right = null ; } } var root; // head --> Pointer to head node of created doubly linked list var head; // Initialize previously visited node as NULL. This is // so that the same value is accessible in all recursive // calls var prev = null ; // A simple recursive function to convert a given Binary tree // to Doubly Linked List // root --> Root of Binary Tree function BinaryTree2DoubleLinkedList(root) { // Base case if (root == null ) return ; // Recursively convert left subtree BinaryTree2DoubleLinkedList(root.left); // Now convert this node if (prev == null ) head = root; else { root.left = prev; prev.right = root; } prev = root; // Finally convert right subtree BinaryTree2DoubleLinkedList(root.right); } /* Function to print nodes in a given doubly linked list */ function printList(node) { while (node != null ) { document.write(node.data + " " ); node = node.right; } } // Driver program to test above functions // Let us create the tree as shown in above diagram root = new Node(10); root.left = new Node(12); root.right = new Node(15); root.left.left = new Node(25); root.left.right = new Node(30); root.right.left = new Node(36); // convert to DLL BinaryTree2DoubleLinkedList(root); // Print the converted List printList(head); // This code contributed by umadevi9616 </script> |
输出：
25 12 30 10 36 15
请注意，使用上述静态变量不是推荐的做法（为了简单起见，我们使用了静态变量）。想象一种情况，两棵或更多的树调用相同的函数。旧价值观 上 将在下一次调用另一棵树时使用。为了避免此类问题，我们可以使用双指针或对指针的引用。 时间复杂性： 上面的程序执行简单的顺序遍历，因此时间复杂度为O（n），其中n是给定二叉树中的节点数。
下面的代码是上述顺序遍历方法的直观迭代实现（灵感来自 这段视频 ) –
C++
Node * bToDLL(Node *root) { stack<pair<Node*, int >> s; s.push({root, 0}); vector< int > res; bool flag = true ; Node* head = NULL; Node* prev = NULL; while (!s.empty()) { auto x = s.top(); Node* t = x.first; int state = x.second; s.pop(); if (state == 3 or t == NULL) continue ; s.push({t, state+1}); if (state == 0) s.push({t->left, 0}); else if (state == 1) { if (prev) prev->right = t; t->left = prev; prev = t; if (flag) { head = t; flag = false ; } } else if (state == 2) s.push({t->right, 0}); } return head; } |
时间复杂度：O（N）
空间复杂性：O（N）
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
