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

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

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

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

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

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

參考代碼：

首先我們定義二元查找樹結(jié)點的數(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
    };

思路一對應(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);
}

思路二對應(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語言中，假設(shè)我們有這樣的一個函數(shù)：
　　
　　int function(int a,int b)
　　
　　調(diào)用時只要用result = function(1,2)這樣的方式就可以使用這個函數(shù)。但是，當高級語言被編譯成計算機可以識別的機器碼時，有一個問題就凸現(xiàn)出來：在CPU中，計算機沒有辦法知道一個函數(shù)調(diào)用需要多少個、什么樣的參數(shù)，也沒有硬件可以保存這些參數(shù)。也就是說，計算機不知道怎么給這個函數(shù)傳遞參數(shù)，傳遞參數(shù)的工作必須由函數(shù)調(diào)用者和函數(shù)本身來協(xié)調(diào)。為此，計算機提供了一種被稱為棧的數(shù)據(jù)結(jié)構(gòu)來支持參數(shù)傳遞。

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

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

　　在參數(shù)傳遞中，有兩個很重要的問題必須得到明確說明：
　　
　　當參數(shù)個數(shù)多于一個時，按照什么順序把參數(shù)壓入堆棧 
　　函數(shù)調(diào)用后，由誰來把堆棧恢復(fù)原裝 
　　在高級語言中，通過函數(shù)調(diào)用約定來說明這兩個問題。常見的調(diào)用約定有：

　　stdcall 
　　cdecl 
　　fastcall 
　　thiscall 
　　naked call

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

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

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

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

　　而對于函數(shù)自身，則可以翻譯為： 
　　push ebp　　　　　　 保存ebp寄存器，該寄存器將用來保存堆棧的棧頂指針，可以在函數(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ù)的名字被翻譯成_function@8

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

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

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

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

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

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

　　被調(diào)用函數(shù)_function處
　　push ebp　　　　　　 保存ebp寄存器，該寄存器將用來保存堆棧的棧頂指針，可以在函數(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　　　　　　　　　注意，這里沒有修改堆棧

　　MSDN中說，該修飾自動在函數(shù)名前加前導(dǎo)的下劃線，因此函數(shù)名在符號表中被記錄為_function，但是我在編譯時似乎沒有看到這種變化。

　　由于參數(shù)按照從右向左順序壓棧，因此最開始的參數(shù)在最接近棧頂?shù)奈恢茫虼水敳捎貌欢▊€數(shù)參數(shù)時，第一個參數(shù)在棧中的位置肯定能知道，只要不定的參數(shù)個數(shù)能夠根據(jù)第一個后者后續(xù)的明確的參數(shù)確定下來，就可以使用不定參數(shù)，例如對于CRT中的sprintf函數(shù)，定義為：
　　int sprintf(char* buffer,const char* format,...)
　　由于所有的不定參數(shù)都可以通過format確定，因此使用不定個數(shù)的參數(shù)是沒有問題的。

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

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

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

　　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沒有被入棧

　　//函數(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
　　
　　可見，對于參數(shù)個數(shù)固定情況下，它類似于stdcall，不定時則類似cdecl

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

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

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

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

　 注意這個修飾是和__stdcall及cdecl結(jié)合使用的，前面是它和cdecl結(jié)合使用的代碼，對于和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)致的常見問題
　　如果定義的約定和使用的約定不一致，則將導(dǎo)致堆棧被破壞，導(dǎo)致嚴重問題，下面是兩種常見的問題：

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

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

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

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

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