TheDeveloperBlog.com

Home | Contact Us

C-Sharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript | SQL | PHP | Angular | HTML

Program to Create a Doubly Linked List From a Ternary Tree

Program to Create a Doubly Linked List From a Ternary Tree on fibonacci, factorial, prime, armstrong, swap, reverse, search, sort, stack, queue, array, linkedlist, tree, graph etc.

<< Back to PROGRAM

Q. Program to create a doubly linked list from a Ternary Tree.

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:

Program to create a doubly linked list from a Ternary Tree

Corresponding doubly linked list:

Program to create a doubly linked list from a Ternary Tree

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.

Solution

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

Next Topic#




Related Links:

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

Related Links

Adjectives Ado Ai Android Angular Antonyms Apache Articles Asp Autocad Automata Aws Azure Basic Binary Bitcoin Blockchain C Cassandra Change Coa Computer Control Cpp Create Creating C-Sharp Cyber Daa Data Dbms Deletion Devops Difference Discrete Es6 Ethical Examples Features Firebase Flutter Fs Git Go Hbase History Hive Hiveql How Html Idioms Insertion Installing Ios Java Joomla Js Kafka Kali Laravel Logical Machine Matlab Matrix Mongodb Mysql One Opencv Oracle Ordering Os Pandas Php Pig Pl Postgresql Powershell Prepositions Program Python React Ruby Scala Selecting Selenium Sentence Seo Sharepoint Software Spellings Spotting Spring Sql Sqlite Sqoop Svn Swift Synonyms Talend Testng Types Uml Unity Vbnet Verbal Webdriver What Wpf