微软面试题：树转化为双链表

前言:只是为了加深自己对面试题的理解，如果有做的错的，请指出，感激。

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

CSDN上有一个http://blog.csdn.net/v_JULY_v 里面有微软面试一百题，大家感兴趣的话可以去那里汲取营养，并且自己code，加深理解。

代码实现是使用java实现的，我用了好长时间的C#，但是现在绝大部分公司要求java，所以就开始学习java了。　　

 1 public class BSTreeNode
 2 {
 3     /** value of node
 4      * */
 5      public int m_nValue;
 6      /**左子树也是指向前面节点
 7       * */
 8     public BSTreeNode leftSon;
 9      /**右子树也是指向后面节点
10       * */
11     public BSTreeNode rightSon;
12     public void setValue(int value)
13     {
14         m_nValue=value;
15     }
16     public BSTreeNode()
17     {
18         leftSon=null;
19         rightSon=null;
20     }
21 }

　　可以通过注释观察到，转换成双链表后，leftSon指向前驱，rightson指向后继，树的结构完全丧失。

　　假设一个二叉树根节点为A，左子树为B，右子树为C，转换之后为A=B=C，它是通过中序遍历，就是二叉树的转换成双向链表。

　　可以通过递归实现，对于树节点A，可以先把他的左子树转换成双向链表LB，再把它的右子树转换双向链表LC，A在LB和LC的中间，把LB，LC和A合并，就形成了新的双向链表。

　　代码实现也比较容易，关键是测试，用java写了一个生成树的代码，通过下面第三行，定义了一个接口类型的变量，这个在设计模式里面是叫做策略模式，把类中可能出现出现变化的分离出去，通过新的接口实现。

1     public BSTreeNode root; 
2     private int initHelper;
3     private IBTreeBuilder i_btBuilder;
4

　　总结：好久没有写java代码了，这次代码认识到了java的几个知识点：

　　1一个java文件中只可能有一个public类(内部类除外)

　　2java中没有struct这种数据结构。

　　3java不像C#有ref或者out关键字，可以对变量进行引用。

下为效果图：

微软面试题：树转化为双链表

由于java代码对于文件的格式要求比较强，所以代码请下载文件。

秒客网

微软面试题：树转化为双链表

相关文章