二叉搜索树与双向链表

问题描述

输入一颗二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向

思路分析

由于是二叉排序树，其左子树结点值小于根结点，右子树大于根节点，可以利用中序遍历，即先左孩子递归，找到树中最小的节点，然后作为头结点，然后遍历到该左子树最后一个结点，在其后继追加根结点，同样，遍历右子树，得到右子树中的第一个结点，然后将根结点追加到其前继结点即可

码上有戏

public class ConvertTreeToDLinkList {

	static class TreeNode{
		int data;
		TreeNode left;
		TreeNode right;
		
		public TreeNode(int data){
			this.data=data;
		}
	}
	
	public TreeNode Convert(TreeNode root){
		if(root==null) return null;
		if(root.left==null&&root.right==null)
			return root;
		TreeNode LastOfLeftTreeNode=Convert(root.left);
		  TreeNode  p=LastOfLeftTreeNode;
		 //定位到左子树的最后一个结点
		    while(p!=null&&p.right!=null){
		    	p=p.right;
		    }
		    //将根结点追加到左子树最后一个结点
		    if(LastOfLeftTreeNode!=null){
		    	p.right=root;
		    	root.left=p;
		    }
		    TreeNode LastOfRightTreeNode=Convert(root.right);
		      if(LastOfRightTreeNode!=null){
		    	  LastOfRightTreeNode.left=root;
		    	   root.right=LastOfRightTreeNode;
		      }
		      
		      if(LastOfLeftTreeNode!=null)
		    	  return LastOfLeftTreeNode;
		return root;
	}
	
	public static void main(String[] args) {
		TreeNode root=new TreeNode(10);
		TreeNode a=new TreeNode(6);
		TreeNode b=new TreeNode(14);
		TreeNode c=new TreeNode(4);
		TreeNode d=new TreeNode(8);
		TreeNode e=new TreeNode(12);
		TreeNode f=new TreeNode(16);
		
		 root.left=a;
		 root.right=b;
		 a.left=c;
		 a.right=d;
		 b.left=e;
		 b.right=f;
		 
		 TreeNode node=new ConvertTreeToDLinkList().Convert(root);
		 while(node!=null){
			 System.out.println(node.data);
			  node=node.right;
		 }
	}

}