Convert Ternary Tree to doubly linked list.

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

Solution:

 using System;

namespace LinkedListOpearation
{
    class Program
    {
        public static void Main()
        {
            DoublyLinkedList ternaryTree = new DoublyLinkedList();
            ternaryTree.Root = new Node(1);
            ternaryTree.Root.Left = new Node(110);
            ternaryTree.Root.Middle = new Node(122);
            ternaryTree.Root.Right = new Node(5);
            ternaryTree.Root.Left.Left = new Node(2);
            ternaryTree.Root.Left.Middle = new Node(41);
            ternaryTree.Root.Left.Right = new Node(5);
            ternaryTree.Root.Middle.Left = new Node(14);
            ternaryTree.Root.Middle.Middle = new Node(26);
            ternaryTree.Root.Middle.Right = new Node(18);
            ternaryTree.Root.Right.Left = new Node(3);
            ternaryTree.Root.Right.Middle = new Node(45);
            ternaryTree.Root.Right.Right = new Node(70);
            ternaryTree.ConvertTernaryToDll(ternaryTree.Root);
            ternaryTree.Print();
            Console.ReadLine();
        }
    }


    public class DoublyLinkedList
    {
        public Node Root;
        public Node Head;
        public Node Tail;

        public void ConvertTernaryToDll(Node node)
        {
            if (node == null)
                return;

            Node left = node.Left;
            Node middle = node.Middle;
            Node right = node.Right;

            if (Head == null)
            {
                Head = Tail = node;
                node.Middle = null;
                Head.Left = null;
                Tail.Right = null;
            }
            else
            {
                Tail.Right = node;
                node.Left = Tail;
                node.Middle = null;
                Tail = node;
                Tail.Right = null;
            }

            ConvertTernaryToDll(left);
            ConvertTernaryToDll(middle);
            ConvertTernaryToDll(right);
        }


        public void Print()
        {
            Node current = Head;
            if (Head == null)
                return;

            while (current != null)
            {
                Console.WriteLine(current.Data);
                current = current.Right;
            }
        }
    }

    public class Node
    {
        public int Data;
        public Node Next;
        public Node Left;
        public Node Middle;
        public Node Right;

        public Node(int data)
        {
            Data = data;
        }
    }
} 

Leave a Reply

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