微軟等數據結構與算法面試100題 第一題

第一題
題目：輸入一棵二元查找樹，將該二元查找樹轉換成一個排序的雙向鏈表。
要求不能創建任何新的節點，只能調整指針的指向。 參考了July的整理。表示感謝。

分析：
由上面的例子可以看到，在對於樹進行遍歷的時候使用了中序遍歷方法，依次修改樹中節點的前指向和後指向。
因為是要求不能創建新的節點，因為在中序遍歷修改指向的時候，需要一個指針指向上次遍歷的那個節點的地址，以便於
當前指針的指向，因此需要一個指針。（這個應該不算是節點的創建吧？）

因此，程序主要分為兩個部分，一個是樹的構建（節點的插入函數），另一個是在樹的中序遍歷，並且在中序遍歷的過程中，修改
當前遍歷的節點的前指向和後指向。

代碼如下：
[cpp] 
#include<iostream> 
#include<stdio.h> 
  
 
using namespace std; 
 
typedef struct BSTreeNode 
{ 
    float value; 
    BSTreeNode * NodeLeft; 
    BSTreeNode * NodeRight; 
}DoubleList; 
 
DoubleList * listHead; 
DoubleList * listIndex; 
 
void convert2DoubleLIST(BSTreeNode * nodeCurrent); 
void InOrder(BSTreeNode * root) 
{ 
    if(NULL==root) 
    { 
        return; 
    } 
    if(root->NodeLeft!=NULL) 
    { 
        InOrder(root->NodeLeft); 
    } 
 
    convert2DoubleLIST(root); 
 
    if(NULL!=root->NodeRight) 
    { 
        InOrder(root->NodeRight); 
    } 
} 
 
void convert2DoubleLIST(BSTreeNode * nodeCurrent) 
{ 
    //listIndex存儲上次的記錄 
    nodeCurrent->NodeLeft = listIndex; 
     
    if(NULL==listIndex) 
    { 
        listHead = nodeCurrent; 
    } 
    else 
    //這裡面都是對地址進行操作 
    { 
        //上次處理的節點 
        listIndex->NodeRight = nodeCurrent; 
    } 
 
    listIndex = nodeCurrent; 
    cout<<nodeCurrent->value<<endl; 
 
} 
 
void addBSTreeNode(BSTreeNode * & root, float value){ 
 
    //創建二叉搜索樹 
    if(NULL==root)//這樣寫是因為root==NULL容易寫成root=NULL 
    { 
        BSTreeNode *paddNode = new BSTreeNode(); 
        paddNode->value = value; 
        paddNode->NodeLeft = NULL; 
        paddNode->NodeRight = NULL; 
        root = paddNode; 
    } 
    else 
    { 
        if(value < root->value) 
        { 
            addBSTreeNode(root->NodeLeft,value);  
        } 
        else if(value > root->value) 
        { 
            addBSTreeNode(root->NodeRight,value);     
        } 
        else 
        { 
            cout<<"重復插入節點"<<endl; 
        } 
    } 
 
} 
 
int main(){ 
 
    listIndex = NULL; 
    BSTreeNode * root = NULL; 
    addBSTreeNode(root,10); 
    addBSTreeNode(root,6); 
    addBSTreeNode(root,4); 
    addBSTreeNode(root,8); 
    addBSTreeNode(root,12); 
    addBSTreeNode(root,14); 
    addBSTreeNode(root,16); 
    addBSTreeNode(root,15); 
 
    InOrder(root); 
 
    return 0; 
}