问：将给定的二叉树转换为双向链表的程序。

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

说明

在此程序中，我们需要将给定的二叉树转换为相应的双向链表。

二叉树是一种树状数据结构，其中每个节点最多有两个子节点。

可以通过以中序遍历的方式来实现，即左子节点 -> 根节点 -> 右子节点。遍历左子树，通过将节点添加到列表末尾来将其转换为双向链表。这样，最左边的节点将成为列表的头。然后，将右子树转换为双向链表。

二叉树

Program to convert a given binary tree to doubly linked list

相应的双向链表

算法

定义一个 Node 类来表示二叉树中的一个节点。它将具有三个属性：data、left 和 right，其中 left 和 right 分别表示节点的两个子节点。
Root 将表示二叉树的根。Head 和 tail 节点分别表示双向链表的头和尾。
BinaryTreeToDLL() 函数可以将给定的二叉树转换为相应的双向链表。
1. 通过先转换左子树来执行二叉树的中序遍历。
2. 如果列表为空，则head和tail都将指向一个节点。
3. 如果列表不为空，则节点将被插入到列表的末尾。在这里，指针 left 和 right 将分别表示双向链表的上一个和下一个指针。
4. 现在，递归调用 BinaryTreeToDLL() 来转换右子树。
display() 将显示列表中存在的所有节点。
1. 定义一个新节点“current”，它将指向头节点。
2. 打印 current.data 直到 current 指向 null。
3. 在每次迭代中，current 将指向列表中的下一个节点。

解决方案

Python

#Represent a node of binary tree
class Node:
    def __init__(self,data):
        self.data = data;
        self.left = None;
        self.right = None;
        
class BinaryTreeToDLL:
    def __init__(self):
        #Represent the root of binary tree
        self.root = None;
        #Represent the head and tail of the doubly linked list
        self.head = None;
        self.tail = None;
        
    #convertbtToDLL() will convert the given binary tree to corresponding doubly linked list
    def convertbtToDLL(self, node):
        #Checks whether node is None
        if(node == None):
            return;
            
        #Convert left subtree to doubly linked list
        self.convertbtToDLL(node.left);
        
        #If list is empty, add node as head of the list
        if(self.head == None):
            #Both head and tail will point to node
            self.head = self.tail = node;
        #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 will become new tail
            self.tail = node;
            
        #Convert right subtree to doubly linked list
        self.convertbtToDLL(node.right);
    
    #display() will print out the nodes of the list
    def display(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;
        
       
bt = BinaryTreeToDLL();
#Add nodes to the binary tree
bt.root = Node(1);
bt.root.left = Node(2);
bt.root.right = Node(3);
bt.root.left.left = Node(4);
bt.root.left.right = Node(5);
bt.root.right.left = Node(6);
bt.root.right.right = Node(7);
 
#Converts the given binary tree to doubly linked list
bt.convertbtToDLL(bt.root);
 
#Displays the nodes present in the list
bt.display();

输出

Nodes of generated doubly linked list: 
4 2 5 1 6 3 7

C

#include <stdio.h>
 
//Represent a node of the binary tree

struct node{
    int data;
    struct node *left;
    struct node *right;
};    
 
//Represent the root of the binary 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, set left and right child to NULL
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    
    return newNode;
}
 
//convertbtToDLL() will convert the given binary tree to corresponding doubly linked list
void convertbtToDLL(struct node *node) {
    //Checks whether node is NULL
    if(node == NULL)
        return;
    
    //Convert left subtree to doubly linked list
    convertbtToDLL(node->left);
    
    //If list is empty, add node as head of the list
    if(head == NULL) {
        //Both head and tail will point to node
        head = tail = node;
    }
    //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 will become new tail
        tail = node;
    }
    
    //Convert right subtree to doubly linked list
    convertbtToDLL(node->right);
}
 
//display() will print out the nodes of the list
void display() {
    //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 binary tree
    root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);
    
    //Converts the given binary tree to doubly linked list
    convertbtToDLL(root);
    
    //Displays the nodes present in the list
    display();    
 
    return 0;
}

输出

Nodes of generated doubly linked list: 
4 2 5 1 6 3 7

JAVA

public class BinaryTreeToDLL {
       //Represent a node of the binary tree
    public static class Node{
        int data;
        Node left;
        Node right;
        
        public Node(int data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }
    
    //Represent the root of the binary tree

    public Node root;
      
    //Represent the head and tail of the doubly linked list
    Node head, tail = null;
    
    //convertbtToDLL() will convert the given binary tree to corresponding doubly linked list
    public void convertbtToDLL(Node node) {
        //Checks whether node is null
        if(node == null)
            return;
        
        //Convert left subtree to doubly linked list
        convertbtToDLL(node.left);
        
        //If list is empty, add node as head of the list
        if(head == null) {
            //Both head and tail will point to node
            head = tail = node;
        }
        //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 will become new tail
            tail = node;
        }
        
        //Convert right subtree to doubly linked list
        convertbtToDLL(node.right);
    }
    
    //display() will print out the nodes of the list
    public void display() {
        //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) {
        
        BinaryTreeToDLL bt = new BinaryTreeToDLL();
        //Add nodes to the binary tree
        bt.root = new Node(1);
        bt.root.left = new Node(2);
        bt.root.right = new Node(3);
        bt.root.left.left = new Node(4);
        bt.root.left.right = new Node(5);
        bt.root.right.left = new Node(6);
        bt.root.right.right = new Node(7);
        
        //Converts the given binary tree to doubly linked list
        bt.convertbtToDLL(bt.root);
        
        //Displays the nodes present in the list
        bt.display();
    }
}

输出

Nodes of generated doubly linked list: 
4 2 5 1 6 3 7

C#

using System; 
namespace DoublyLinkedList 
{                     
    public class Program
    {
        //Represent a node of the binary tree

        public class Node<T>{
            public T data;
            public Node<T> left;
            public Node<T> right;
            
            public Node(T value) {
                data = value;
                left = null;
                right = null;
            }
        }
        
        public class BinaryTreeToDLL<T>{
            //Represent the root of the binary 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;
            
            //convertbtToDLL() will convert the given binary tree to corresponding doubly linked list
            public void convertbtToDLL(Node<T> node) {
                //Checks whether node is null
                if(node == null)
                    return;
 
                //Convert left subtree to doubly linked list
                convertbtToDLL(node.left);
 
                //If list is empty, add node as head of the list
                if(head == null) {
                    //Both head and tail will point to node
                    head = tail = node;
                }
                //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 will become new tail
                    tail = node;
                }
 
                //Convert right subtree to doubly linked list
                convertbtToDLL(node.right);
            }
    
            //display() will print out the nodes of the list
            public void display() {
                //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()
        {
            BinaryTreeToDLL<int> bt = new BinaryTreeToDLL<int>();
            //Add nodes to the binary tree
            bt.root = new Node<int>(1);
            bt.root.left = new Node<int>(2);
            bt.root.right = new Node<int>(3);
            bt.root.left.left = new Node<int>(4);
            bt.root.left.right = new Node<int>(5);
            bt.root.right.left = new Node<int>(6);
            bt.root.right.right = new Node<int>(7);
 
            //Converts the given binary tree to doubly linked list
            bt.convertbtToDLL(bt.root);
 
            //Displays the nodes present in the list
            bt.display();
        }    
    }
}

输出

Nodes of generated doubly linked list: 
4 2 5 1 6 3 7

PHP

<!DOCTYPE html>
<html>
<body>
<?php
//Represent a node of binary tree
class Node{
    public $data;
    public $left;
    public $right;
    
    function __construct($data){
        $this->data = $data;
        $this->left = NULL;
        $this->right = NULL;
    }
}
class BinaryTreeToDLL{
    //Represent the root of binary 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;
    }
    
    //convertbtToDLL() will convert the given binary tree to corresponding doubly linked list
    function convertbtToDLL($node) {
        //Checks whether node is null
        if($node == NULL)
            return;
        
        //Convert left subtree to doubly linked list
        $this->convertbtToDLL($node->left);
        
        //If list is empty, add node as head of the list
        if($this->head == NULL) {
            //Both head and tail will point to node
            $this->head = $this->tail = $node;
        }
        //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 will become new tail
            $this->tail = $node;
        }
        
        //Convert right subtree to doubly linked list
        $this->convertbtToDLL($node->right);
    }
    
    //display() will print out the nodes of the list
    function display() {
        //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>");
    }
}
    
$bt = new BinaryTreeToDLL();
//Add nodes to the binary tree
$bt->root= new Node(1);
$bt->root->left = new Node(2);
$bt->root->right = new Node(3);
$bt->root->left->left = new Node(4);
$bt->root->left->right = new Node(5);
$bt->root->right->left = new Node(6);
$bt->root->right->right = new Node(7);
 
//Converts the given binary tree to doubly linked list
$bt->convertbtToDLL($bt->root);
 
//Displays the nodes present in the list
$bt->display();
?>
</body>
</html>

输出

Nodes of generated doubly linked list: 
4 2 5 1 6 3 7

下一主题#

问：将给定的二叉树转换为双向链表的程序。

说明

算法

解决方案

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

相关帖子

计算两个矩阵之和的程序

确定一个字符串是否为另一个字符串的旋转的程序

查找半圆面积和周长的程序

打印 n 个数的平均值的程序

计算矩阵每行每列之和的程序

查找二叉树所有节点之和的程序

查找字符串中最长和最短单词的程序

将字符串分成 N 个相等部分的程序

从循环链表开头删除新节点的程序

对双向链表元素进行排序的程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器