三叉树转换为双向链表的Java程序

1 简介

在此程序中，给定的三叉树将被转换为相应的双向链表。

三叉树是一个分层的数据结构，其中每个节点最多可以有三个孩子。这可以通过以一种预定的方式遍历三叉树来实现，即根->左子->中间子->右子。首先，遍历根节点并将其添加到列表中。然后，分别添加其左，中和右子树。

三元树：

对应的双向链表：

2 算法思路

• 定义一个Node类，该类代表三叉树中的一个节点。它具有四个属性：数据，左，中，右，其中左，中和右表示节点的三个子级。
• 根将代表三元树的根。头和尾节点代表双向链表的头和尾。
• convertTernaryToDLL（）会将给定的三叉树转换为相应的双向链表。
  • 左，中和右节点代表给定节点的子节点。
  • 如果该节点不为空，则该节点将被插入到列表中。
  • 如果列表为空，头和尾都将指向一个节点。
  • 如果列表不为空，则该节点将插入列表的末尾。在这里，左，右指针将代表双向链表的上一个和下一个指针。中间不会指向任何内容，因此，只需将其设置为null。
  • 将节点成功添加到列表中后，请递归调用convertTernaryToDLL（）以将给定节点的左，中和右子级添加到列表中。
• 定义一个新节点“current”，该节点将指向头部。
• 打印current.data直到current指向null。
• 当前将在每次迭代中指向列表中的下一个节点。

3 程序实现

/**
 * 一点教程网： http://www.yiidian.com
 */
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();  
    }  
}  

输出结果为：

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