完全二叉树指向同一层的相邻结点

本文主要是介绍完全二叉树指向同一层的相邻结点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：对于一颗完全二叉树，要求给所有节点加上一个pNext指针，指向同一层的相邻节点；如果当前节点已经是该层的最后一个节点，则将pNext指针指向NULL；给出程序实现，并分析时间复杂度和空间复杂度。

答：时间复杂度为O(n),空间复杂度为O(1)。

#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <vector>using namespace std;struct TreeNode 
{int m_nValue;TreeNode *m_pLeft;TreeNode *m_pRight;TreeNode *pNext;
};//假定所创建的二叉树如下图所示
/*1/     \2       3/ \      / \4   5    6   7/ \  / \  / \8   9 10 11 12 13
*/
void CreateBitree(TreeNode *&pNode, fstream &fin)
{int dat;fin>>dat;if(dat == 0){pNode = NULL;}else {pNode = new TreeNode();pNode->m_nValue = dat;pNode->m_pLeft = NULL;pNode->m_pRight = NULL;pNode->pNext = NULL;CreateBitree(pNode->m_pLeft, fin);      CreateBitree(pNode->m_pRight, fin); }
}//完全二叉树指向同一层的相邻结点
void Solution(TreeNode *pHead)
{if (NULL == pHead){return;}vector<TreeNode*> vec;vec.push_back(pHead);TreeNode *pre = NULL;TreeNode *pNode = NULL;int cur = 0;int last = 0;while(cur < vec.size()){last = vec.size();while (cur < last){if (NULL == pre){pre = vec[cur];}else{pre->pNext = vec[cur];}if (NULL != vec[cur]->m_pLeft){vec.push_back(vec[cur]->m_pLeft);}if (NULL != vec[cur]->m_pRight){vec.push_back(vec[cur]->m_pRight);}pre = vec[cur];cur++;}pre->pNext = NULL;pre = NULL;}
}int _tmain(int argc, _TCHAR* argv[])
{fstream fin("tree.txt");TreeNode *pHead = NULL;TreeNode *pNode = NULL;CreateBitree(pHead, fin);Solution(pHead);while (NULL != pHead){cout<<pHead->m_nValue<<"  ";pNode = pHead->pNext;while (NULL != pNode){cout<<pNode->m_nValue<<"  ";pNode = pNode->pNext;}cout<<endl;pHead = pHead->m_pLeft;}cout<<endl;return 0;
}