给定一棵二叉树，将其转换为循环双链表（就地）。
null
- 在转换后的循环链表中，节点中的左指针和右指针分别用作上一个和下一个指针。
- 列表中节点的顺序必须与给定二叉树的顺序相同。
- 顺序遍历的第一个节点必须是循环列表的头节点。
例子：
可以使用以下步骤来描述这个想法。 1） 编写一个通用函数，将两个给定的循环双列表连接起来（该函数将在下面解释）。 2） 现在遍历给定的树 ….a） 递归地将左子树转换为循环DLL。将转换后的列表设为leftList。 ….a） 递归地将右子树转换为循环DLL。将转换后的列表设为rightList。 ….c） 制作一个树根的循环链表，使树根的左右指向自身。 ….d） 将leftList与单个根节点的列表连接起来。 ….e） 将上面（d）步中生成的列表与rightList连接起来。 请注意，上面的代码以后序方式遍历树。我们也可以以有序的方式穿越。我们可以先将左子树和根连接起来，然后对右子树进行递归，并将结果与左根连接起来。
如何连接两个循环DLL？
- 获取左侧列表的最后一个节点。检索最后一个节点是一个O（1）操作，因为头部的prev指针指向列表的最后一个节点。
- 将其与右侧列表的第一个节点连接
- 获取第二个列表的最后一个节点
- 将其与列表的开头连接起来。
下面是上述想法的实现。
C++
// C++ Program to convert a Binary Tree // to a Circular Doubly Linked List #include<iostream> using namespace std; // To represents a node of a Binary Tree struct Node { struct Node *left, *right; int data; }; // A function that appends rightList at the end // of leftList. Node *concatenate(Node *leftList, Node *rightList) { // If either of the list is empty // then return the other list if (leftList == NULL) return rightList; if (rightList == NULL) return leftList; // Store the last Node of left List Node *leftLast = leftList->left; // Store the last Node of right List Node *rightLast = rightList->left; // Connect the last node of Left List // with the first Node of the right List leftLast->right = rightList; rightList->left = leftLast; // Left of first node points to // the last node in the list leftList->left = rightLast; // Right of last node refers to the first // node of the List rightLast->right = leftList; return leftList; } // Function converts a tree to a circular Linked List // and then returns the head of the Linked List Node *bTreeToCList(Node *root) { if (root == NULL) return NULL; // Recursively convert left and right subtrees Node *left = bTreeToCList(root->left); Node *right = bTreeToCList(root->right); // Make a circular linked list of single node // (or root). To do so, make the right and // left pointers of this node point to itself root->left = root->right = root; // Step 1 (concatenate the left list with the list // with single node, i.e., current node) // Step 2 (concatenate the returned list with the // right List) return concatenate(concatenate(left, root), right); } // Display Circular Link List void displayCList(Node *head) { cout << "Circular Linked List is :" ; Node *itr = head; do { cout << itr->data << " " ; itr = itr->right; } while (head!=itr); cout << "" ; } // Create a new Node and return its address Node *newNode( int data) { Node *temp = new Node(); temp->data = data; temp->left = temp->right = NULL; return temp; } // Driver Program to test above function 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 = bTreeToCList(root); displayCList(head); return 0; } |
JAVA
// Java Program to convert a Binary Tree to a // Circular Doubly Linked List // Node class represents a Node of a Tree class Node { int val; Node left,right; public Node( int val) { this .val = val; left = right = null ; } } // A class to represent a tree class Tree { Node root; public Tree() { root = null ; } // concatenate both the lists and returns the head // of the List public Node concatenate(Node leftList,Node rightList) { // If either of the list is empty, then // return the other list if (leftList == null ) return rightList; if (rightList == null ) return leftList; // Store the last Node of left List Node leftLast = leftList.left; // Store the last Node of right List Node rightLast = rightList.left; // Connect the last node of Left List // with the first Node of the right List leftLast.right = rightList; rightList.left = leftLast; // left of first node refers to // the last node in the list leftList.left = rightLast; // Right of last node refers to the first // node of the List rightLast.right = leftList; // Return the Head of the List return leftList; } // Method converts a tree to a circular // Link List and then returns the head // of the Link List public Node bTreeToCList(Node root) { if (root == null ) return null ; // Recursively convert left and right subtrees Node left = bTreeToCList(root.left); Node right = bTreeToCList(root.right); // Make a circular linked list of single node // (or root). To do so, make the right and // left pointers of this node point to itself root.left = root.right = root; // Step 1 (concatenate the left list with the list // with single node, i.e., current node) // Step 2 (concatenate the returned list with the // right List) return concatenate(concatenate(left, root), right); } // Display Circular Link List public void display(Node head) { System.out.println( "Circular Linked List is :" ); Node itr = head; do { System.out.print(itr.val+ " " ); itr = itr.right; } while (itr != head); System.out.println(); } } // Driver Code class Main { public static void main(String args[]) { // Build the tree Tree tree = new Tree(); 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 ); // head refers to the head of the Link List Node head = tree.bTreeToCList(tree.root); // Display the Circular LinkedList tree.display(head); } } |
Python3
# Python3 Program to convert a Binary # Tree to a Circular Doubly Linked List class newNode: def __init__( self , data): self .data = data self .left = self .right = None # A function that appends rightList # at the end of leftList. def concatenate(leftList, rightList): # If either of the list is empty # then return the other list if (leftList = = None ): return rightList if (rightList = = None ): return leftList # Store the last Node of left List leftLast = leftList.left # Store the last Node of right List rightLast = rightList.left # Connect the last node of Left List # with the first Node of the right List leftLast.right = rightList rightList.left = leftLast # Left of first node points to # the last node in the list leftList.left = rightLast # Right of last node refers to # the first node of the List rightLast.right = leftList return leftList # Function converts a tree to a circular # Linked List and then returns the head # of the Linked List def bTreeToCList(root): if (root = = None ): return None # Recursively convert left and # right subtrees left = bTreeToCList(root.left) right = bTreeToCList(root.right) # Make a circular linked list of single # node (or root). To do so, make the # right and left pointers of this node # point to itself root.left = root.right = root # Step 1 (concatenate the left list # with the list with single # node, i.e., current node) # Step 2 (concatenate the returned list # with the right List) return concatenate(concatenate(left, root), right) # Display Circular Link List def displayCList(head): print ( "Circular Linked List is :" ) itr = head first = 1 while (head ! = itr or first): print (itr.data, end = " " ) itr = itr.right first = 0 print () # Driver Code if __name__ = = '__main__' : 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 ) head = bTreeToCList(root) displayCList(head) # This code is contributed by PranchalK |
C#
// C# Program to convert a Binary Tree // to a Circular Doubly Linked List using System; // Node class represents a Node of a Tree public class Node { public int val; public Node left, right; public Node( int val) { this .val = val; left = right = null ; } } // A class to represent a tree public class Tree { internal Node root; public Tree() { root = null ; } // concatenate both the lists // and returns the head of the List public virtual Node concatenate(Node leftList, Node rightList) { // If either of the list is empty, // then return the other list if (leftList == null ) { return rightList; } if (rightList == null ) { return leftList; } // Store the last Node of left List Node leftLast = leftList.left; // Store the last Node of right List Node rightLast = rightList.left; // Connect the last node of Left List // with the first Node of the right List leftLast.right = rightList; rightList.left = leftLast; // left of first node refers to // the last node in the list leftList.left = rightLast; // Right of last node refers to // the first node of the List rightLast.right = leftList; // Return the Head of the List return leftList; } // Method converts a tree to a circular // Link List and then returns the head // of the Link List public virtual Node bTreeToCList(Node root) { if (root == null ) { return null ; } // Recursively convert left // and right subtrees Node left = bTreeToCList(root.left); Node right = bTreeToCList(root.right); // Make a circular linked list of single // node (or root). To do so, make the // right and left pointers of this node // point to itself root.left = root.right = root; // Step 1 (concatenate the left list with // the list with single node, // i.e., current node) // Step 2 (concatenate the returned list // with the right List) return concatenate(concatenate(left, root), right); } // Display Circular Link List public virtual void display(Node head) { Console.WriteLine( "Circular Linked List is :" ); Node itr = head; do { Console.Write(itr.val + " " ); itr = itr.right; } while (itr != head); Console.WriteLine(); } } // Driver Code public class GFG { public static void Main( string [] args) { // Build the tree Tree tree = new Tree(); 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); // head refers to the head of the Link List Node head = tree.bTreeToCList(tree.root); // Display the Circular LinkedList tree.display(head); } } // This code is contributed by Shrikant13 |
Javascript
<script> // javascript Program to convert a Binary Tree to a // Circular Doubly Linked List // Node class represents a Node of a Tree class Node { constructor(val) { this .val = val; this .left = null ; this .right = null ; } } // A class to represent a var root = null ; // concatenate both the lists and returns the head // of the List function concatenate(leftList, rightList) { // If either of the list is empty, then // return the other list if (leftList == null ) return rightList; if (rightList == null ) return leftList; // Store the last Node of left List var leftLast = leftList.left; // Store the last Node of right List var rightLast = rightList.left; // Connect the last node of Left List // with the first Node of the right List leftLast.right = rightList; rightList.left = leftLast; // left of first node refers to // the last node in the list leftList.left = rightLast; // Right of last node refers to the first // node of the List rightLast.right = leftList; // Return the Head of the List return leftList; } // Method converts a to a circular // Link List and then returns the head // of the Link List function bTreeToCList(root) { if (root == null ) return null ; // Recursively convert left and right subtrees var left = bTreeToCList(root.left); var right = bTreeToCList(root.right); // Make a circular linked list of single node // (or root). To do so, make the right and // left pointers of this node point to itself root.left = root.right = root; // Step 1 (concatenate the left list with the list // with single node, i.e., current node) // Step 2 (concatenate the returned list with the // right List) return concatenate(concatenate(left, root), right); } // Display Circular Link List function display(head) { document.write( "Circular Linked List is :<br/>" ); var itr = head; do { document.write(itr.val + " " ); itr = itr.right; } while (itr != head); document.write(); } // Driver Code // Build the 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); // head refers to the head of the Link List var head = bTreeToCList(root); // Display the Circular LinkedList display(head); // This code contributed by umadevi9616 </script> |
输出：
Circular Linked List is : 25 12 30 10 36 15
本文由 希拉格·阿加瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
