微软，google等面试50题（01）---把二元查找树转变成排序的双向链表[数据结构]
把二元查找树转变成排序的双向链表
题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
10
/ \
6 15
/ \ / \
3 7 12 16
转换成双向链表
3=6=7=10=12=15=16
思路：中序遍历二叉树，将上次访问的节点记为previous，当前访问的节点记为current。对于遍历过程中的每个当前节点，让该节点的左指针指向previous(current->left = previous)，让previous的右指针，指向当前节点(previous->right = current)，然后将previous更新为current。当中序遍历结束时，二叉搜索树也
被转化为双链表了。
代码：
public static void main(String[] args) { BSTreeToLinkedList bn=new BSTreeToLinkedList(); int[] a={10,6,15,3,7,12,16};//这些数据是按二叉查找树的层次遍历存放 Node head=bn.creatTree(a); bn.toTwoWayLinkedList(head); bn.printTwoLinkedList(head); } private Node previous; public void toTwoWayLinkedList(Node node){ if(node!=null){ toTwoWayLinkedList(node.getLeft()); if(previous!=null){ previous.setRight(node); node.setLeft(previous); } previous=node; toTwoWayLinkedList(node.getRight()); } } public void printTwoLinkedList(Node node){ if(node!=null){ //after converting to List,head=a[0]=10,but the head is not the actually head of list. //the true head is 4. while(node.getLeft()!=null){ node=node.getLeft();//find the true Head. } while(node!=null){ System.out.print(node.getData()+" "); node=node.getRight(); } } } public Node creatTree(int[] data){ List<Node> nodeList=new ArrayList<Node>(); for(int each:data){ Node node=new Node(each); nodeList.add(node); } int lastRootIndex=data.length/2-1; for(int i=lastRootIndex;i>=0;i--){ int leftIndex=i*2+1; Node root=nodeList.get(i); Node left=nodeList.get(leftIndex); root.setLeft(left); if(leftIndex+1<data.length){ Node right=nodeList.get(leftIndex+1); root.setRight(right); } } Node head=nodeList.get(0); return head; } } class Node{ private int data; private Node left; private Node right; public Node(int i){ data=i; } public int getData() { return data; } public void setData(int data) { this.data = data; } public Node getLeft() { return left; } public void setLeft(Node left) { this.left = left; } public Node getRight() { return right; } public void setRight(Node right) { this.right = right; } }