原文地址：http://zhedahht.blog.163.com/blog/static/254111742007127104759245/
題目：輸入一棵二元查找樹(shù)，將該二元查找樹(shù)轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只調(diào)整指針的指向。

　　比如將二元查找樹(shù)
                                            10
                                          /    \
                                        6       14
                                      /  \     /　 \
                                   　4     8  12 　  16
轉(zhuǎn)換成雙向鏈表

4=6=8=10=12=14=16。

　　分析：本題是微軟的面試題。很多與樹(shù)相關(guān)的題目都是用遞歸的思路來(lái)解決，本題也不例外。下面我們用兩種不同的遞歸思路來(lái)分析。

　　思路一：當(dāng)我們到達(dá)某一結(jié)點(diǎn)準(zhǔn)備調(diào)整以該結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹(shù)時(shí)，先調(diào)整其左子樹(shù)將左子樹(shù)轉(zhuǎn)換成一個(gè)排好序的左子鏈表，再調(diào)整其右子樹(shù)轉(zhuǎn)換右子鏈表。最近鏈接左子鏈表的最右結(jié)點(diǎn)（左子樹(shù)的最大結(jié)點(diǎn)）、當(dāng)前結(jié)點(diǎn)和右子鏈表的最左結(jié)點(diǎn)（右子樹(shù)的最小結(jié)點(diǎn)）。從樹(shù)的根結(jié)點(diǎn)開(kāi)始遞歸調(diào)整所有結(jié)點(diǎn)。

　　思路二：我們可以中序遍歷整棵樹(shù)。按照這個(gè)方式遍歷樹(shù)，比較小的結(jié)點(diǎn)先訪問(wèn)。如果我們每訪問(wèn)一個(gè)結(jié)點(diǎn)，假設(shè)之前訪問(wèn)過(guò)的結(jié)點(diǎn)已經(jīng)調(diào)整成一個(gè)排序雙向鏈表，我們?cè)侔颜{(diào)整當(dāng)前結(jié)點(diǎn)的指針將其鏈接到鏈表的末尾。當(dāng)所有結(jié)點(diǎn)都訪問(wèn)過(guò)之后，整棵樹(shù)也就轉(zhuǎn)換成一個(gè)排序雙向鏈表了。

參考代碼：

首先我們定義二元查找樹(shù)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下：
    struct BSTreeNode // a node in the binary search tree
    {
        int          m_nValue; // value of node
        BSTreeNode  *m_pLeft;  // left child of node
        BSTreeNode  *m_pRight; // right child of node
    };

思路一對(duì)應(yīng)的代碼：
///////////////////////////////////////////////////////////////////////
// Covert a sub binary-search-tree into a sorted double-linked list
// Input: pNode - the head of the sub tree
//        asRight - whether pNode is the right child of its parent
// Output: if asRight is true, return the least node in the sub-tree
//         else return the greatest node in the sub-tree
///////////////////////////////////////////////////////////////////////
BSTreeNode* ConvertNode(BSTreeNode* pNode, bool asRight)
{
      if(!pNode)
            return NULL;

      BSTreeNode *pLeft = NULL;
      BSTreeNode *pRight = NULL;

      // Convert the left sub-tree
      if(pNode->m_pLeft)
            pLeft = ConvertNode(pNode->m_pLeft, false);

      // Connect the greatest node in the left sub-tree to the current node
      if(pLeft)
      {
            pLeft->m_pRight = pNode;
            pNode->m_pLeft = pLeft;
      }

      // Convert the right sub-tree
      if(pNode->m_pRight)
            pRight = ConvertNode(pNode->m_pRight, true);

      // Connect the least node in the right sub-tree to the current node
      if(pRight)
      {
            pNode->m_pRight = pRight;
            pRight->m_pLeft = pNode;
      }

      BSTreeNode *pTemp = pNode;

      // If the current node is the right child of its parent, 
      // return the least node in the tree whose root is the current node
      if(asRight)
      {
            while(pTemp->m_pLeft)
                  pTemp = pTemp->m_pLeft;
      }
      // If the current node is the left child of its parent, 
      // return the greatest node in the tree whose root is the current node
      else
      {
            while(pTemp->m_pRight)
                  pTemp = pTemp->m_pRight;
      }
 
      return pTemp;
}

///////////////////////////////////////////////////////////////////////
// Covert a binary search tree into a sorted double-linked list
// Input: the head of tree
// Output: the head of sorted double-linked list
///////////////////////////////////////////////////////////////////////
BSTreeNode* Convert(BSTreeNode* pHeadOfTree)
{
      // As we want to return the head of the sorted double-linked list,
      // we set the second parameter to be true
      return ConvertNode(pHeadOfTree, true);
}

思路二對(duì)應(yīng)的代碼：
///////////////////////////////////////////////////////////////////////
// Covert a sub binary-search-tree into a sorted double-linked list
// Input: pNode -           the head of the sub tree
//        pLastNodeInList - the tail of the double-linked list
///////////////////////////////////////////////////////////////////////
void ConvertNode(BSTreeNode* pNode, BSTreeNode*& pLastNodeInList)
{
      if(pNode == NULL)
            return;

      BSTreeNode *pCurrent = pNode;

      // Convert the left sub-tree
      if (pCurrent->m_pLeft != NULL)
            ConvertNode(pCurrent->m_pLeft, pLastNodeInList);

      // Put the current node into the double-linked list
      pCurrent->m_pLeft = pLastNodeInList; 
      if(pLastNodeInList != NULL)
            pLastNodeInList->m_pRight = pCurrent;

      pLastNodeInList = pCurrent;

      // Convert the right sub-tree
      if (pCurrent->m_pRight != NULL)
            ConvertNode(pCurrent->m_pRight, pLastNodeInList);
}

///////////////////////////////////////////////////////////////////////
// Covert a binary search tree into a sorted double-linked list
// Input: pHeadOfTree - the head of tree
// Output: the head of sorted double-linked list
///////////////////////////////////////////////////////////////////////
BSTreeNode* Convert_Solution1(BSTreeNode* pHeadOfTree)
{
      BSTreeNode *pLastNodeInList = NULL;
      ConvertNode(pHeadOfTree, pLastNodeInList);

      // Get the head of the double-linked list
      BSTreeNode *pHeadOfList = pLastNodeInList;
      while(pHeadOfList && pHeadOfList->m_pLeft)
            pHeadOfList = pHeadOfList->m_pLeft;

      return pHeadOfList;
}

原文地址：
http://blog.csdn.net/fly2k5/archive/2005/12/05/544112.aspx
在C語(yǔ)言中，假設(shè)我們有這樣的一個(gè)函數(shù)：
　　
　　int function(int a,int b)
　　
　　調(diào)用時(shí)只要用result = function(1,2)這樣的方式就可以使用這個(gè)函數(shù)。但是，當(dāng)高級(jí)語(yǔ)言被編譯成計(jì)算機(jī)可以識(shí)別的機(jī)器碼時(shí)，有一個(gè)問(wèn)題就凸現(xiàn)出來(lái)：在CPU中，計(jì)算機(jī)沒(méi)有辦法知道一個(gè)函數(shù)調(diào)用需要多少個(gè)、什么樣的參數(shù)，也沒(méi)有硬件可以保存這些參數(shù)。也就是說(shuō)，計(jì)算機(jī)不知道怎么給這個(gè)函數(shù)傳遞參數(shù)，傳遞參數(shù)的工作必須由函數(shù)調(diào)用者和函數(shù)本身來(lái)協(xié)調(diào)。為此，計(jì)算機(jī)提供了一種被稱(chēng)為棧的數(shù)據(jù)結(jié)構(gòu)來(lái)支持參數(shù)傳遞。

　　棧是一種先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)，棧有一個(gè)存儲(chǔ)區(qū)、一個(gè)棧頂指針。棧頂指針指向堆棧中第一個(gè)可用的數(shù)據(jù)項(xiàng)（被稱(chēng)為棧頂）。用戶(hù)可以在棧頂上方向棧中加入數(shù)據(jù)，這個(gè)操作被稱(chēng)為壓棧(Push)，壓棧以后，棧頂自動(dòng)變成新加入數(shù)據(jù)項(xiàng)的位置，棧頂指針也隨之修改。用戶(hù)也可以從堆棧中取走棧頂，稱(chēng)為彈出棧(pop)，彈出棧后，棧頂下的一個(gè)元素變成棧頂，棧頂指針隨之修改。

　　函數(shù)調(diào)用時(shí)，調(diào)用者依次把參數(shù)壓棧，然后調(diào)用函數(shù)，函數(shù)被調(diào)用以后，在堆棧中取得數(shù)據(jù)，并進(jìn)行計(jì)算。函數(shù)計(jì)算結(jié)束以后，或者調(diào)用者、或者函數(shù)本身修改堆棧，使堆?；謴?fù)原裝。

　　在參數(shù)傳遞中，有兩個(gè)很重要的問(wèn)題必須得到明確說(shuō)明：
　　
　　當(dāng)參數(shù)個(gè)數(shù)多于一個(gè)時(shí)，按照什么順序把參數(shù)壓入堆棧 
　　函數(shù)調(diào)用后，由誰(shuí)來(lái)把堆棧恢復(fù)原裝 
　　在高級(jí)語(yǔ)言中，通過(guò)函數(shù)調(diào)用約定來(lái)說(shuō)明這兩個(gè)問(wèn)題。常見(jiàn)的調(diào)用約定有：

　　stdcall 
　　cdecl 
　　fastcall 
　　thiscall 
　　naked call

　　stdcall調(diào)用約定
　　stdcall很多時(shí)候被稱(chēng)為pascal調(diào)用約定，因?yàn)閜ascal是早期很常見(jiàn)的一種教學(xué)用計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言，其語(yǔ)法嚴(yán)謹(jǐn)，使用的函數(shù)調(diào)用約定就是stdcall。在Microsoft C++系列的C/C++編譯器中，常常用PASCAL宏來(lái)聲明這個(gè)調(diào)用約定，類(lèi)似的宏還有WINAPI和CALLBACK。

　　stdcall調(diào)用約定聲明的語(yǔ)法為(以前文的那個(gè)函數(shù)為例）：
　　
　　int __stdcall function(int a,int b)
　　
　　stdcall的調(diào)用約定意味著：1）參數(shù)從右向左壓入堆棧，2）函數(shù)自身修改堆棧 3)函數(shù)名自動(dòng)加前導(dǎo)的下劃線，后面緊跟一個(gè)@符號(hào)，其后緊跟著參數(shù)的尺寸

　　以上述這個(gè)函數(shù)為例，參數(shù)b首先被壓棧，然后是參數(shù)a，函數(shù)調(diào)用function(1,2)調(diào)用處翻譯成匯編語(yǔ)言將變成：

　　push 2　　　　　　　 第二個(gè)參數(shù)入棧
　　push 1　　　　　　　 第一個(gè)參數(shù)入棧
　　call function　　　　調(diào)用參數(shù)，注意此時(shí)自動(dòng)把cs:eip入棧

　　而對(duì)于函數(shù)自身，則可以翻譯為： 
　　push ebp　　　　　　 保存ebp寄存器，該寄存器將用來(lái)保存堆棧的棧頂指針，可以在函數(shù)退出時(shí)恢復(fù)
　　mov　ebp, esp　　　　保存堆棧指針
　　mov　eax,[ebp + 8H]　堆棧中ebp指向位置之前依次保存有ebp, cs:eip, a, b, ebp +8指向a
　　add　eax,[ebp + 0CH] 堆棧中ebp + 12處保存了b
　　mov　esp, ebp　　　　恢復(fù)esp
　　pop　ebp
　　ret　8

　　而在編譯時(shí)，這個(gè)函數(shù)的名字被翻譯成_function@8

　　注意不同編譯器會(huì)插入自己的匯編代碼以提供編譯的通用性，但是大體代碼如此。其中在函數(shù)開(kāi)始處保留esp到ebp中，在函數(shù)結(jié)束恢復(fù)是編譯器常用的方法。

　　從函數(shù)調(diào)用看，2和1依次被push進(jìn)堆棧，而在函數(shù)中又通過(guò)相對(duì)于ebp(即剛進(jìn)函數(shù)時(shí)的堆棧指針）的偏移量存取參數(shù)。函數(shù)結(jié)束后，ret 8表示清理8個(gè)字節(jié)的堆棧，函數(shù)自己恢復(fù)了堆棧。

　　
　　cdecl調(diào)用約定
　　cdecl調(diào)用約定又稱(chēng)為C調(diào)用約定，是C語(yǔ)言缺省的調(diào)用約定，它的定義語(yǔ)法是：

　　int function (int a ,int b)　//不加修飾就是C調(diào)用約定
　　int __cdecl function(int a,int b)//明確指出C調(diào)用約定

　　在寫(xiě)本文時(shí)，出乎我的意料，發(fā)現(xiàn)cdecl調(diào)用約定的參數(shù)壓棧順序是和stdcall是一樣的，參數(shù)首先由右向左壓入堆棧。所不同的是，函數(shù)本身不清理堆棧，調(diào)用者負(fù)責(zé)清理堆棧。由于這種變化，C調(diào)用約定允許函數(shù)的參數(shù)的個(gè)數(shù)是不固定的，這也是C語(yǔ)言的一大特色。對(duì)于前面的function函數(shù)，使用cdecl后的匯編碼變成：

　　調(diào)用處
　　push 1
　　push 2
　　call function
　　add　esp, 8　　　　　注意：這里調(diào)用者在恢復(fù)堆棧

　　被調(diào)用函數(shù)_function處
　　push ebp　　　　　　 保存ebp寄存器，該寄存器將用來(lái)保存堆棧的棧頂指針，可以在函數(shù)退出時(shí)恢復(fù)
　　mov　ebp,esp　　　　 保存堆棧指針
　　mov　eax,[ebp + 8H]　堆棧中ebp指向位置之前依次保存有ebp,cs:eip,a,b,ebp +8指向a
　　add　eax,[ebp + 0CH] 堆棧中ebp + 12處保存了b
　　mov　esp,ebp　　　　 恢復(fù)esp
　　pop　ebp
　　ret　　　　　　　　　注意，這里沒(méi)有修改堆棧

　　MSDN中說(shuō)，該修飾自動(dòng)在函數(shù)名前加前導(dǎo)的下劃線，因此函數(shù)名在符號(hào)表中被記錄為_(kāi)function，但是我在編譯時(shí)似乎沒(méi)有看到這種變化。

　　由于參數(shù)按照從右向左順序壓棧，因此最開(kāi)始的參數(shù)在最接近棧頂?shù)奈恢?，因此?dāng)采用不定個(gè)數(shù)參數(shù)時(shí)，第一個(gè)參數(shù)在棧中的位置肯定能知道，只要不定的參數(shù)個(gè)數(shù)能夠根據(jù)第一個(gè)后者后續(xù)的明確的參數(shù)確定下來(lái)，就可以使用不定參數(shù)，例如對(duì)于CRT中的sprintf函數(shù)，定義為：
　　int sprintf(char* buffer,const char* format,...)
　　由于所有的不定參數(shù)都可以通過(guò)format確定，因此使用不定個(gè)數(shù)的參數(shù)是沒(méi)有問(wèn)題的。

　　fastcall
　　fastcall調(diào)用約定和stdcall類(lèi)似，它意味著： 
　　
　　函數(shù)的第一個(gè)和第二個(gè)DWORD參數(shù)（或者尺寸更小的）通過(guò)ecx和edx傳遞，其他參數(shù)通過(guò)從右向左的順序壓棧 
　　被調(diào)用函數(shù)清理堆棧 
　　函數(shù)名修改規(guī)則同stdcall 
　　其聲明語(yǔ)法為：int fastcall function(int a, int b)

　　thiscall
　　thiscall是唯一一個(gè)不能明確指明的函數(shù)修飾，因?yàn)閠hiscall不是關(guān)鍵字。它是C++類(lèi)成員函數(shù)缺省的調(diào)用約定。由于成員函數(shù)調(diào)用還有一個(gè)this指針，因此必須特殊處理，thiscall意味著：

　　參數(shù)從右向左入棧 
　　如果參數(shù)個(gè)數(shù)確定，this指針通過(guò)ecx傳遞給被調(diào)用者；如果參數(shù)個(gè)數(shù)不確定，this指針在所有參數(shù)壓棧后被壓入堆棧。對(duì)參數(shù)個(gè)數(shù)不定的，調(diào)用者清理堆棧，否則函數(shù)自己清理堆棧為了說(shuō)明這個(gè)調(diào)用約定，定義如下類(lèi)和使用代碼：

　　class A
　　{
　　public:
　　　 int function1(int a,int b);
　　　 int function2(int a,...);
　　};

　　int A::function1 (int a,int b)
　　{
　　　 return a+b;
　　}

　　#include <stdarg.h>
　　int A::function2(int a,...)
　　{
　　　 va_list ap;
　　　 va_start(ap,a);
　　　 int i;
　　　 int result = 0;
　　　 for(i = 0 ; i < a ; i ++)
　　　 {
　　　　　result += va_arg(ap,int);
　　　 }
　　　 return result;
　　}

　　void callee()
　　{
　　　 A a;
　　　 a.function1(1, 2);
　　　 a.function2(3, 1, 2, 3);
　　}

callee函數(shù)被翻譯成匯編后就變成： 
　　//函數(shù)function1調(diào)用
　　00401C1D　 push　　　　2
　　00401C1F　 push　　　　1
　　00401C21　 lea　　　　 ecx,[ebp-8]
　　00401C24　 call　　　　function1　　　　　注意，這里this沒(méi)有被入棧

　　//函數(shù)function2調(diào)用
　　00401C29　 push　　　　3
　　00401C2B　 push　　　　2
　　00401C2D　 push　　　　1
　　00401C2F　 push　　　　3
　　00401C31　 lea　　　　 eax, [ebp-8]　　　 這里引入this指針
　　00401C34　 push　　　　eax
　　00401C35　 call　　　　function2
　　00401C3A　 add　　　　 esp, 14h
　　
　　可見(jiàn)，對(duì)于參數(shù)個(gè)數(shù)固定情況下，它類(lèi)似于stdcall，不定時(shí)則類(lèi)似cdecl

　　naked call
　　這是一個(gè)很少見(jiàn)的調(diào)用約定，一般程序設(shè)計(jì)者建議不要使用。編譯器不會(huì)給這種函數(shù)增加初始化和清理代碼，更特殊的是，你不能用return返回返回值，只能用插入?yún)R編返回結(jié)果。這一般用于實(shí)模式驅(qū)動(dòng)程序設(shè)計(jì)，假設(shè)定義一個(gè)求和的加法程序，可以定義為：

　　__declspec(naked) int　add(int a,int b)
　　{
　　　 __asm mov eax,a
　　　 __asm add eax,b
　　　 __asm ret 
　　}

　　注意，這個(gè)函數(shù)沒(méi)有顯式的return返回值，返回通過(guò)修改eax寄存器實(shí)現(xiàn)，而且連退出函數(shù)的ret指令都必須顯式插入。上面代碼被翻譯成匯編以后變成：

　　mov eax,[ebp+8]
　　add eax,[ebp+12]
　　ret 8

　 注意這個(gè)修飾是和__stdcall及cdecl結(jié)合使用的，前面是它和cdecl結(jié)合使用的代碼，對(duì)于和stdcall結(jié)合的代碼，則變成：

　　__declspec(naked) int __stdcall function(int a,int b)
　 {
　　　　__asm mov eax,a
　　　　__asm add eax,b
　　　　__asm ret 8　　　　//注意后面的8
　　}

　　至于這種函數(shù)被調(diào)用，則和普通的cdecl及stdcall調(diào)用函數(shù)一致。

　　函數(shù)調(diào)用約定導(dǎo)致的常見(jiàn)問(wèn)題
　　如果定義的約定和使用的約定不一致，則將導(dǎo)致堆棧被破壞，導(dǎo)致嚴(yán)重問(wèn)題，下面是兩種常見(jiàn)的問(wèn)題：

　　函數(shù)原型聲明和函數(shù)體定義不一致 
　　DLL導(dǎo)入函數(shù)時(shí)聲明了不同的函數(shù)約定 
　　以后者為例，假設(shè)我們?cè)赿ll種聲明了一種函數(shù)為：

　　__declspec(dllexport) int func(int a,int b);//注意，這里沒(méi)有stdcall，使用的是cdecl
　　使用時(shí)代碼為：

　　typedef int (*WINAPI DLLFUNC)func(int a,int b);
　　hLib = LoadLibrary(...);

　　DLLFUNC func = (DLLFUNC)GetProcAddress(...)//這里修改了調(diào)用約定
　　result = func(1,2);//導(dǎo)致錯(cuò)誤

　　由于調(diào)用者沒(méi)有理解WINAPI的含義錯(cuò)誤的增加了這個(gè)修飾，上述代碼必然導(dǎo)致堆棧被破壞，MFC在編譯時(shí)插入的checkesp函數(shù)將告訴你，堆棧被破壞