首页 > 代码库 > 二叉搜索树与双向链表转换
二叉搜索树与双向链表转换
题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中节点的指针指向。二叉树的结点定义如下:
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
二叉搜索树与双向链表转换
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。