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

1 简介

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

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

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

2 算法思路

• 定义一个Node类，该类代表二叉树中的一个节点。它具有三个属性：左数据和右数据，其中左和右代表节点的两个子代。
• 根将代表二叉树的根。头和尾节点代表双向链表的头和尾。
• BinaryTreeToDLL（）将给定的二叉树转换为相应的双向链表。
  • 通过首先转换左子树来执行二叉树的有序遍历。
  • 如果列表为空，头和尾都将指向一个节点。
  • 如果列表不为空，则该节点将插入列表的末尾。在这里，左，右指针将代表双向链表的上一个和下一个指针。
  • 现在，递归调用BinaryTreeToDLL（）以转换正确的子树。
• 定义一个新节点“current”，该节点将指向头部。
• 打印current.data直到current指向null。
• 当前将在每次迭代中指向列表中的下一个节点。

3 程序实现

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