C-Sharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript | SQL | PHP | Angular | HTML
Q. Program to create a doubly linked list from a Ternary Tree.ExplanationIn 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
SolutionPython#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 JAVApublic 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#
|