把二進制查找樹轉變成排序的雙向連結清單

題目： 輸入一棵二進制查找樹，将該二進制查找樹轉換成一個排序的雙向連結清單。 要求不能建立任何新的結點，隻調整指針的指向。 10 / \ 6 14 / \ / \ 4 8 12 16 轉換成雙向連結清單 4=6=8=10=12=14=16。 首先我們定義的二進制查找樹節點的資料結構如下： struct BSTreeNode { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node };

​ ​// 1：構造二叉查找樹； ​ ​ ​ ​// 2：中序周遊二叉查找樹，是以結點按從小到大順序通路，假設之前通路過的結點已經調整為一個雙向連結清單，那麼​ ​ ​ ​//       隻需要将目前結點連接配接至雙向連結清單的最後一個結點即可，通路完後，雙向連結清單也就調整完了​ ​ ​ ​#include <iostream>​ ​ ​ ​using ​ ​ ​ ​namespace​ ​ ​ ​std; ​ ​ ​ ​struct ​ ​ ​ ​BSTreeNode ​ ​ ​ ​{ ​ ​ ​ ​int ​ ​ ​ ​m_nValue; ​ ​ ​ ​// value of node​ ​ ​ ​BSTreeNode *m_pLeft;​ ​ ​ ​// left child of node ​ ​ ​ ​BSTreeNode *m_pRight;​ ​ ​ ​// right child of node ​ ​ ​ ​}; ​ ​ ​ ​void​ ​ ​ ​addBSTreeNode(BSTreeNode *&pCurrent,​ ​ ​ ​int ​ ​ ​ ​value); ​ ​ ​ ​void​ ​ ​ ​inOrderBSTree(BSTreeNode* pBSTree); ​ ​ ​ ​void​ ​ ​ ​convertToDoubleList(BSTreeNode* pCurrent); ​ ​ ​ ​BSTreeNode *pHead=NULL;​ ​ ​ ​//指向循環隊列頭結點​ ​ ​ ​BSTreeNode *pIndex=NULL;​ ​ ​ ​//指向前一個結點​ ​ ​ ​int​ ​ ​ ​ main() ​ ​ ​ ​{ ​ ​ ​ ​BSTreeNode *pRoot=NULL;​ ​ ​ ​addBSTreeNode(pRoot,10);​ ​ ​ ​addBSTreeNode(pRoot,6);​ ​ ​ ​addBSTreeNode(pRoot,14);​ ​ ​ ​addBSTreeNode(pRoot,4);​ ​ ​ ​addBSTreeNode(pRoot,8);​ ​ ​ ​addBSTreeNode(pRoot,12);​ ​ ​ ​addBSTreeNode(pRoot,16);​ ​ ​ ​inOrderBSTree(pRoot);​ ​ ​ ​return​ ​ ​ ​0; ​ ​ ​ ​} ​ ​ ​ ​/* 建立二叉排序樹                                                               */​ ​ ​ ​void ​ ​ ​ ​addBSTreeNode(BSTreeNode *&pCurrent,​ ​ ​ ​int ​ ​ ​ ​value)​ ​ ​ ​//在這個函數中會要改變指針值，一定要記得使用引用傳遞​ ​ ​ ​{ ​ ​ ​ ​if​ ​ ​ ​(pCurrent==NULL) ​ ​ ​ ​{​ ​ ​ ​BSTreeNode* pBSTree=​ ​ ​ ​new ​ ​ ​ ​BSTreeNode(); ​ ​ ​ ​pBSTree->m_nValue=value;​ ​ ​ ​pBSTree->m_pLeft=NULL;​ ​ ​ ​pBSTree->m_pRight=NULL;​ ​ ​ ​pCurrent=pBSTree;​ ​ ​ ​}​ ​ ​ ​else​ ​ ​ ​if​ ​ ​ ​(pCurrent->m_nValue<value)​ ​ ​ ​{​ ​ ​ ​addBSTreeNode(pCurrent->m_pRight,value);​ ​ ​ ​}​ ​ ​ ​else​ ​ ​ ​if​ ​ ​ ​(pCurrent->m_nValue>value)​ ​ ​ ​{​ ​ ​ ​addBSTreeNode(pCurrent->m_pLeft,value);​ ​ ​ ​}​ ​ ​ ​else​ ​ ​ ​{​ ​ ​ ​cout<<​ ​ ​ ​"node repeated"​ ​ ​ ​<<endl;​ ​ ​ ​}​ ​ ​ ​} ​ ​ ​ ​/* 中序周遊二叉樹，同時調整結點指針                                                                     */​ ​ ​ ​void ​ ​ ​ ​inOrderBSTree(BSTreeNode* pBSTree) ​ ​ ​ ​{ ​ ​ ​ ​if​ ​ ​ ​(NULL==pBSTree) ​ ​ ​ ​{​ ​ ​ ​return​ ​ ​ ​;​ ​ ​ ​}​ ​ ​ ​if​ ​ ​ ​(NULL!=pBSTree->m_pLeft) ​ ​ ​ ​{​ ​ ​ ​inOrderBSTree(pBSTree->m_pLeft);​ ​ ​ ​}​ ​ ​ ​//  if (NULL!=pBSTree)​ ​ ​ ​//  {​ ​ ​ ​//      cout<<pBSTree->m_nValue;​ ​ ​ ​//  }​ ​ ​ ​convertToDoubleList(pBSTree);​ ​ ​ ​if​ ​ ​ ​(NULL!=pBSTree->m_pRight) ​ ​ ​ ​{​ ​ ​ ​inOrderBSTree(pBSTree->m_pRight);​ ​ ​ ​}​ ​ ​ ​} ​ ​ ​ ​/* 調整結點指針                                                                   */​ ​ ​ ​void ​ ​ ​ ​convertToDoubleList(BSTreeNode* pCurrent) ​ ​ ​ ​{ ​ ​ ​ ​pCurrent->m_pLeft=pIndex;​ ​ ​ ​//使目前結點的左指針指向雙向連結清單中最後一個結點​ ​ ​ ​if​ ​ ​ ​(NULL==pIndex)​ ​ ​ ​//若最後一個元素不存在，此時雙向連結清單尚未建立，是以将目前結點設為雙向連結清單頭結點​ ​ ​ ​{​ ​ ​ ​pHead=pCurrent;​ ​ ​ ​}​ ​ ​ ​else​ ​ ​ ​//使雙向連結清單中最後一個結點的右指針指向目前結點​ ​ ​ ​{​ ​ ​ ​pIndex->m_pRight=pCurrent;​ ​ ​ ​}​ ​ ​ ​pIndex=pCurrent;​ ​ ​ ​//将目前結點設為雙向連結清單中最後一個結點​ ​ ​ ​cout<<pCurrent->m_nValue<<​ ​ ​ ​" "​ ​ ​ ​;​ ​