"名企经典c/c 笔试题100道：二元查找树转双向链表详解"

名企经典c/c 笔试题100道；从别的地方下下来的，希望可以帮到大家。 这份题目集中包含了100道C/C++编程笔试题，其中涵盖了各种经典的算法和数据结构题目。这些题目来源于各个知名企业的笔试题库，希望可以帮助大家更好地准备面试。其中有一道关于将二元查找树转变成排序的双向链表的题目。 题目描述如下：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。假设有一棵如下的二元查找树： ``` 10 / \ 6 14 / \ / \ 4 8 12 16 ``` 要将其转换成排序的双向链表，使得链表的顺序为4=6=8=10=12=14=16。首先我们定义的二元查找树节点的数据结构如下： ```c struct BSTreeNode{ int m_nValue; // 节点的值 BSTreeNode *m_pLeft; // 左子节点指针 BSTreeNode *m_pRight; // 右子节点指针 }; ``` 解决这个问题的关键在于使用递归。对于每个节点，将其左子节点和右子节点转换成排序的双向链表，然后将左子节点的双向链表和当前节点连接，再将当前节点和右子节点的双向链表连接，最后返回左子节点链表的头节点和右子节点链表的尾节点，作为当前节点的左右指针。具体的代码实现可以参考下面的示例： ```c BSTreeNode* Convert(BSTreeNode* root) { if (root == nullptr) { return nullptr; } // 转换左子树 BSTreeNode* leftList = Convert(root->m_pLeft); // 转换右子树 BSTreeNode* rightList = Convert(root->m_pRight); // 将左子树的尾节点和根节点连接 if (leftList != nullptr) { BSTreeNode* node = leftList; while (node->m_pRight != nullptr) { node = node->m_pRight; } node->m_pRight = root; root->m_pLeft = node; } else { leftList = root; } // 将右子树的头节点和根节点连接 if (rightList != nullptr) { rightList->m_pLeft = root; root->m_pRight = rightList; } else { rightList = root; } return leftList; } ``` 通过这样的递归方式，我们可以将二元查找树转换成排序的双向链表。在实际应用中，可以根据实际需求对这个算法进行优化，比如使用全局变量保存头尾节点，减少重复遍历，或者添加一些辅助函数来简化递归过程。希望这道题目可以帮助大家更好地理解递归算法和二叉树的操作，也希望大家可以通过这些经典题目加强自己的编程能力，更好地面对工作和面试挑战。