邢台做网站地方/广州发布紧急通知

1-题目 :
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表；要求不能创建任何新的结点，只能调整指针的方向。

2-示例 :

将转变为4=6=8=10=12=14=16

3-思路 :
很多与树相关的题目都是用递归的思路来解决 :
3.1-思路1 : 当到达某一结点准备调整以该结点为根的子树时，先调整其左子树将左子树转换为一个排好序的左子链表，再调整其右子树将右子树转换为一个排好序的右子链表；链接左子链表的最右结点(左子树的最大结点)=当前结点=右子链表的最左结点(右子树的最小结点)；从树的根结点开始递归调整所有结点。
3.2-思路2 : 可以中序遍历整棵树，较小的结点先访问；每访问一个结点，假设之前访问过的结点已经调整成一个排好序的双向链表，再调整当前结点的指针将其链接到链表的末尾；那么当遍历结束，整棵树也就转换成了一个排序的双向链表了。

4-代码 :

//思路1对应代码
//二元查找树的一个结点
struct BSTreeNode
{int m_nValue; //结点的值BSTreeNode *m_pLeft; //结点的左孩子 BSTreeNode *m_pRight; //结点的右孩子 
};//输入 : pNode-子树的头结点; asRight-该结点是否是其父结点的右孩子
//输出 : 若asRight为true,返回右子树的最小结点; 若asRight为false,返回左子树的最大结点
BSTreeNode* ConvertNode(BSTreeNode* pNode, bool asRight)
{//若子树为空,返回NULLif(!pNode) return NULL;BSTreeNode *pLeft = NULL;BSTreeNode *pRight = NULL;//转换左子树if(pNode->m_pLeft){pLeft = ConvertNode(pNode->m_pLeft, false);}//将左子树的最大结点与当前结点双向链接if(pLeft){pLeft->m_pRight = pNode;pNode->m_pLeft = pLeft;}//转换右子树if(pNode->m_pRight){pRight = ConvertNode(pNode->m_pRight, true);}//将右子树的最小结点与当前结点双向链接if(pRight){pNode->m_pRight = pRight;pRight->m_pLeft = pNode;}BSTreeNode *pTemp = pNode;//若当前结点是其父结点的右孩子,则返回以当前结点为根的子树的最小结点if(asRight){while(pTemp->m_pLeft){pTemp = pTemp->m_pLeft;}}//若当前结点是其父结点的左孩子,则返回以当前结点为根的子树的最大结点else{while(pTemp->m_pRight){pTemp->m_pRight;}}return pTemp;
}BSTreeNode* Convert(BSTreeNode* pHeadOfTree)
{//若想返回排序好的双向链表的头指针,则将pHeadOfTree设为truereturn ConvertNode(pHeadOfTree, true);
}

//思路2对应代码
//输入 : pNode-子树的头结点; pLastNodeInList-双向链表的尾结点
void ConvertNode(BSTreeNode* pNode, BSTtreeNode*& pLastNodeInList)
{if(pNode == NULL) return NULL;BSTreeNode *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);}
}//输入 : pHeadOfTree-树的头结点
//输出 : 排序好的双向链表的头结点
BSTreeNode* Convert(BSTreeNode* pHeadOfTree)
{BSTreeNode *pLastNodeInList = NULL;ConvertNode(pHeadOfTree, pLastNodeInList);//获取双向链表的头结点BSTreeNode *pHeadOfList = pLastNodeInList;while(pHeadOfList && pHeadOfList->m_pLeft){pHeadOfList = pHeadOfList->m_pLeft;}return pHeadOfList;
}