Create a Doubly Linked List from a Ternary Tree in C++
In this tutorial, we are going to learn how to create a doubly linked list from a ternary tree in C++. Here we will learn about the ternary tree, doubly linked list, and how to create a doubly linked list from a ternary tree. After that we will see the C++ program for the same.
Ternary Tree
A ternary tree is a data structure in which each node has at most three children.
Ternary means composed of three parts. So, in a ternary tree, the parent node can have at most three child nodes, which are often called as the ‘left’, ‘middle’, and ‘right’ node, respectively. The structure of a node is defined as:-
struct node{ int val; struct node *left; struct node *middle; struct node *right; };
Here, the variables ‘left’ points to the left subtree, ‘middle’ points to the middle subtree, and ‘right’ points to the right subtree. The variable ‘val’ stores the value or data of a node. Let us see an example:-
1
/ | \
/ | \
2 6 10
/ | \ / | \ / | \
3 4 5 7 8 9 11 12 13
Doubly Linked List
A doubly-linked list is a data structure that contains sequentially linked records i.e. nodes. It is a variation of a singly linked list. In the doubly linked list we can move or traverse in both the direction forward as well as backward. The structure of a node is defined as:-
struct node { int val; struct node* next; struct node* prev; };
Here, the variable ‘next’ points to the next node, and the variable ‘prev’ points to the previous node. The variable ‘val’ stores the value or data of a node. Let us see an example:-
null<–>1<–>2<–>3<–>4<–>5<–>6<–>7<–>8<–>9<–>10<–>11<–>12<–>13<–>null
Algorithm to create a doubly linked list from a ternary tree
We can create a doubly linked list from the ternary tree by using any of the following traversal:-
- Using pre-order traversal.
- Using in-order traversal.
- Or, using post-order traversal.
Here, we will create a doubly-linked list from the given ternary tree by storing the pre-order traversal of the given ternary tree. So, here are the steps to create a doubly linked list from a ternary tree:-
- Create a ternary tree with any number of nodes.
- Create an empty doubly-linked list with head and tail pointers.
- Perform the pre-order traversal of the ternary tree.
- While performing the pre-order traversal, append the current node in the doubly-linked list simultaneously.
- At last, our doubly linked list is created from a ternary tree and it contains the pre-order traversal of the ternary tree.
C++ program to create a doubly linked list from ternary tree
So, here is the C++ implementation of the above algorithm:-
#include<bits/stdc++.h> using namespace std; //Structure of a node of the ternary tree struct TreeNode { int val; TreeNode *left; TreeNode *middle; TreeNode *right; }; TreeNode *head=NULL, *tail = NULL; /*===================================================== FUNCTION TO CONVERT TERNARY TREE TO DOUBLY LINKED LIST =======================================================*/ void create_doubly_from_ternary(TreeNode *root) { // Check node is null or not.If it is null then return if(!root) return; //storing the address of left child TreeNode *left_subtree = root->left; //storing the address of middle child TreeNode *middle_subtree = root->middle; //storing the address of right child TreeNode *right_subtree = root->right; if(head == NULL) // If list is empty { // Make head and tail equal to root; head = tail = root; //And store null in root->middle,head->left //& tail->right root->middle = head->left = tail->right = NULL; } //If list is not empty else { //insert new node after tail tail->right = root; //And store tail address in root->left to maintain //doubly linked list property root->left = tail; root->middle = NULL; //root will become new tail tail = root; //And tail->right should be null tail->right = NULL; } //Recursively call left subtree create_doubly_from_ternary(left_subtree); //Recursively call middle subtree create_doubly_from_ternary(middle_subtree); //Recursively call right subtree create_doubly_from_ternary(right_subtree); } /*============================================ FUNCTION TO DISPLAY THE DOUBLY LINKED LIST =============================================*/ void display_doubly_linked_list() { TreeNode *ptr = head; if(head == NULL) //Checking for empty list { cout<<"Your list is empty"<<endl; return; } cout<<"New converted doubly linked list is:"<<endl<<endl; cout<<"null"; while(ptr != NULL) //Terminate when ptr==NULL { cout<<" <-> "<<ptr->val; ptr = ptr->right; //Increment ptr to right } cout<<" <-> null"<<endl; } /*=========================================== FUNCTION TO CREATE NEW NODE FOR TERNARY TREE ============================================*/ TreeNode* makeTreeNode(int data) { TreeNode *newTreeNode = new TreeNode(); newTreeNode->val = data; return newTreeNode; } /*====================================== MAIN FUNCTION =======================================*/ int main() { TreeNode *root; //Make a ternary tree by calling //function makeTreeNode() root = makeTreeNode(1); root->left = makeTreeNode(2); root->left->left = makeTreeNode(3); root->left->middle = makeTreeNode(4); root->left->right = makeTreeNode(5); root->middle = makeTreeNode(6); root->middle->left = makeTreeNode(7); root->middle->middle = makeTreeNode(8); root->middle->right = makeTreeNode(9); root->right = makeTreeNode(10); root->right->left = makeTreeNode(11); root->right->middle = makeTreeNode(12); root->right->right = makeTreeNode(13); //Representation of input tree // 1 // / | \ // / | \ // 2 6 10 // / | \ / | \ / | \ // 3 4 5 7 8 9 11 12 13 //Calling converting function that create doubly //linked list from ternary tree create_doubly_from_ternary(root); //Calling display function to print final //converted doubly linked list display_doubly_linked_list(); return 0; }
Output:-
New converted doubly linked list is: null <-> 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 <-> 7 <-> 8 <-> 9 <-> 10 <-> 11 <-> 12 <-> 13 <-> null
Thanks for reading this tutorial. I hope it helps you !!
Leave a Reply