把二元查找树转变成排序的双向链表

分析：二叉树中序遍历即可得到一个有序的结果，只要按照中序遍历的顺序把二叉树节点依次放入双向链表中即可。这里以原有二叉树节点的左序节点表示前驱，右子节点表示后继。

 

具体源码如下：

二叉树节点类：

package convertBSTreeToDList;

public class BSTreeNode {

	int data;
	BSTreeNode left;
	BSTreeNode right;
	public BSTreeNode(int data){
		this.data =data;
		this.right=null;
		this.left=null;
	}
}

 

二叉树：

package convertBSTreeToDList;



public class BSTree {
	private BSTreeNode root;
	
	public BSTree(BSTreeNode node){
		this.setRoot(node);
	}
	
	public void setRoot(BSTreeNode root) {
		this.root = root;
	}
	public BSTreeNode getRoot() {
		return root;
	}
	
	/**
	 * 忽略已经存在该值的节点
	 */
	public  void insert(BSTreeNode root,BSTreeNode node){
		if(root == null)
			root = node;
		if(root.data>node.data){
			if(root.left!=null)
				insert(node,root.left);
			root.left = node;
		}
		
		if(root.data<node.data){
			if(root.right!=null)
				insert(node,root.right);
			root.right = node;
		}
	}
	
	public void displayInOrder(BSTreeNode root){
		if(root == null)
			return;
		if(root.left!=null)
			displayInOrder(root.left);
		
		System.out.print(root.data+" ");
		
		if(root.right!=null)
			displayInOrder(root.right);
	}
}

 

双向链表类：

package convertBSTreeToDList;

public class DList {

	/**
	 * 双向链表头结点
	 */
	private BSTreeNode head;
	/**
	 * 双向链表当前结点 也就是双向链表的尾节点
	 */
	private BSTreeNode current;
	
	public DList(BSTreeNode head){
		this.setHead(head);
	}
	
	/**
	 * 插入一个新二叉树节点到双向链表，并返回双向链表的当前节点
	 */
	public BSTreeNode insertDListNode(BSTreeNode node){
		
		if(current == null){
			head = node;
			current = node;
			return current;
			}
		
		current.right = node;
		node.left = current;
		current = current.right;
		return current;
	}
	
	public void setHead(BSTreeNode head) {
		this.head = head;
	}
	public BSTreeNode getHead() {
		return head;
	}
	public void setCurrent(BSTreeNode current) {
		this.current = current;
	}
	public BSTreeNode getCurrent() {
		return current;
	}

}

 

转换工具类：

package convertBSTreeToDList;

public class BSTree2DListConvertutil {
	
	/**
	 * 二叉树到双向链表的转化
	 * 将二叉树的中序遍历结果放入一个双向链表中即可
	 * @param root
	 * @param dlist
	 */
	public static void convert(BSTreeNode root,DList dlist){

		if(root ==null)
			return;
		
		if(root.left!=null)
			convert(root.left,dlist);
	
		dlist.insertDListNode(root);
		
		if(root.right!=null)
			convert(root.right,dlist);
		
	}
	/**
	 * 双向链表的正向打印
	 * @param dlist
	 */
	public static void displayAfterConvert(DList dlist){
		BSTreeNode head = dlist.getHead();
		if(head !=null)
			System.out.print(head.data);
		head = head.right;
		while(head!=null){
			System.out.print("-->"+head.data);
			head = head.right;
		}
	}
	/**
	 * 反向打印双向链表，就是从尾打向头，为了便于观看，这里巧用了stringBuffer的reverse方法
	 * @param dlist
	 * @return
	 */
	public static String reverseDisplay(DList dlist){
		BSTreeNode current  = dlist.getCurrent();
		StringBuilder sb = new StringBuilder();
		
		while(current!=null){
			sb.append(current.data);
			if(current.left!=null)
				sb.append("--<");
			current = current.left;
		}
		sb.reverse();
		return sb.toString();
	}

}

 

测试类：

package convertBSTreeToDList;

public class BSTree2DListConvertTest {

	public static void main(String[]args){
		BSTreeNode head = null;
		DList dlist = new DList(head);
		int [] demo = {5,9,2,7,11,1,4};
		BSTreeNode node = new BSTreeNode(demo[0]);
		BSTree t = new BSTree(node);
		for(int i=1;i<demo.length;i++){
			node = new BSTreeNode(demo[i]);
			t.insert(t.getRoot(), node);
		}
		System.out.println("二叉树遍历如下：");
		t.displayInOrder(t.getRoot());
		System.out.println();
		System.out.println("-------------");
		
		BSTree2DListConvertutil.convert(t.getRoot(),dlist);
		System.out.println("双向链表正向遍历如下：");
		BSTree2DListConvertutil.displayAfterConvert(dlist);
		System.out.println();
		System.out.println("双向链表反向遍历如下：");
		String result = BSTree2DListConvertutil.reverseDisplay(dlist);
		System.out.println(result);
	}
}

 

测试结果如下：

二叉树遍历如下：
1 2 4 5 7 9 11
-------------
双向链表正向遍历如下：
1-->2-->4-->5-->7-->9-->11
双向链表反向遍历如下：
1<--2<--4<--5<--7<--9<--11

 

总结：要点在于对二叉查找树的性质要熟悉。