首页 > 代码库 > 将一棵二叉树转换为双向链表的俩中算法

将一棵二叉树转换为双向链表的俩中算法

2024-07-03 11:48:24   227人阅读

要求：输入一棵二叉排序树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建新的结点，只能调整树中结点的指针的指向。如下图：

方法一：我们借助一个容器来顺序存储结点的指针，然后改变指针的指向。

 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 }

 


联系
我们