Q:

Program to create a doubly linked list from a Ternary Tree

belongs to collection: Doubly Linked List Programs

robaa
Save to bookmark
|
2022-11-10
|
  286 
0

Explanation

In this program, The given ternary tree will be converted into a corresponding doubly linked list.

The ternary tree is a hierarchical data structure in which each node can have at most three children. This can be accomplished by traversing the ternary tree in a preorder fashion that is, root -> left child -> middle child -> right child. First, traverse root node and add it to the list. Then, add its left, middle and right subtrees respectively.

Ternary tree:

Corresponding doubly linked list:

Algorithm

  1. Define a Node class which represents a node in the ternary tree. It will have four properties: data, left, middle, right where left, middle and right represent three children of a node.
  2. Root will represent the root of the ternary tree. Head and tail node represent the head and tail of the doubly linked list.
  3. convertTernaryToDLL() will convert the given ternary tree to corresponding doubly linked list.
    1. Nodes left, middle and right represent the child of given node.
    2. If the node is not null, then the node will be inserted into the list.
    3. If the list is empty, both head and tail will point to a node.
    4. If the list is not empty then, the node will be inserted at the end of the list. Here, pointer left, and right will represent the previous and next pointer of the doubly linked list. The middle will not point to anything hence, simply set it to null.
    5. When a node is successfully added into the list then, call convertTernaryToDLL() recursively to add a left, middle and right child of given node to the list.
  4. displayDLL() will show all the nodes present in the list.
    1. Define a new node 'current' that will point to the head.
    2. Print current.data till current points to null.
    3. Current will point to the next node in the list in each iteration.

Input:

 

#Add nodes to the ternary tree  

tree.root = Node(5);  

tree.root.left = Node(10);  

tree.root.middle = Node(12);  

tree.root.right = Node(15);  

tree.root.left.left = Node(20);  

tree.root.left.middle = Node(40);  

tree.root.left.right = Node(50);  

tree.root.middle.left = Node(24);  

tree.root.middle.middle = Node(36);  

tree.root.middle.right = Node(48);  

tree.root.right.left = Node(30);  

tree.root.right.middle = Node(45);  

tree.root.right.right = Node(60);   

Output:

Nodes of the generated doubly linked list: 5 10 20 40 50 12 24 36 48 15 30 45 60
Python programming, Php programming, Java programming, C programming, c# programming, examples, Python programming examples, Php programming examples, Java programming examples, C programming examples, c# programming examples,
login and add your own answer to this question

All Answers

robaa
2022-11-10
need an explanation for this answer? contact us directly to get an explanation for this answer

Python

#Represent a node of ternary tree  
class Node:  
    def __init__(self,data):  
        self.data = data;  
        self.left = None;  
        self.middle = None;  
        self.right = None;  
          
class TernaryTreeToDLL:  
    def __init__(self):  
        #Represent the root of ternary tree  
        self.root = None;  
        #Represent the head and tail of the doubly linked list  
        self.head = None;  
        self.tail = None;  
          
    #convertTernaryToDLL() will convert the given ternary tree to corresponding doubly linked list  
    def convertTernaryToDLL(self, node):  
        #Checks whether node is None  
        if(node == None):  
            return;  
              
        #Keep three pointers to all three children  
        left = node.left;  
        middle = node.middle;  
        right = node.right;  
          
        #If list is empty then, add node as head of the list  
        if(self.head == None):  
            #Both head and tail will point to node  
            self.head = self.tail = node;  
            node.middle = None;  
            #head's left will point to None  
            self.head.left = None;  
            #tail's right will point to None, as it is the last node of the list  
            self.tail.right = None;  
        #Otherwise, add node to the end of the list  
        else:  
            #node will be added after tail such that tail's right will point to node  
            self.tail.right = node;  
            #node's left will point to tail  
            node.left = self.tail;  
            node.middle = None;  
            #node will become new tail  
            self.tail = node;  
            #As it is last node, tail's right will point to None  
            self.tail.right = None;  
              
        #Add left child of current node to the list  
        self.convertTernaryToDLL(left);  
        #Then, add middle child of current node to the list  
        self.convertTernaryToDLL(middle);  
        #Then, add right child of current node to the list  
        self.convertTernaryToDLL(right);  
      
    #displayDLL() will print out the nodes of the list  
    def displayDLL(self):  
        #Node current will point to head  
        current = self.head;  
        if(self.head == None):  
            print("List is empty");  
            return;  
        print("Nodes of generated doubly linked list: ");  
        while(current != None):  
            #Prints each node by incrementing pointer.  
            print(current.data),  
            current = current.right;  
              
tree = TernaryTreeToDLL();  
#Add nodes to the ternary tree  
tree.root = Node(5);  
tree.root.left = Node(10);  
tree.root.middle = Node(12);  
tree.root.right = Node(15);  
tree.root.left.left = Node(20);  
tree.root.left.middle = Node(40);  
tree.root.left.right = Node(50);  
tree.root.middle.left = Node(24);  
tree.root.middle.middle = Node(36);  
tree.root.middle.right = Node(48);  
tree.root.right.left = Node(30);  
tree.root.right.middle = Node(45);  
tree.root.right.right = Node(60);  
   
#Converts the given ternary tree to doubly linked list  
tree.convertTernaryToDLL(tree.root);  
   
#Displays the nodes present in the list  
tree.displayDLL();

 

Output:

Nodes of the generated doubly linked list: 

5 10 20 40 50 12 24 36 48 15 30 45 60

 

C

#include <stdio.h>  
   
//Represent a node of the ternary tree  
  
struct node{  
    int data;  
    struct node *left;  
    struct node *middle;  
    struct node *right;  
};      
   
//Represent the root of the ternary tree  
  
struct node *root;  
      
//Represent the head and tail of the doubly linked list  
struct node *head, *tail = NULL;  
   
//createNode() will create a new node  
struct node* createNode(int data){  
    //Create a new node  
    struct node *newNode = (struct node*)malloc(sizeof(struct node));  
    //Assign data to newNode  
    newNode->data = data;  
   
    return newNode;  
}  
   
//convertTernaryToDLL() will convert the given ternary tree to corresponding doubly linked list  
void convertTernaryToDLL(struct node *node) {  
    //Checks whether node is NULL  
    if(node == NULL)  
        return;  
      
    //Keep three pointers to all three children  
    struct node *left = node->left;  
    struct node *middle = node->middle;  
    struct node *right = node->right;  
      
    //If list is empty then, add node as head of the list  
    if(head == NULL) {  
        //Both head and tail will point to node  
        head = tail = node;  
        node->middle = NULL;  
        //head's left will point to NULL  
        head->left = NULL;  
        //tail's right will point to NULL, as it is the last node of the list  
        tail->right = NULL;  
    }  
    //Otherwise, add node to the end of the list  
    else {  
        //node will be added after tail such that tail's right will point to node  
        tail->right = node;  
        //node's left will point to tail  
        node->left = tail;  
        node->middle = NULL;  
        //node will become new tail  
        tail = node;  
        //As it is last node, tail's right will point to NULL  
        tail->right = NULL;  
    }  
      
    //Add left child of current node to the list  
    convertTernaryToDLL(left);  
    //Then, add middle child of current node to the list  
    convertTernaryToDLL(middle);  
    //Then, add right child of current node to the list  
    convertTernaryToDLL(right);  
}  
   
//displayDLL() will print out the nodes of the list  
void displayDLL() {  
    //Node current will point to head  
    struct node *current = head;  
    if(head == NULL) {  
        printf("List is empty\n");  
        return;  
    }  
    printf("Nodes of generated doubly linked list: \n");  
    while(current != NULL) {  
        //Prints each node by incrementing pointer.  
        printf("%d ",current->data);  
        current = current->right;  
    }  
    printf("\n");  
}  
      
int main()  
{  
    //Add nodes to the ternary tree  
    root = createNode(5);  
    root->left = createNode(10);  
    root->middle = createNode(12);  
    root->right = createNode(15);  
    root->left->left = createNode(20);  
    root->left->middle = createNode(40);  
    root->left->right = createNode(50);  
    root->middle->left = createNode(24);  
    root->middle->middle = createNode(36);  
    root->middle->right = createNode(48);  
    root->right->left = createNode(30);  
    root->right->middle = createNode(45);  
    root->right->right = createNode(60);  
      
    //Converts the given ternary tree to doubly linked list  
    convertTernaryToDLL(root);  
      
    //Displays the nodes present in the list  
    displayDLL();      
   
    return 0;  
}

 

Output:

Nodes of generated doubly linked list: 
5 10 20 40 50 12 24 36 48 15 30 45 60

 

JAVA

public class TernaryTreeToDLL {  
      
    //Represent a node of ternary tree  
    public static class Node{  
        int data;  
        Node left;  
        Node middle;  
        Node right;  
          
        public Node(int data) {  
            this.data = data;  
        }  
    }  
      
    //Represent the root of the ternary tree  
  
    public Node root;  
       
    //Represent the head and tail of the doubly linked list  
    Node head, tail = null;  
      
    //convertTernaryToDLL() will convert the given ternary tree to corresponding doubly linked list  
    public void convertTernaryToDLL(Node node) {  
        //Checks whether node is null  
        if(node == null)  
            return;  
          
        //Keep three pointers to all three children  
        Node left = node.left;  
        Node middle = node.middle;  
        Node right = node.right;  
          
        //If list is empty then, add node as head of the list  
        if(head == null) {  
            //Both head and tail will point to node  
            head = tail = node;  
            node.middle = null;  
            //head's left will point to null  
            head.left = null;  
            //tail's right will point to null, as it is the last node of the list  
            tail.right = null;  
        }  
        //Otherwise, add node to the end of the list  
        else {  
            //node will be added after tail such that tail's right will point to node  
            tail.right = node;  
            //node's left will point to tail  
            node.left = tail;  
            node.middle = null;  
            //node will become new tail  
            tail = node;  
            //As it is last node, tail's right will point to null  
            tail.right = null;  
        }  
          
        //Add left child of current node to the list  
        convertTernaryToDLL(left);  
        //Then, add middle child of current node to the list  
        convertTernaryToDLL(middle);  
        //Then, add right child of current node to the list  
        convertTernaryToDLL(right);  
    }  
      
    //displayDLL() will print out the nodes of the list  
    public void displayDLL() {  
        //Node current will point to head  
        Node current = head;  
        if(head == null) {  
            System.out.println("List is empty");  
            return;  
        }  
        System.out.println("Nodes of generated doubly linked list: ");  
        while(current != null) {  
            //Prints each node by incrementing the pointer.  
  
            System.out.print(current.data + " ");  
            current = current.right;  
        }  
        System.out.println();  
    }  
      
    public static void main(String[] args) {  
          
        TernaryTreeToDLL tree = new TernaryTreeToDLL();  
        //Add nodes to the ternary tree  
        tree.root = new Node(5);  
        tree.root.left = new Node(10);  
        tree.root.middle = new Node(12);  
        tree.root.right = new Node(15);  
        tree.root.left.left = new Node(20);  
        tree.root.left.middle = new Node(40);  
        tree.root.left.right = new Node(50);  
        tree.root.middle.left = new Node(24);  
        tree.root.middle.middle = new Node(36);  
        tree.root.middle.right = new Node(48);  
        tree.root.right.left = new Node(30);  
        tree.root.right.middle = new Node(45);  
        tree.root.right.right = new Node(60);  
          
        //Converts the given ternary tree to doubly linked list  
        tree.convertTernaryToDLL(tree.root);  
          
        //Displays the nodes present in the list  
        tree.displayDLL();  
    }  
}

 

Output:

Nodes of generated doubly linked list: 
5 10 20 40 50 12 24 36 48 15 30 45 60

 

C#

using System;   
namespace DoublyLinkedList   
{                       
    public class Program  
    {  
        //Represent a node of ternary tree  
        public class Node<T>{  
            public T data;  
            public Node<T> left;  
            public Node<T> middle;  
            public Node<T> right;  
              
            public Node(T value) {  
                data = value;  
            }  
        }  
          
        public class TernaryTreeToDLL<T>{  
            //Represent the root of the ternary tree  
  
            public Node<T> root;  
              
            //Represent the head and tail of the doubly linked list  
            public Node<T> head = null;               
             public Node<T> tail = null;  
              
            //convertTernaryToDLL() will convert the given ternary tree to corresponding doubly linked list  
            public void convertTernaryToDLL(Node<T> node) {  
                //Checks whether node is null  
                if(node == null)  
                    return;  
   
                //Keep three pointers to all three children  
                Node<T> left = node.left;  
                Node<T> middle = node.middle;  
                Node<T> right = node.right;  
   
                //If list is empty then, add node as head of the list  
                if(head == null) {  
                    //Both head and tail will point to node  
                    head = tail = node;  
                    node.middle = null;  
                    //head's left will point to null  
                    head.left = null;  
                    //tail's right will point to null, as it is the last node of the list  
                    tail.right = null;  
                }  
                //Otherwise, add node to the end of the list  
                else {  
                    //node will be added after tail such that tail's right will point to node  
                    tail.right = node;  
                    //node's left will point to tail  
                    node.left = tail;  
                    node.middle = null;  
                    //node will become new tail  
                    tail = node;  
                    //As it is last node, tail's right will point to null  
                    tail.right = null;  
                }  
   
                //Add left child of current node to the list  
                convertTernaryToDLL(left);  
                //Then, add middle child of current node to the list  
                convertTernaryToDLL(middle);  
                //Then, add right child of current node to the list  
                convertTernaryToDLL(right);  
            }  
      
            //displayDLL() will print out the nodes of the list  
            public void displayDLL() {  
                //Node current will point to head  
                Node<T> current = head;  
                if(head == null) {  
                    Console.WriteLine("List is empty");  
                    return;  
                }  
                Console.WriteLine("Nodes of generated doubly linked list: ");  
                while(current != null) {  
                    //Prints each node by incrementing the pointer.  
  
                    Console.Write(current.data + " ");  
                    current = current.right;  
                }  
                Console.WriteLine();  
            }  
        }  
          
        public static void Main()  
        {  
            TernaryTreeToDLL<int> tree = new TernaryTreeToDLL<int>();  
            //Add nodes to the ternary tree  
            tree.root = new Node<int>(5);  
            tree.root.left = new Node<int>(10);  
            tree.root.middle = new Node<int>(12);  
            tree.root.right = new Node<int>(15);  
            tree.root.left.left = new Node<int>(20);  
            tree.root.left.middle = new Node<int>(40);  
            tree.root.left.right = new Node<int>(50);  
            tree.root.middle.left = new Node<int>(24);  
            tree.root.middle.middle = new Node<int>(36);  
            tree.root.middle.right = new Node<int>(48);  
            tree.root.right.left = new Node<int>(30);  
            tree.root.right.middle = new Node<int>(45);  
            tree.root.right.right = new Node<int>(60);  
   
            //Converts the given ternary tree to doubly linked list  
            tree.convertTernaryToDLL(tree.root);  
   
            //Displays the nodes present in the list  
            tree.displayDLL();  
        }      
    }  
}

 

Output:

Nodes of generated doubly linked list: 
5 10 20 40 50 12 24 36 48 15 30 45 60

 

PHP

<!DOCTYPE html>  
<html>  
<body>  
<?php  
//Represent a node of ternary tree  
class Node{  
    public $data;  
    public $left;  
    public $middle;  
    public $right;  
      
    function __construct($data){  
        $this->data = $data;  
    }  
}  
class TernaryTreeToDLL{  
    //Represent the root of ternary tree      
    public $root;  
    //Represent the head and tail of the doubly linked list  
    public $head;  
    public $tail;  
    function __construct(){  
        $this->head = NULL;  
        $this->tail = NULL;  
        $this->root = NULL;  
    }  
      
    //convertTernaryToDLL() will convert the given ternary tree to corresponding doubly linked list  
    function convertTernaryToDLL($node) {  
        //Checks whether node is NULL  
        if($node == NULL)  
            return;  
          
        //Keep three pointers to all three children  
        $left = $node->left;  
        $middle = $node->middle;  
        $right = $node->right;  
          
        //If list is empty then, add node as head of the list  
        if($this->head == NULL) {  
            //Both head and tail will point to node  
            $this->head = $this->tail = $node;  
            $node->middle = NULL;  
            //head's left will point to NULL  
            $this->head->left = NULL;  
            //tail's right will point to NULL, as it is the last node of the list  
            $this->tail->right = NULL;  
        }  
        //Otherwise, add node to the end of the list  
        else {  
            //node will be added after tail such that tail's right will point to node  
            $this->tail->right = $node;  
            //node's left will point to tail  
            $node->left = $this->tail;  
            $node->middle = NULL;  
            //node will become new tail  
            $this->tail = $node;  
            //As it is last node, tail's right will point to NULL  
            $this->tail->right = NULL;  
        }  
          
        //Add left child of current node to the list  
        $this->convertTernaryToDLL($left);  
        //Then, add middle child of current node to the list  
        $this->convertTernaryToDLL($middle);  
        //Then, add right child of current node to the list  
        $this->convertTernaryToDLL($right);  
    }  
      
    //displayDLL() will print out the nodes of the list  
    function displayDLL() {  
        //Node current will point to head  
        $current = $this->head;  
        if($this->head == NULL) {  
            print("List is empty <br>");  
            return;  
        }  
        print("Nodes of generated doubly linked list: <br>");  
        while($current != NULL) {  
            //Prints each node by incrementing pointer.  
            print($current->data . " ");  
            $current = $current->right;  
        }  
        print("<br>");  
    }  
}  
      
$tree = new TernaryTreeToDLL();  
//Add nodes to the ternary tree  
$tree->root= new Node(5);  
$tree->root->left = new Node(10);  
$tree->root->middle = new Node(12);  
$tree->root->right = new Node(15);  
$tree->root->left->left = new Node(20);  
$tree->root->left->middle = new Node(40);  
$tree->root->left->right = new Node(50);  
$tree->root->middle->left = new Node(24);  
$tree->root->middle->middle = new Node(36);  
$tree->root->middle->right = new Node(48);  
$tree->root->right->left = new Node(30);  
$tree->root->right->middle = new Node(45);  
$tree->root->right->right = new Node(60);  
   
//Converts the given ternary tree to doubly linked list  
$tree->convertTernaryToDLL($tree->root);  
   
//Displays the nodes present in the list  
$tree->displayDLL();  
?>  
</body>  
</html>

 

 

Output:

Nodes of generated doubly linked list: 
5 10 20 40 50 12 24 36 48 15 30 45 60

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Doubly Linked List Programs
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Program to create a doubly linked list of n nodes ... >>
<< Program to convert a given binary tree to doubly l...