C++ code to convert a binary tree to a circular doubly linked list.














































C++ code to convert a binary tree to a circular doubly linked list.



/*C++ Program to convert a Binary Tree to a Circular Doubly Linked List Input is given in the main function and the output will be: 61 14 5 65 80 43 3 41 20 54 Description: The left and right pointers in the node are used as previous and next pointers in circular linked list. The order of display is used as Inorder in the list. Thus, keeping the root node of the tree as the head node of the list. Rest of the info is written as comments in the code itself. */ #include<iostream> using namespace std; struct Dlist { struct Dlist *left, *right; int data; }; Dlist *append(Dlist *leftlist, Dlist *rightlist)//Appends right list to the end of left list { if (leftlist == NULL) return rightlist; if (rightlist == NULL) return leftlist; Dlist *leftlast = leftlist->left; Dlist*rightlast = rightlist->left; leftlast->right = rightlist; rightlist->left = leftlast; leftlist->left = rightlast; rightlast->right = leftlist; return leftlist; } Dlist*btree_to_clist(Dlist *root) //convert tree to circular link list { if (root == NULL) return NULL; Dlist*left = btree_to_clist(root->left); Dlist*right = btree_to_clist(root->right); root->left = root->right = root; return append(append(left, root), right); } Dlist*new_node(int data) { Dlist*tmp = new Dlist(); tmp->data = data; tmp->left = tmp->right = NULL; return tmp; } void display_clist(Dlist *head)//Display the clist { cout << "Circular Linked List is :\n"; Dlist *ptr = head; do { cout <<ptr->data <<" "; ptr = ptr->right; } while (head!=ptr); cout << "\n"; } int main() { Dlist*root = new_node(43); root->left = new_node(5); root->right = new_node(20); root->left->left = new_node(14); root->left->right = new_node(65); root->right->left = new_node(41); root->right->right = new_node(54); root->left->right->right = new_node(80); root->right->left->left = new_node(3); root->left->left->left = new_node(61); Dlist*head = btree_to_clist(root); display_clist(head); return 0; }

More Articles of Ankur Jain:

Name Views Likes
C++ code to convert a binary tree to a circular doubly linked list. 219 20

Comments