二叉查找树转换成排序的双向链表

题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。
比如将二元查找树
10
/
6 14
/ /
4 8 12 16
转换成双向链表4=6=8=10=12=14=16。思路：对于树的很多题目，都可以使用递归的方法来处理。这道题目也不例外。我们从最基本的思路来考虑这个题目。把一个二叉树编程双向链表，最终是一个有序的序列，也就是中序遍历之后的结果，那么当我们采用中序遍历的方式遍历二叉树时，遍历到某个节点，是的前序节点的右指针指向当前节点，然后当前节点的左指针指向前序节点，然后使得前序节点指向当前节点。BinTree* head =NULL;
void helper（BinTree* root,BinTree*& pre）
{
if（root == NULL && root == NULL）
return ;

helper（root->left,pre）;
if（head == NULL）
head = root;
if（pre == NULL）
pre = root;
else
{
root->left = pre;
pre->right = root;
pre = root;
}
//cout<<root->value<<" "<<endl;
helper（root->right,pre）;
}
BinTree* SearchTreeConverstToList（BinTree* root）
{
BinTree* pre = NULL;
helper（root,pre）;
return head;
}思路二：如果对于当前节点，我们把右子树转换成双向链表，然后把左子树转换成双向链表，转换的时候我们都标记了链表的头节点和尾节点，那么我们只需要将当前节点和左子树的尾部相连，和右子树的头部相连即可。void helper_second（BinTree* root,BinTree*& head,BinTree*& tail）
{
if（root==NULL || （root->left == NULL && root->right == NULL））
{
head = root;
tail = root;
return;
}
BinTree* left_head = NULL;
BinTree* left_tail = NULL;
BinTree* right_head = NULL;
BinTree* right_tail = NULL;

helper_second（root->left,left_head,left_tail）;
helper_second（root->right,right_head,right_tail）; if（left_head == NULL）
head = root;
else
{
head = left_head;
left_tail->right = root;
root->right = left_tail;
}
if（right_head == NULL）
tail = root;
else
{
tail = right_tail;
root->right = right_head;
right_head->left = root;
}
}BinTree* ConverstToList（BinTree* root）
{
BinTree* head=NULL;
BinTree* tail = NULL;
helper_second（root,head,tail）;
return head;
}二叉树的常见问题及其解决程序 http://www.linuxidc.com/Linux/2013-04/83661.htm【递归】二叉树的先序建立及遍历 http://www.linuxidc.com/Linux/2012-12/75608.htm在JAVA中实现的二叉树结构 http://www.linuxidc.com/Linux/2008-12/17690.htm【非递归】二叉树的建立及遍历 http://www.linuxidc.com/Linux/2012-12/75607.htm二叉树递归实现与二重指针 http://www.linuxidc.com/Linux/2013-07/87373.htm二叉树先序中序非递归算法 http://www.linuxidc.com/Linux/2014-06/102935.htm轻松搞定面试中的二叉树题目 http://www.linuxidc.com/linux/2014-07/104857.htm本文永久更新链接地址：http://www.linuxidc.com/Linux/2015-04/116799.htm