題目：
輸入一棵二元查找樹彩扔，將該二元查找樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只調(diào)整指針的指向。
例如：
10
/ /
6 14
/ / / /
4 8 12 16
轉(zhuǎn)換成雙向鏈表:
4=6=8=10=12=14=16舞吭。
solution1
第一個(gè)解決方案是答案里面提供的，不算是純的c語言解法析珊，使用了c++的引用傳參數(shù)羡鸥，而且結(jié)果也并不是雙向鏈表，而是一個(gè)單向鏈表忠寻，代碼如下：
<pre><code>
include<stdio.h>
include<stdlib.h>
//定義樹節(jié)點(diǎn)
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);
//傳入父節(jié)點(diǎn)指針和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
{
//鏈接左節(jié)點(diǎn)
if((pCurrent->m_nValue)>value)
{
addBSTreeNode(pCurrent->m_pleft,value);
}
else if((pCurrent->m_nValue)<value)
{
addBSTreeNode(pCurrent->m_pright,value);
}
else
{
printf("重復(fù)的節(jié)點(diǎn)\n");
}
}
//遍歷二元查找樹
void ergodicBSTree(BSTreeNode *pCurrent){
if(NULL==pCurrent){
return;
}
//有左節(jié)點(diǎn)惧浴，則進(jìn)入左節(jié)點(diǎn)分支
if(NULL != pCurrent->m_pleft){
ergodicBSTree(pCurrent->m_pleft);
}
//節(jié)點(diǎn)接到鏈表尾部
convertToDoubleList(pCurrent);
//有右節(jié)點(diǎn)，則進(jìn)入有右節(jié)點(diǎn)分支
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>
總結(jié)：這段代碼需要使用g++來編譯
solution2
純c的代碼奕剃，第二個(gè)solution我比較中意衷旅，他構(gòu)造了一個(gè)很清晰的遞歸原則，轉(zhuǎn)換過程只需要傳入根節(jié)點(diǎn)纵朋，返回鏈表首節(jié)點(diǎn)：
- 如果左子樹不為null芜茵，處理左子樹
1.a）遞歸轉(zhuǎn)化左子樹為雙向鏈表；
1.b）找出根結(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)（是左子樹的最右的節(jié)點(diǎn)）
1.c）將上一步找出的節(jié)點(diǎn)和根結(jié)點(diǎn)連接起來 - 如果右子樹不為null倡蝙，處理右子樹（和上面的很類似）
1.a）遞歸轉(zhuǎn)化右子樹為雙向鏈表九串；
1.b）找出根結(jié)點(diǎn)的后繼節(jié)點(diǎn)（是右子樹的最左的節(jié)點(diǎn)）
1.c）將上一步找出的節(jié)點(diǎn)和根結(jié)點(diǎn)連接起來 - 找到最左邊的節(jié)點(diǎn)并返回
源代碼如下：
<pre><code>
include "stdio.h"
include "stdlib.h"
typedef struct Node{
int data;
struct Node *left;
struct Node *right;
}Node;
//新建一顆樹，返回根節(jié)點(diǎn)
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;
}
//輸入根節(jié)點(diǎn)寺鸥，返回轉(zhuǎn)換成雙向鏈表的子節(jié)點(diǎn)的頭部
Node change(Node root){
//base case
if(!root)
return NULL;
//轉(zhuǎn)換左子樹猪钮，連接到根節(jié)點(diǎn)
if(root->left!=NULL){
//找到最小值
Node left=change(root->left);
for (;left->right!=NULL;left=left->right);
left->right=root;
root->left=left;
}
//轉(zhuǎn)換右子樹，根節(jié)點(diǎn)連接到右子樹
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>
總結(jié)：遞歸比較難想胆建，要明白這幾句的意思：
//找到左子樹里面最大值烤低，就是左子樹的最右邊的值，讓他和root的左邊雙向連接起來
for (;left->right!=NULL;left=left->right);
left->right=root;
root->left=left;