Python program to create a doubly linked list from a ternary tree.

python tutorials and learn python

Created with Sketch.

Python program to create a doubly linked list from a ternary tree.

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 pre-order fashion that is, root -> left the child -> middle child -> right child. First, traverse root node and add it to the list. Then, add its left, middle and right sub-trees respectively.

Ternary tree:

Python program to create a doubly linked list from a ternary tree

Corresponding doubly linked list:

Python 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 the corresponding doubly linked list.
  • Nodes left, middle and right represent the child of the given node.
  • If the node is not null, then the node will be inserted into the list.
  • If the list is empty, both head and tail will point to a node.
  • 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.
  • 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.

a. displayDLL() will show all the nodes present in the list.

  • Define a new node ‘current’ that will point to the head.
  • Print current.data till current points to null.
  • Current will point to the next node in the list in each iteration.

PROGRAM:

  1. #Represent a node of ternary tree  
  2. class Node:
  3.     def __init__(self,data):
  4.         self.data = data;
  5.         self.left = None;
  6.         self.middle = None;
  7.         self.right = None;
  8. class TernaryTreeToDLL:
  9.     def __init__(self):
  10.         #Represent the root of ternary tree  
  11.         self.root = None;
  12.         #Represent the head and tail of the doubly linked list  
  13.         self.head = None;
  14.         self.tail = None;
  15.     #convertTernaryToDLL() will convert the given ternary tree to corresponding doubly linked list  
  16.     def convertTernaryToDLL(self, node):
  17.         #Checks whether node is None  
  18.         if(node == None):
  19.             return;
  20.         #Keep three pointers to all three children  
  21.         left = node.left;
  22.         middle = node.middle;
  23.         right = node.right;
  24.         #If list is empty then, add node as head of the list  
  25.         if(self.head == None):
  26.             #Both head and tail will point to node  
  27.             self.head = self.tail = node;
  28.             node.middle = None;
  29.             #head’s left will point to None  
  30.             self.head.left = None;
  31.             #tail’s right will point to None, as it is the last node of the list  
  32.             self.tail.right = None;
  33.         #Otherwise, add node to the end of the list  
  34.         else:
  35.             #node will be added after tail such that tail’s right will point to node  
  36.             self.tail.right = node;
  37.             #node’s left will point to tail  
  38.             node.left = self.tail;
  39.             node.middle = None;
  40.             #node will become new tail  
  41.             self.tail = node;
  42.             #As it is last node, tail’s right will point to None  
  43.             self.tail.right = None;
  44.         #Add left child of current node to the list  
  45.         self.convertTernaryToDLL(left);
  46.         #Then, add middle child of current node to the list  
  47.         self.convertTernaryToDLL(middle);
  48.         #Then, add right child of current node to the list  
  49.         self.convertTernaryToDLL(right);
  50.     #displayDLL() will print out the nodes of the list  
  51.     def displayDLL(self):
  52.         #Node current will point to head  
  53.         current = self.head;
  54.         if(self.head == None):
  55.             print(“List is empty”);
  56.             return;
  57.         print(“Nodes of generated doubly linked list: “);
  58.         while(current != None):
  59.             #Prints each node by incrementing pointer.  
  60.             print(current.data),
  61.             current = current.right;
  62. tree = TernaryTreeToDLL();
  63. #Add nodes to the ternary tree  
  64. tree.root = Node(5);
  65. tree.root.left = Node(10);
  66. tree.root.middle = Node(12);
  67. tree.root.right = Node(15);
  68. tree.root.left.left = Node(20);
  69. tree.root.left.middle = Node(40);
  70. tree.root.left.right = Node(50);
  71. tree.root.middle.left = Node(24);
  72. tree.root.middle.middle = Node(36);
  73. tree.root.middle.right = Node(48);
  74. tree.root.right.left = Node(30);
  75. tree.root.right.middle = Node(45);
  76. tree.root.right.right = Node(60);
  77. #Converts the given ternary tree to doubly linked list  
  78. tree.convertTernaryToDLL(tree.root);
  79. #Displays the nodes present in the list  
  80. tree.displayDLL();

Output:

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

Leave a Reply

Your email address will not be published. Required fields are marked *