二叉搜索树与双向链表的C++实现

二叉搜索树与双向链表的C++实现2015-10-14题目：输入一颗二叉搜索树, 将该二叉搜索树转换成一个排序的双向链表.

要求不能创建任何新的结点, 只能调整数中结点的指针的指向.

方法: 使用中序遍历每一个结点, 并进行连接, 即左子树指前, 右子树指后, 并保存前一个节点.

本程序包含算法原理, 测试程序, 及输出.

代码:

/** main.cpp**Created on: 2014.6.12*Author: Spike*//*eclipse cdt, gcc 4.8.1*/#include <iostream>#include <stack>#include <queue>using namespace std;struct BinaryTreeNode {int m_nValue;BinaryTreeNode* m_pLeft;BinaryTreeNode* m_pRight;};void printTree （BinaryTreeNode* tree）{BinaryTreeNode* node = tree;std::queue<BinaryTreeNode*> temp1;std::queue<BinaryTreeNode*> temp2;temp1.push（node）;while （！temp1.empty（））{node = temp1.front（）;if （node->m_pLeft ！= NULL） {temp2.push（node->m_pLeft）;}if （node->m_pRight ！= NULL） {temp2.push（node->m_pRight）;}temp1.pop（）;std::cout << node->m_nValue<< " ";if （temp1.empty（））{std::cout << std::endl;temp1 = temp2;std::queue<BinaryTreeNode*> empty;std::swap（temp2, empty）;}}}BinaryTreeNode* buildTree （const std::vector<int>& L）{if （L.empty（））return nullptr;std::queue<BinaryTreeNode*> parentQueue;std::queue<BinaryTreeNode*> childQueue;BinaryTreeNode* root = new BinaryTreeNode（）;root->m_nValue = L[0];parentQueue.push（root）;std::size_t times = 1;while （times < L.size（））{BinaryTreeNode* parent = parentQueue.front（）;parentQueue.pop（）;BinaryTreeNode* lchild = new BinaryTreeNode（）;lchild->m_nValue = L[times];lchild->m_pLeft = nullptr;lchild->m_pRight = nullptr;++times;parent->m_pLeft = lchild;childQueue.push（lchild）;if （times == L.size（）） break;BinaryTreeNode* rchild = new BinaryTreeNode（）;rchild->m_nValue = L[times];rchild->m_pLeft = nullptr;rchild->m_pRight = nullptr;++times;parent->m_pRight = rchild;childQueue.push（rchild）;if （parentQueue.empty（）） {parentQueue = childQueue;std::queue<BinaryTreeNode*> empty;std::swap（childQueue, empty）;}}return root;}void printList （BinaryTreeNode* pHeadOfList）{while （pHeadOfList ！= NULL && pHeadOfList->m_pRight ！= NULL）{std::cout << pHeadOfList->m_nValue << " ";pHeadOfList = pHeadOfList->m_pRight;}std::cout << pHeadOfList->m_nValue << " ";std::cout << std::endl;return;}void ConvertNode（BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList）{if （pNode == NULL）return;BinaryTreeNode* pCurrent = pNode;if （pCurrent->m_pLeft ！= NULL）ConvertNode（pCurrent->m_pLeft, pLastNodeInList）;pCurrent->m_pLeft = *pLastNodeInList;if （*pLastNodeInList ！= NULL）（*pLastNodeInList）->m_pRight = pCurrent;*pLastNodeInList = pCurrent;if （pCurrent->m_pRight ！= NULL）ConvertNode（pCurrent->m_pRight, pLastNodeInList）;}BinaryTreeNode* Convert（BinaryTreeNode* pRootOfTree）{BinaryTreeNode* pLastNodeInList = NULL;ConvertNode（pRootOfTree, &pLastNodeInList）;BinaryTreeNode* pHeadOfList = pLastNodeInList;while （pHeadOfList ！= NULL && pHeadOfList->m_pLeft ！= NULL）pHeadOfList = pHeadOfList->m_pLeft;return pHeadOfList;}int main （void）{std::vector<int> L = {10, 6, 14, 4, 8, 12, 16};BinaryTreeNode* tree = buildTree（L）;std::cout << "----Tree:----
";printTree（tree）;BinaryTreeNode* list = Convert（tree）;std::cout << "----List:----
";printList（list）;return 0;}

输出:

----Tree:----10 6 14 4 8 12 16 ----List:----4 6 8 10 12 14 16

作者：csdn博客 Caroline-Wendy