将二叉树结构转换为双向链表 java语言实现

小灰灰 2022-08-12 00:16 102阅读 0赞

import java.util.ArrayList;
    
    
    public class TreeToList 
    {
    	public static void main(String args[])
    	{
    		TreeToList ttl=new TreeToList();
    		int[]a=new int[]{8,6,9,5,7,8,12};
    		Nodel head=ttl.creatTree(a);
    		ttl.setList(head);
    	}
    	private Nodel creatTree(int[]b)
    	{
    		ArrayList<Nodel> arrayList=new ArrayList<Nodel>();
    		for(int i=0;i<b.length;i++)
    		{
    			Nodel node=new Nodel(b[i]);
    			arrayList.add(node);
    		}
    		for(int i=0;i<b.length/2;i++)
    		{
    			Nodel root=arrayList.get(i);
    			int leftIndex=i*2+1;
    			if(leftIndex<b.length)
    			{
    				root.setLeft(arrayList.get(leftIndex));
    			}
    			int rightIndex=leftIndex+1;
    			if(rightIndex<b.length)
    			{
    				root.setRight(arrayList.get(rightIndex));
    			}
    		}
    		Nodel head=arrayList.get(0);
    		return head;
    	}
    	//创建一颗二叉树
    	private Nodel previous;
    	private void setList(Nodel node)
    	{
    		if(node!=null)
    		{
    			this.setList(node.left);
    			if(this.previous!=null)
    			{
    				previous.right=node;
    				node.left=previous;
    			}
    			this.previous=node;
    			this.setList(node.right);
    		}
    		
    		//形成双向链表
    		
    		while(node!=null)
    		{
    			node=node.left;
    		}
    		while(node!=null)
    		{
    			System.out.print(node.x);
    			node=node.right;
    		}
    	}
    }
    class Nodel
    {
    	Nodel left;
    	int x;
    	Nodel right;
    	public Nodel(int x)
    	{
    		this.x =x;
    	}
    	
    	public void setLeft(Nodel left)
    	{
    		this.left = left;
    	}
    
    	public void setRight(Nodel right) 
    	{
    		this.right = right;
    	}
    }