"微软等公司数据结构算法面试100题：二元查找树转化为排序双向链表"

微软等公司数据结构算法面试100题.doc中提到了一个题目，题目要求我们将一个二叉查找树转换成一个排序的双向链表，要求不能创建任何新的结点，只调整指针的指向。给定的二叉查找树如下： 10 / \ 6 14 / \ / \ 4 8 12 16 我们需要将这个二叉查找树转换成一个排序的双向链表，转换后的链表应为： 4 = 6 = 8 = 10 = 12 = 14 = 16 首先，我们可以定义二叉查找树节点的数据结构如下： struct BSTreeNode{ int m_nValue; // 节点的值 BSTreeNode* m_pLeft; // 左子节点指针 BSTreeNode* m_pRight; // 右子节点指针 }; 那么我们可以使用中序遍历的方式来遍历二叉查找树，这样可以保证我们遍历到的节点是按照从小到大的顺序的。我们可以定义一个辅助函数来进行中序遍历，该函数接收一个二叉查找树节点指针和一个双向链表的指针（也就是头结点指针），并将该二叉查找树转换成一个排序的双向链表： void ConvertBSTToDoubleList(BSTreeNode* pRoot, BSTreeNode** pHead) { if(pRoot == NULL) // 如果根节点为空，返回 return; BSTreeNode* pTail = NULL; // 定义一个尾指针 // 转换左子树 if(pRoot->m_pLeft) ConvertBSTToDoubleList(pRoot->m_pLeft, pHead); // 将根节点连接到双向链表中 pRoot->m_pLeft = pTail; if(pTail) pTail->m_pRight = pRoot; else *pHead = pRoot; // 更新尾指针 pTail = pRoot; // 转换右子树 if(pRoot->m_pRight) ConvertBSTToDoubleList(pRoot->m_pRight, pHead); } 首先，在转换过程中，我们需要一个尾指针来记录已经被转换的链表的最后一个节点。对于每个节点，我们需要先转换其左子树（如果存在），然后将根节点连接到双向链表中，最后再转换右子树（如果存在）。 接下来，我们使用一个头指针（也就是指向双向链表头结点的指针）来记录链表的头部。在转换过程中，我们需要更新头指针，使其指向双向链表的头部。 最后，我们需要注意在函数结束之前更新尾指针的位置，以便将最后一个节点连接到双向链表中。 最后，我们可以调用这个辅助函数来将二叉查找树转换成排序的双向链表： BSTreeNode* ConvertBSTToDoubleList(BSTreeNode* pRoot) { BSTreeNode* pHead = NULL; // 定义一个头指针 ConvertBSTToDoubleList(pRoot, &pHead); return pHead; // 返回头指针 } 这样，我们就完成了将二叉查找树转换成排序的双向链表的操作。可以看到，我们并没有创建任何新的节点，只是通过调整指针的指向来实现了转换。这符合题目的要求。 总结起来，题目要求我们将一个二叉查找树转换成排序的双向链表，要求不能创建任何新的节点，只调整指针的指向。我们通过中序遍历的方式来遍历二叉查找树，然后通过调整指针的指向将其转换成排序的双向链表。最后，我们返回头指针即可。这样，我们就完成了题目的要求。