Create a Doubly Linked List from a Ternary Tree in C++
By Dinesh KumarIn 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