题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。比如输入下图中左边儿茶搜索树,则输出转换后的排序双向链表。 10 / \ 6 14 / \ / \ 4 8 12 16 4=6=8=10=12=14=16
将二叉搜索树转化为有序双向链表,类似于中序遍历,中序遍历的结果就是一个排序的数字。因此在程序中以中序遍历树,当遍历左子树到在叶子结点的时候,开始修改指针。
代码实例:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif?x-oss-process=image/resize,w_1400/format,webp)
本文转自xwdreamer博客园博客,原文链接http://www.cnblogs.com/xwdreamer/archive/2012/04/28/2475300.html,如需转载请自行联系原作者