题目：输入一颗二元查找树，将该二元查找树转变成一个排序的双向链表 要求不能创建任何，只调整指针的指向
转换成双向链表 4=6=8=10=12=14=16
答案：
#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 *& pCurrentNode, int value); void inOderBSTree(BSTreeNode *pBSTree); void convertToDoubleList(BSTreeNode *pCurrentNode); BSTreeNode *pHead = nullptr; //指向循环队列头结点 BSTreeNode *pIndex = nullptr; //指向下一个节点 int main(int argc, char *argv[]) { BSTreeNode *pRoot = nullptr; addBSTreeNode(pRoot, 10); addBSTreeNode(pRoot, 6); addBSTreeNode(pRoot, 14); addBSTreeNode(pRoot, 4); addBSTreeNode(pRoot, 8); addBSTreeNode(pRoot, 12); addBSTreeNode(pRoot, 16); inOderBSTree(pRoot); getchar(); return true; } //建立二叉排序树 //第一次传入节点为空，走第一个分支创建根节点 //第二次传入的节点数据6比第一个节点数据小，走第三个分支传入第一个节点的左子节点，此时该左子节点又为空，继续走第一个分支 //第三次传入的节点数据14比第一个节点数据大，走第二个分支传入第一个节点的右子节点，此时该右子节点为空，继续第一个分支 //第四次传入数据4比第一个节点数据小，走第三个分支传入第一个节点的左子节点此时该左子节点不为空，并且数据比该节点数据小，继续走第三个分支传入第二个节点的左子节点 //依次类推构成查找树 void addBSTreeNode(BSTreeNode *& pCurrentNode, int value) { if (pCurrentNode == nullptr) { BSTreeNode *pBSTree = new BSTreeNode(); pBSTree->m_nValue = value; pBSTree->m_pLeft = nullptr; pBSTree->m_pRight = nullptr; pCurrentNode = pBSTree; } else if (pCurrentNode->m_nValue < value) { addBSTreeNode(pCurrentNode->m_pRight, value); } else if (pCurrentNode->m_nValue > value) { addBSTreeNode(pCurrentNode->m_pLeft, value); } else { cout << "node repeated!" << endl; } } //中序遍历二叉树，同时调整节点指针 void inOderBSTree(BSTreeNode *pBSTree) { if (nullptr == pBSTree) { cout << "input tree is nullptr" << endl; return; } if (nullptr != pBSTree->m_pLeft) { inOderBSTree(pBSTree->m_pLeft); } /*if (nullptr != pBSTree) { cout << pBSTree->m_nValue<< endl; }*/ convertToDoubleList(pBSTree); if (nullptr != pBSTree->m_pRight) { inOderBSTree(pBSTree->m_pRight); } } //调整指针结构 void convertToDoubleList(BSTreeNode *pCurrentNode) { //使当前节点的左子节点指向双向链表中最后一个节点 pCurrentNode->m_pLeft = pIndex; //若最后一个节点为空，则此时双向链表还未建立，因此将当前节点设置为双向链表的头结点 if (nullptr == pIndex) { pHead = pCurrentNode; } //使双向链表的右指针指向当前节点 else { pIndex->m_pRight = pCurrentNode; } //将当前节点设为双向链表的最后一个节点 pIndex = pCurrentNode; cout << pCurrentNode->m_nValue << " "; }