把二元查找树转变成排序的双向链表
题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表,要求不能创建任何新节点,只调整指针指向。
比如将二元查找树
10
/
6 14
/ /
4 8 12 16
转换成双向链表4=6=8=10=12=14=16
分析:
思路一:当到达某一节点准备调整以该节点为根节点的子树时,先调整其左子树将左子树转换成一个排好序的左子链表,再调整其右子树转换右子链表。最近链接左子链表的最右节点(左子树的最大节点)、当前节点和有子链表的最左节点(右子树的最小节点)。从树的根节点开始递归调整所有节点。
首先定义二元查找树的数据结构如下:
structBSTreeNode
{
int m_nValue;
BSTreeNode *m_pLeft;
BSTreeNode *m_pRight;
}
BSTreeNode*ConvertNode(BSTreeNode* pNode, bool asRight)
{
if (!pNode)
returnNULL;
BSTreeNode *pLeft = NULL;
BSTreeNode* pRight = NULL;
//Convert the left sub-tree
if(pNode -> m_pLeft)
pLeft = ConvertNode(pNode ->m_pLeft, false);
//Convert the greatest node in the leftsub-tree to the current node
if (pLeft)
{
pLeft -> m_pRight = pNode;
pNode -> m_pLeft = pLeft;
}
//Convert the right sub-tree
if (pNode -> m_pRight)
pRight= ConvertNode (pNode -> m_pRight, true);
//Connect the least node in the rightsub-tree to the current node
if (pRight)
{
pNode-> m_pRight = pRight;
pRight-> m_pLeft = pNode;
}
BSTreeNode *pTemp = pNode;
//If the current node is the right child ofits parent, return the least node in the tree whose root is the current node
if (asRight)
{
while(pTemp -> m_pLeft)
pTemp= pTemp -> m_pLeft;
}
//if the current node is the left child ofits parent, return the greatest node in the tree whose root is the current node
else
{
while(pTemp -> m_pRight)
pTemp= pTemp -> m_pRight;
}
return pTemp;
//Convert a BSTree into a sorteddouble-linked list
BSTreeNode* Convert(BSTreeNode* pHeadOfTree)
{
returnConvertNode(pHeadOfTree, true);
}
思路二:中序遍历二叉树。较小节点先访问。如果访问一个节点,假设之前访问过的节点已经调整成一个排序的双向链表,再把调整当前节点的指针将其连接到链表末尾,当所有节点都访问过之后,整棵树也就转换为一个排序的双向链表了。
voidConvertNode(BSTreeNode* pNode, BSTreeNode*& pLastNodeInList) { if(pNode ==NULL) return; BSTreeNode *pCurrent = pNode; //Convert the left sub-tree if (pCurrent -> m_pLeft !=NULL) ConvertNode(pCurrent-> m_pLeft, pLastNodeInList); //Put the current node into thedouble-linked list pCurrent -> m_pLeft = pLastNodeInList; if(pLastNodeInList != NULL) pLastNodeInList-> m_pRight = pCurrent; pLastNodeInList = pCurrent; //Convert the right sub-tree if (pCurrent -> m_pRight != NULL) ConvertNode(pCurrent-> m_pRight, pLastNodeInList); //Convert a BSTree into a sorteddouble-linked list BSTreeNode* Convert_Solution(BSTreeNode*pHeadOfTree) { BSTreeNode*pLastNodeInList = NULL; ConvertNode(pHeadOfTree,pLastNodeInList); //Getthe head of the double-linked list BSTreeNode*pHeadOfList = pLastNodeInList; while(pHeadOfList && pHeadOfList -> m_pLeft) pHeadOfList= pHeadOfList -> m_pLeft; return pHeadOfList; } }