题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。
例如：
10
/ /
6 14
/ / / /
4 8 12 16
转换成双向链表:
4=6=8=10=12=14=16。
solution1
第一个解决方案是答案里面提供的，不算是纯的c语言解法，使用了c++的引用传参数，而且结果也并不是双向链表，而是一个单向链表，代码如下：
<pre><code>
include<stdio.h>
include<stdlib.h>
//定义树节点
typedef struct BSTreeNode{
int m_nValue; //value of node
struct BSTreeNode *m_pleft;
struct BSTreeNode *m_pright;
} BSTreeNode;
typedef BSTreeNode DoubleList;
DoubleList *pHead;
DoubleList *pListIndex;
void convertToDoubleList(BSTreeNode *pCurrent);
//传入父节点指针和value
void addBSTreeNode(BSTreeNode* &pCurrent, int value)
{
if (NULL==pCurrent)
{
//c++使用new
//BSTreeNode *pBSTree=new BSTreeNode();
BSTreeNode *pBSTree=(BSTreeNode *)malloc(sizeof(BSTreeNode));
pBSTree->m_nValue=value;
pBSTree->m_pleft=NULL;
pBSTree->m_pright=NULL;
pCurrent = pBSTree;
}
else
{
//链接左节点
if((pCurrent->m_nValue)>value)
{
addBSTreeNode(pCurrent->m_pleft,value);
}
else if((pCurrent->m_nValue)<value)
{
addBSTreeNode(pCurrent->m_pright,value);
}
else
{
printf("重复的节点\n");
}
}
//遍历二元查找树
void ergodicBSTree(BSTreeNode *pCurrent){
if(NULL==pCurrent){
return;
}
//有左节点，则进入左节点分支
if(NULL != pCurrent->m_pleft){
ergodicBSTree(pCurrent->m_pleft);
}
//节点接到链表尾部
convertToDoubleList(pCurrent);
//有右节点，则进入有右节点分支
if(NULL != pCurrent->m_pright){
ergodicBSTree(pCurrent->m_pright);
}
}
void convertToDoubleList(BSTreeNode *pCurrent){
pCurrent->m_pleft=pListIndex;
if(NULL !=pListIndex)
{
pListIndex->m_pright =pCurrent;
}
else
{
pHead=pCurrent;
}
printf("the value is %d\n",pCurrent->m_nValue);
}
int main(){
BSTreeNode *pRoot=NULL;
pListIndex=NULL;
pHead=NULL;
addBSTreeNode(pRoot,10);
addBSTreeNode(pRoot,4);
addBSTreeNode(pRoot,6);
addBSTreeNode(pRoot,8);
addBSTreeNode(pRoot,12);
addBSTreeNode(pRoot,14);
addBSTreeNode(pRoot,15);
ergodicBSTree(pRoot);
printf("the end\n");
return 0;
}
</code></pre>
总结：这段代码需要使用g++来编译
solution2
纯c的代码，第二个solution我比较中意，他构造了一个很清晰的递归原则，转换过程只需要传入根节点，返回链表首节点：
- 如果左子树不为null，处理左子树
1.a）递归转化左子树为双向链表；
1.b）找出根结点的前驱节点（是左子树的最右的节点）
1.c）将上一步找出的节点和根结点连接起来 - 如果右子树不为null，处理右子树（和上面的很类似）
1.a）递归转化右子树为双向链表；
1.b）找出根结点的后继节点（是右子树的最左的节点）
1.c）将上一步找出的节点和根结点连接起来 - 找到最左边的节点并返回
源代码如下：
<pre><code>
include "stdio.h"
include "stdlib.h"
typedef struct Node{
int data;
struct Node *left;
struct Node *right;
}Node;
//新建一颗树，返回根节点
Node * create(){
Node *root;
Node *p4=(Node *)malloc(sizeof(Node));
Node *p8=(Node *)malloc(sizeof(Node));
Node *p6=(Node *)malloc(sizeof(Node));
Node *p12=(Node *)malloc(sizeof(Node));
Node *p16=(Node *)malloc(sizeof(Node));
Node *p14=(Node *)malloc(sizeof(Node));
Node *p10=(Node *)malloc(sizeof(Node));
Node *p1=(Node *)malloc(sizeof(Node));
Node *p5=(Node *)malloc(sizeof(Node));
Node *p18=(Node )malloc(sizeof(Node));
p4->data=4;
p8->data=8;
p6->data=6;
p12->data=12;
p16->data=16;
p14->data=14;
p10->data=10;
p1->data=1;
p5->data=5;
p18->data=18;
p4->left=p1;
p4->right=p5;
p16->right=p18;
p6->left=p4;
p6->right=p8;
p10->left=p6;
p10->right=p14;
p14->left=p12;
p14->right=p16;
root=p10;
return p10;
}
//输入根节点，返回转换成双向链表的子节点的头部
Node change(Node root){
//base case
if(!root)
return NULL;
//转换左子树，连接到根节点
if(root->left!=NULL){
//找到最小值
Node left=change(root->left);
for (;left->right!=NULL;left=left->right);
left->right=root;
root->left=left;
}
//转换右子树，根节点连接到右子树
if(root->right!=NULL){
Node* right=change(root->right);
for(;right->left!=NULL;right=right->left);
right->left=root;
root->right=right;
}
return root;
}
Node * treeto2list(Node *root){
if (root==NULL){
return root;
}
root = change(root);
while (root->left!=NULL)
root = root->left;
return root;
}
int main(){
Node *root=create();
Node *head = treeto2list(root);
Node *tail=NULL;
while(head){
printf("the number is %d\n",head->data);
tail=head;
head=head->right;
}
printf("反向\n");
while(tail){
printf("the number is %d\n",tail->data);
tail=tail->left;
}
return 0;
}
</code></pre>
总结：递归比较难想，要明白这几句的意思：
//找到左子树里面最大值，就是左子树的最右边的值，让他和root的左边双向连接起来
for (;left->right!=NULL;left=left->right);
left->right=root;
root->left=left;