首页 > 代码库 > 将一棵二叉树转换为双向链表的俩中算法
将一棵二叉树转换为双向链表的俩中算法
要求:输入一棵二叉排序树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建新的结点,只能调整树中结点的指针的指向。如下图:
方法一:我们借助一个容器来顺序存储结点的指针,然后改变指针的指向。
1 //////////////////////二叉搜索树与双向链表(方法一)////////////////////////////////////////// 2 3 void Convertfirst(BinaryTreeNode* pRoot , vector<BinaryTreeNode*>& Vec) 4 { 5 if (pRoot) 6 { 7 Convertfirst(pRoot->m_pLeft , Vec); 8 Vec.push_back(pRoot); 9 Convertfirst(pRoot->m_pRight , Vec); 10 } 11 } 12 BinaryTreeNode* Convert1(BinaryTreeNode* pRoot) 13 { 14 if (!pRoot) 15 { 16 return NULL; 17 } 18 vector<BinaryTreeNode*> Vec ; 19 Convertfirst(pRoot ,Vec); 20 BinaryTreeNode* pHead = Vec[0]; 21 vector<BinaryTreeNode*>::iterator it = Vec.begin(); 22 for ( ; it != Vec.end()-1;it++) 23 { 24 (*it)->m_pRight = (*(it+1)) ; 25 (*(it+1))->m_pLeft = (*it) ; 26 } 27 28 return pHead ; 29 }
方法二:我们边遍历边改变指针的指向。
1 //////////////////////二叉搜索树与双向链表(方法二)////////////////// 2 void ConvertNode(BinaryTreeNode* pNode , BinaryTreeNode** pLastNodeList) 3 { 4 if (pNode) 5 { 6 ConvertNode(pNode->m_pLeft , pLastNodeList); 7 pNode->m_pLeft = *pLastNodeList; 8 if (*pLastNodeList != NULL) 9 { 10 (*pLastNodeList)->m_pRight = pNode ; 11 } 12 *pLastNodeList = pNode ; 13 ConvertNode(pNode->m_pRight , pLastNodeList); 14 } 15 } 16 17 BinaryTreeNode* Convert2(BinaryTreeNode* pRoot) 18 { 19 if (!pRoot) 20 { 21 return NULL; 22 } 23 BinaryTreeNode* pLastNodeList = NULL ; 24 ConvertNode(pRoot ,&pLastNodeList); 25 while (pLastNodeList && pLastNodeList->m_pLeft) 26 { 27 pLastNodeList = pLastNodeList->m_pLeft ; 28 } 29 30 return pLastNodeList; 31 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。