劍指OFFER之二叉搜索樹與雙向鏈表（九度OJ1503）

題目描述：

輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點，只能調整樹中結點指針的指向。

 

輸入：

輸入可能包含多個測試樣例。
對於每個測試案例，輸入的第一行為一個數n(0<n<1000)，代表測試樣例的個數。
接下來的n行，每行為一個二叉搜索樹的先序遍歷序列，其中左右子樹若為空則用0代替。

 

輸出：

對應每個測試案例，
輸出將二叉搜索樹轉換成排序的雙向鏈表後，從鏈表頭至鏈表尾的遍歷結果。

 

樣例輸入：

1
2 1 0 0 3 0 0

樣例輸出：

1 2 3

解題思路：

　　這道題應該是最近寫的最繁瑣的一道題了。

　　首先輸入按規則來，需要進行前序遍歷輸入

void createTree(BTree **b){  
    int m;
    scanf("%d",&m);
    if(m == 0)
        *b = NULL;
    else{
        BTree *s = (BTree *)malloc(sizeof(BTree));
        s->data = m;
        s->lchild = NULL;
        s->rchild = NULL;
        *b = s;
        createTree(&((*b)->lchild));
        createTree(&((*b)->rchild));
    }
}

　　另外，整體的思路，是用一個指針記錄轉換的雙鏈表表尾。

　　每次進行中序遍歷的轉換。

　　最先轉換的是最左下的節點，

void converNode(BTree *b,BTree **p){
    if(b == NULL)
        return ;
    BTree *pnow = b;
    if(b->lchild != NULL)
        converNode(b->lchild,p);
    
    pnow->lchild = *p;
    if(*p != NULL)
        (*p)->rchild = pnow;

    *p = pnow;

    if(b->rchild != NULL)
        converNode(b->rchild,p);
}

　　每次遍歷節點的左孩子右孩子。把左孩子指向轉換鏈表的尾節點，並把末尾指針的右孩子指向自己。右孩子指向節點的右孩子。如果沒有右孩子就返回。下面是代碼思路的步驟：

1 找到最左邊也就是最小的節點，PLast = NULL;

2 讓節點的左孩子指向鏈尾，然後鏈尾指針右移。如果右孩子為空就返回。

最後我們從尾遍歷回頭指針返回。

全部代碼：

#include <stdio.h>
#include <stdlib.h>
typedef struct btree{
    int data;
    struct btree *lchild,*rchild;
}BTree;
 
void createTree(BTree **b);
void inorderTree(BTree *b);
BTree * convert(BTree *b);
void converNode(BTree *b,BTree **p);
 
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        BTree *b = (BTree *)malloc(sizeof(BTree));   
        createTree(&b);
        BTree *head = convert(b);
        while(head!=NULL){
            printf("%d ",head->data);
            head = head->rchild;
        }
        printf("\n");
    }
    return 0;
}
BTree* convert(BTree *b){
    BTree *pLast = NULL;
    converNode(b,&pLast);
 
    BTree *phead = pLast;
    while(phead != NULL && phead->lchild != NULL)
        phead = phead->lchild;
    return phead;
}
void converNode(BTree *b,BTree **p){
    if(b == NULL)
        return ;
    BTree *pnow = b;
    if(b->lchild != NULL)
        converNode(b->lchild,p);
     
    pnow->lchild = *p;
    if(*p != NULL)
        (*p)->rchild = pnow;
 
    *p = pnow;
 
    if(b->rchild != NULL)
        converNode(b->rchild,p);
}
void createTree(BTree **b){  
    int m;
    scanf("%d",&m);
    if(m == 0)
        *b = NULL;
    else{
        BTree *s = (BTree *)malloc(sizeof(BTree));
        s->data = m;
        s->lchild = NULL;
        s->rchild = NULL;
        *b = s;
        createTree(&((*b)->lchild));
        createTree(&((*b)->rchild));
    }
}
/**************************************************************
    Problem: 1503
    User: xhalo
    Language: C
    Result: Accepted
    Time:80 ms
    Memory:1704 kb
****************************************************************/