Java 从三叉树创建双向链表的程序

17 Mar 2025 | 4 分钟阅读

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

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

三叉树

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

相应的双向链表

算法

定义一个Node类，表示三叉树中的一个节点。它将具有四个属性：data、left、middle、right，其中left、middle和right表示节点的三个子节点。
Root表示三叉树的根。Head和tail节点表示双向链表的头和尾。
convertTernaryToDLL()将把给定的三叉树转换为相应的双向链表。
- Nodes left、middle和right表示给定节点的子节点。
- 如果节点不为null，则将该节点插入列表中。
- 如果列表为空，则head和tail都将指向一个节点。
- 如果列表不为空，则将在列表末尾插入节点。这里，left和right指针将分别表示双向链表的previous和next指针。middle将不指向任何东西，因此只需将其设置为null。
- 当一个节点成功添加到列表中时，将递归调用convertTernaryToDLL()将给定节点的left、middle和right子节点添加到列表中。

a. displayDLL()将显示列表中存在的所有节点。

定义一个新节点“current”，它将指向头节点。
打印 current.data 直到 current 指向 null。
在每次迭代中，current 将指向列表中的下一个节点。

程序

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

下一个主题Java 程序

Java 从三叉树创建双向链表的程序

算法

程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java 程序

Java 从三叉树创建双向链表的程序

算法

程序

相关帖子

如何在 Java 中将对象转换为字符串

如何在 Java 中将十进制转换为十六进制

Java Program to Find Largest of Three Numbers

如何在 Java 中将 int 转换为 long

Java 中的标签内容提取器问题

Duck Number Java

Peterson Number in Java

Java 中的二分搜索

Java 中的阿姆斯特朗数

Java Program to Display Even Numbers From 1 to 100

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器