2. Python程序从三叉树创建一个双向链表。

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

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

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

三叉树

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

相应的双向链表

算法

定义一个Node类，表示三叉树中的一个节点。它将具有四个属性：data、left、middle、right，其中left、middle和right表示节点的三个子节点。
Root表示三叉树的根。Head和tail节点表示双向链表的头和尾。
convertTernaryToDLL()会将给定的三叉树转换为相应的双向链表。

节点left、middle和right表示给定节点的子节点。
如果节点不为null，则将该节点插入列表中。
如果列表为空，则head和tail都将指向一个节点。
如果列表不为空，则将在列表末尾插入节点。这里，left和right指针将分别表示双向链表的previous和next指针。middle将不指向任何东西，因此只需将其设置为null。
当一个节点成功添加到列表中时，将递归调用convertTernaryToDLL()将给定节点的left、middle和right子节点添加到列表中。

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

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

程序

#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 generated doubly linked list: 
5 10 20 40 50 12 24 36 48 15 30 45 60

下一个主题Python 程序

← 上一个下一个 →

2. Python程序从三叉树创建一个双向链表。

算法

程序

联系信息

关注我们

教程

面试题

在线编译器

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 程序

2. Python程序从三叉树创建一个双向链表。

算法

程序

相关帖子

Python 程序打印斐波那契数列（序列）

Python 程序打印数组中的最大元素

Python 程序进行算术运算

Python 程序查找最小公倍数

Python 程序：按字母顺序排序单词

Python 程序打印 1 到 100 之间的所有 Disarium 数

Python 程序在循环链表开头插入一个新节点

Python 程序按升序对数组元素进行排序

Python 程序查找字符的ASCII值

Python 程序打印 1 到 100 之间的所有 Pronic Numbers

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器