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());}}?