问：程序：将三叉树转换为双向链表。

2025年3月17日 | 阅读 10 分钟

说明

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

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

三叉树

Program to create a doubly linked list from a Ternary Tree

相应的双向链表

算法

定义一个Node类，表示三叉树中的一个节点。它将具有四个属性：data、left、middle、right，其中left、middle和right表示节点的三个子节点。
Root表示三叉树的根。Head和tail节点表示双向链表的头和尾。
convertTernaryToDLL() 函数将给定的三叉树转换为相应的双向链表。
1. left、middle 和 right 节点代表给定节点的子节点。
2. 如果节点不为null，则将该节点插入列表中。
3. 如果列表为空，则head和tail都将指向一个节点。
4. 如果列表不为空，则将在列表末尾插入节点。这里，left和right指针将分别表示双向链表的previous和next指针。middle将不指向任何东西，因此只需将其设置为null。
5. 当一个节点成功添加到列表中时，将递归调用convertTernaryToDLL()将给定节点的left、middle和right子节点添加到列表中。
displayDLL() 函数将显示列表中存在的所有节点。
1. 定义一个新节点“current”，它将指向头节点。
2. 打印 current.data 直到 current 指向 null。
3. 在每次迭代中，current 将指向列表中的下一个节点。

解决方案

Python

#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();

输出

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;
} 

输出

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

JAVA

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

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();
        }    
    }
}

输出

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>

输出

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

下一主题#

问：程序：将三叉树转换为双向链表。

说明

算法

解决方案

Python

C

JAVA

C#

PHP

联系信息

关注我们

教程

面试题

在线编译器

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

程序

问：程序：将三叉树转换为双向链表。

说明

算法

解决方案

Python

C

JAVA

C#

PHP

相关帖子

查找二叉树中距离最远的节点的程序

打印给定数字的排列 (nPr) 的程序

以升序对数组元素进行排序的程序

查找字符串中最长重复序列的程序

对循环链表元素进行排序的程序

从单向链表中删除重复元素的程序

将米转换为厘米的程序

编写计算等腰三角形面积的程序

打印 1 到 100 之间的所有快乐数的程序

使用链表实现二叉树的程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器