题目：

输入一颗二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的节点，只能调整树中节点指针的方向：

分析：

1：由于要求链表是有序的，可以借助二叉树中序遍历，因为中序遍历算法的特点就是从小到大访问结点。当遍历访问到根结点时，假设根结点的左侧已经处理好，只需将根结点与上次访问的最近结点（左子树中最大值结点）的指针连接好即可。进而更新当前链表的最后一个结点指针。

2：由于中序遍历过程正好是转换成链表的过程，即可采用递归处理

 

代码：

 

// BT.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include <iostream>#include <math.h>#include <queue>using namespace std;//节点的数据结构class BTree{public:	int       m_nValue;	BTree*    m_nLeft;	BTree*    m_nRight;public:	BTree(int value)	{		m_nValue = http://www.mamicode.com/value;>

 
C++算法之  二叉搜索树转换为双向链表