首页 > 其他 > 详细

二叉搜索树与双向链表转换

时间:2014-12-02 17:30:15      阅读:148      评论:0      收藏:0      [点我收藏+]

题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中节点的指针指向。二叉树的结点定义如下:

struct BinaryTreeNode
{    
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
}

利用递归来解决问题

BinaryTreeNode* Convert(BinaryTreeNode* pRootOfTree)
{
    BinaryTreeNode* pLastNodeInList=NULL;
    ConvertNode(pRootOfTree,&pLastNodeInList);
    BinaryTreeNode *pHeadOfList=pLastNodeInList;
    while(pHeadOfList!=NULL&&pHeadOfList->m_pLeft!=NULL)
        pHeadOfList=pHeadOfList->m_pLeft;
    return pHeadOfList;
}

void ConvertNode(BinaryTreeNode* pNode,BinaryTreeNode** pLastNodeInList)
{
    if(pNode==NULL)
        return;
    
    BinaryTreeNode *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);
}


本文出自 “仙路千叠惊尘梦” 博客,请务必保留此出处http://secondscript.blog.51cto.com/9370042/1585498

二叉搜索树与双向链表转换

原文:http://secondscript.blog.51cto.com/9370042/1585498

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!