Java实现将二元查找树转变成排序的双向链表

一直觉得自己算法和数据结构方面很欠缺，最近放寒假在家里没事，看见网上的这道题目，所以就编写了下，就当作给今年找工作练练手吧，随便也提高下自己这方面的知识。

题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。

比如将二元查找树

                              

转换成双向链表      4=6=8=10=12=14=16

题目来源：

http://zhedahht.blog.163.com/blog/static/254111742007127104759245/

链接中的解决方法其实已经说的很清楚了，并且用C实现了，我只不过是依葫芦画瓢用Java实现了一把。具体解决方案如下：（直接从以上链接中复制的）

当我们到达某一结点准备调整以该结点为根结点的子树时，先调整其左子树将左子树转换成一个排好序的左子链表，再调整其右子树转换右子链表。最近链接左子链表的最右结点（左子树的最大结点）、当前结点和右子链表的最左结点（右子树的最小结点）。从树的根结点开始递归调整所有结点。

package tree;

/**
 * 代表树中的单个结点
 * @author DHC
 *
 */
public class Node {
	
	public Node(int str) {
		content = str;
	}
	
	private int content;
	
	private Node left;
	
	private Node right;

	public Node getLeft() {
		return left;
	}

	public void setLeft(Node left) {
		this.left = left;
	}

	public Node getRight() {
		return right;
	}

	public int getContent() {
		return content;
	}

	public void setContent(int content) {
		this.content = content;
	}

	public void setRight(Node right) {
		this.right = right;
	}
}

package tree;

/**
 * 代表有结点形成的树，要将其变为双向链表
 * @author DHC
 *
 */
public class Tree {
	
	public static Node rootNode = new Node(10);
	
	static {
		Node node6 = new Node(6);
		Node node4 = new Node(4);
		Node node8 = new Node(8);
		Node node14 = new Node(14);
		Node node12 = new Node(12);
		Node node16 = new Node(16);
		rootNode.setLeft(node6);
		rootNode.setRight(node14);
		node6.setLeft(node4);
		node6.setRight(node8);
		node14.setLeft(node12);
		node14.setRight(node16);	
	}
	public Node getRootNode () {
		return rootNode;
	}
}

package tree;

/**
 * 将树转变为双向链表
 * @author DHC
 *
 */
public class TreeToList {
	
	private Node convert(Node rootNode, boolean isRight) {
		if (rootNode == null) {
			return null;
		}
		
		Node leftNode = rootNode.getLeft();
		Node rightNode = rootNode.getRight();
		
		// 左右节点为空
		if (leftNode != null) {
			Node leftResultNode = convert(leftNode, false);
			if (leftResultNode != null) {
				rootNode.setLeft(leftResultNode);
				leftResultNode.setRight(rootNode);
			}
		}
		
		if (rightNode != null) {
			Node rightResultNode = convert(rightNode, true);
			if (rightResultNode != null) {
				rightResultNode.setLeft(rootNode);
				rootNode.setRight(rightResultNode);
			}
		}
		
		
		Node tempNode = rootNode;
		
		if (isRight) {
			if (leftNode != null) {
				tempNode = leftNode;
			}
		} else {
			if (rightNode != null) {
				tempNode =  rightNode;
			}
		}
		
		return tempNode;
	}
	
	public static void main(String[] args) {
		TreeToList treeToList = new TreeToList();
		treeToList.convert(Tree.rootNode, true);
		
		System.out.println(Tree.rootNode.getLeft().getLeft().getLeft().getContent());
		System.out.println(Tree.rootNode.getLeft().getLeft().getContent());
		System.out.println(Tree.rootNode.getLeft().getContent());
		System.out.println(Tree.rootNode.getContent());
		System.out.println(Tree.rootNode.getRight().getContent());
		System.out.println(Tree.rootNode.getRight().getRight().getContent());
		System.out.println(Tree.rootNode.getRight().getRight().getRight().getContent());
	}

}