给定一个二叉树（BT），将其转换为双链表（DLL）。在转换后的DLL中，节点中的左指针和右指针分别用作上一个和下一个指针。DLL中的节点顺序必须与给定二叉树的顺序相同。按序遍历的第一个节点（BT中最左边的节点）必须是DLL的头节点。
null
这一问题的解决方案已在中讨论过 这篇帖子 . 在这篇文章中，我们将讨论另一个简单而有效的解决方案。这里讨论的解决方案有两个简单的步骤。 1) 修正左指针 : 在这一步中，我们将左指针更改为指向DLL中以前的节点。这个想法很简单，我们按顺序遍历树。为了遍历，我们跟踪之前访问的节点，并将左指针更改为前一个节点。看见 fixPrevPtr（） 具体实施如下。 2) 修正正确的指针 : 以上是直观和简单的。如何更改正确的指针以指向DLL中的下一个节点？这个想法是使用步骤1中固定的左指针。我们从二叉树（BT）中最右边的节点开始。最右边的节点是DLL中的最后一个节点。由于左指针更改为指向DLL中的前一个节点，因此我们可以使用这些指针线性遍历整个DLL。遍历将从最后一个节点到第一个节点。在遍历DLL时，我们会跟踪之前访问的节点，并更改指向前一个节点的右指针。看见 fixNextPtr（） 具体实施如下。
C++
// A simple inorder traversal based // program to convert a Binary Tree to DLL #include <bits/stdc++.h> using namespace std; // A tree node class node { public : int data; node *left, *right; }; // A utility function to create // a new tree node node *newNode( int data) { node *Node = new node(); Node->data = data; Node->left = Node->right = NULL; return (Node); } // Standard Inorder traversal of tree void inorder(node *root) { if (root != NULL) { inorder(root->left); cout << " " << root->data; inorder(root->right); } } // Changes left pointers to work as // previous pointers in converted DLL // The function simply does inorder // traversal of Binary Tree and updates // left pointer using previously visited node void fixPrevPtr(node *root) { static node *pre = NULL; if (root != NULL) { fixPrevPtr(root->left); root->left = pre; pre = root; fixPrevPtr(root->right); } } // Changes right pointers to work // as next pointers in converted DLL node *fixNextPtr(node *root) { node *prev = NULL; // Find the right most node // in BT or last node in DLL while (root && root->right != NULL) root = root->right; // Start from the rightmost node, // traverse back using left pointers. // While traversing, change right pointer of nodes. while (root && root->left != NULL) { prev = root; root = root->left; root->right = prev; } // The leftmost node is head // of linked list, return it return (root); } // The main function that converts // BST to DLL and returns head of DLL node *BTToDLL(node *root) { // Set the previous pointer fixPrevPtr(root); // Set the next pointer and return head of DLL return fixNextPtr(root); } // Traverses the DLL from left to right void printList(node *root) { while (root != NULL) { cout<< " " <<root->data; root = root->right; } } // Driver code int main( void ) { // 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); cout<< " Inorder Tree Traversal" ; inorder(root); node *head = BTToDLL(root); cout << " DLL Traversal" ; printList(head); return 0; } // This code is contributed by rathbhupendra |
C
// A simple inorder traversal based program to convert a Binary Tree to DLL #include<stdio.h> #include<stdlib.h> // A tree node struct node { int data; struct node *left, *right; }; // A utility function to create a new tree node struct node *newNode( int data) { struct node *node = ( struct node *) malloc ( sizeof ( struct node)); node->data = data; node->left = node->right = NULL; return (node); } // Standard Inorder traversal of tree void inorder( struct node *root) { if (root != NULL) { inorder(root->left); printf ( " %d" ,root->data); inorder(root->right); } } // Changes left pointers to work as previous pointers in converted DLL // The function simply does inorder traversal of Binary Tree and updates // left pointer using previously visited node void fixPrevPtr( struct node *root) { static struct node *pre = NULL; if (root != NULL) { fixPrevPtr(root->left); root->left = pre; pre = root; fixPrevPtr(root->right); } } // Changes right pointers to work as next pointers in converted DLL struct node *fixNextPtr( struct node *root) { struct node *prev = NULL; // Find the right most node in BT or last node in DLL while (root && root->right != NULL) root = root->right; // Start from the rightmost node, traverse back using left pointers. // While traversing, change right pointer of nodes. while (root && root->left != NULL) { prev = root; root = root->left; root->right = prev; } // The leftmost node is head of linked list, return it return (root); } // The main function that converts BST to DLL and returns head of DLL struct node *BTToDLL( struct node *root) { // Set the previous pointer fixPrevPtr(root); // Set the next pointer and return head of DLL return fixNextPtr(root); } // Traverses the DLL from left to right void printList( struct node *root) { while (root != NULL) { printf ( " %d" , root->data); root = root->right; } } // Driver program to test above functions int main( void ) { // Let us create the tree shown in above diagram struct 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); printf ( " Inorder Tree Traversal" ); inorder(root); struct node *head = BTToDLL(root); printf ( " DLL Traversal" ); printList(head); return 0; } |
JAVA
// Java program to convert BTT to DLL using // simple inorder traversal public class BinaryTreeToDLL { static class node { int data; node left, right; public node( int data) { this .data = data; } } static node prev; // Changes left pointers to work as previous // pointers in converted DLL The function // simply does inorder traversal of Binary // Tree and updates left pointer using // previously visited node static void fixPrevptr(node root) { if (root == null ) return ; fixPrevptr(root.left); root.left = prev; prev = root; fixPrevptr(root.right); } // Changes right pointers to work // as next pointers in converted DLL static node fixNextptr(node root) { // Find the right most node in // BT or last node in DLL while (root.right != null ) root = root.right; // Start from the rightmost node, traverse // back using left pointers. While traversing, // change right pointer of nodes while (root != null && root.left != null ) { node left = root.left; left.right = root; root = root.left; } // The leftmost node is head of linked list, return it return root; } static node BTTtoDLL(node root) { prev = null ; // Set the previous pointer fixPrevptr(root); // Set the next pointer and return head of DLL return fixNextptr(root); } // Traverses the DLL from left to right static void printlist(node root) { while (root != null ) { System.out.print(root.data + " " ); root = root.right; } } // Standard Inorder traversal of tree static void inorder(node root) { if (root == null ) return ; inorder(root.left); System.out.print(root.data + " " ); inorder(root.right); } public static void main(String[] args) { // Let us create the tree shown in above diagram node 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 ); System.out.println( "Inorder Tree Traversal" ); inorder(root); node head = BTTtoDLL(root); System.out.println( "DLL Traversal" ); printlist(head); } } // This code is contributed by Rishabh Mahrsee |
Python3
# A simple inorder traversal based program to convert a # Binary Tree to DLL # A Binary Tree node class Node: # Constructor to create a new tree node def __init__( self , data): self .data = data self .left = None self .right = None # Standard Inorder traversal of tree def inorder(root): if root is not None : inorder(root.left) print ( " %d" % (root.data),end = " " ) inorder(root.right) # Changes left pointers to work as previous pointers # in converted DLL # The function simply does inorder traversal of # Binary Tree and updates # left pointer using previously visited node def fixPrevPtr(root): if root is not None : fixPrevPtr(root.left) root.left = fixPrevPtr.pre fixPrevPtr.pre = root fixPrevPtr(root.right) # Changes right pointers to work as next pointers in # converted DLL def fixNextPtr(root): prev = None # Find the right most node in BT or last node in DLL while (root and root.right ! = None ): root = root.right # Start from the rightmost node, traverse back using # left pointers # While traversing, change right pointer of nodes while (root and root.left ! = None ): prev = root root = root.left root.right = prev # The leftmost node is head of linked list, return it return root # The main function that converts BST to DLL and returns # head of DLL def BTToDLL(root): # Set the previous pointer fixPrevPtr(root) # Set the next pointer and return head of DLL return fixNextPtr(root) # Traversses the DLL from left to right def printList(root): while (root ! = None ): print ( " %d" % (root.data),end = " " ) root = root.right # Driver program to test above function 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 ) print ( "Inorder Tree Traversal" ) inorder(root) # Static variable pre for function fixPrevPtr fixPrevPtr.pre = None head = BTToDLL(root) print ( "DLL Traversal" ) printList(head) # This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
C#
// C# program to convert BTT to DLL using // simple inorder traversal using System; class GFG { public class node { public int data; public node left, right; public node( int data) { this .data = data; } } public static node prev; // Changes left pointers to work as previous // pointers in converted DLL The function // simply does inorder traversal of Binary // Tree and updates left pointer using // previously visited node public static void fixPrevptr(node root) { if (root == null ) { return ; } fixPrevptr(root.left); root.left = prev; prev = root; fixPrevptr(root.right); } // Changes right pointers to work // as next pointers in converted DLL public static node fixNextptr(node root) { // Find the right most node in // BT or last node in DLL while (root.right != null ) { root = root.right; } // Start from the rightmost node, traverse // back using left pointers. While traversing, // change right pointer of nodes while (root != null && root.left != null ) { node left = root.left; left.right = root; root = root.left; } // The leftmost node is head of // linked list, return it return root; } public static node BTTtoDLL(node root) { prev = null ; // Set the previous pointer fixPrevptr(root); // Set the next pointer and // return head of DLL return fixNextptr(root); } // Traverses the DLL from left to right public static void printlist(node root) { while (root != null ) { Console.Write(root.data + " " ); root = root.right; } } // Standard Inorder traversal of tree public static void inorder(node root) { if (root == null ) { return ; } inorder(root.left); Console.Write(root.data + " " ); inorder(root.right); } public static void Main() { // Let us create the tree // shown in above diagram node 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); Console.WriteLine( "Inorder Tree Traversal" ); inorder(root); node head = BTTtoDLL(root); Console.WriteLine( "DLL Traversal" ); printlist(head); } } // This code is contributed by Shrikant13 |
Javascript
<script> // javascript program to convert BTT to DLL using // simple inorder traversal class node { constructor(val) { this .data = val; this .left = null ; this .right = null ; } } var prev; // Changes left pointers to work as previous // pointers in converted DLL The function // simply does inorder traversal of Binary // Tree and updates left pointer using // previously visited node function fixPrevptr( root) { if (root == null ) return ; fixPrevptr(root.left); root.left = prev; prev = root; fixPrevptr(root.right); } // Changes right pointers to work // as next pointers in converted DLL function fixNextptr( root) { // Find the right most node in // BT or last node in DLL while (root.right != null ) root = root.right; // Start from the rightmost node, traverse // back using left pointers. While traversing, // change right pointer of nodes while (root != null && root.left != null ) { var left = root.left; left.right = root; root = root.left; } // The leftmost node is head of linked list, return it return root; } function BTTtoDLL( root) { prev = null ; // Set the previous pointer fixPrevptr(root); // Set the next pointer and return head of DLL return fixNextptr(root); } // Traverses the DLL from left to right function printlist( root) { while (root != null ) { document.write(root.data + " " ); root = root.right; } } // Standard Inorder traversal of tree function inorder( root) { if (root == null ) return ; inorder(root.left); document.write(root.data + " " ); inorder(root.right); } // Let us create the tree shown in above diagram var 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); document.write( "<br/>Inorder Tree Traversal<br/>" ); inorder(root); var head = BTTtoDLL(root); document.write( "<br/>DLL Traversal<br/>" ); printlist(head); // This code contributed by umadevi9616 </script> |
输出：
Inorder Tree Traversal 25 12 30 10 36 15 DLL Traversal 25 12 30 10 36 15
时间复杂性： O（n），其中n是给定二叉树中的节点数。该解决方案只需对所有二叉树节点进行两次遍历。
本文由 巴拉 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
