Where there is a dream ,there is hope

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

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

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

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

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

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

參考代碼：

首先我們定義二元查找樹結點的數據結構如下：
    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
    };

思路一對應的代碼：
///////////////////////////////////////////////////////////////////////
// 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);
}

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

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

　　函數調用時，調用者依次把參數壓棧，然后調用函數，函數被調用以后，在堆棧中取得數據，并進行計算。函數計算結束以后，或者調用者、或者函數本身修改堆棧，使堆棧恢復原裝。

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

　　stdcall 
　　cdecl 
　　fastcall 
　　thiscall 
　　naked call

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

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

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

　　push 2　　　　　　　 第二個參數入棧
　　push 1　　　　　　　 第一個參數入棧
　　call function　　　　調用參數，注意此時自動把cs:eip入棧

　　而對于函數自身，則可以翻譯為： 
　　push ebp　　　　　　 保存ebp寄存器，該寄存器將用來保存堆棧的棧頂指針，可以在函數退出時恢復
　　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　　　　恢復esp
　　pop　ebp
　　ret　8

　　而在編譯時，這個函數的名字被翻譯成_function@8

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

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

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

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

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

　　調用處
　　push 1
　　push 2
　　call function
　　add　esp, 8　　　　　注意：這里調用者在恢復堆棧

　　被調用函數_function處
　　push ebp　　　　　　 保存ebp寄存器，該寄存器將用來保存堆棧的棧頂指針，可以在函數退出時恢復
　　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　　　　 恢復esp
　　pop　ebp
　　ret　　　　　　　　　注意，這里沒有修改堆棧

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

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

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

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

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

　　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函數被翻譯成匯編后就變成： 
　　//函數function1調用
　　00401C1D　 push　　　　2
　　00401C1F　 push　　　　1
　　00401C21　 lea　　　　 ecx,[ebp-8]
　　00401C24　 call　　　　function1　　　　　注意，這里this沒有被入棧

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

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

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

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

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

　 注意這個修飾是和__stdcall及cdecl結合使用的，前面是它和cdecl結合使用的代碼，對于和stdcall結合的代碼，則變成：

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

　　至于這種函數被調用，則和普通的cdecl及stdcall調用函數一致。

　　函數調用約定導致的常見問題
　　如果定義的約定和使用的約定不一致，則將導致堆棧被破壞，導致嚴重問題，下面是兩種常見的問題：

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

　　__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(...)//這里修改了調用約定
　　result = func(1,2);//導致錯誤

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