对于一颗完全二叉树，要求给所有节点加上一个pNext指针，指向同一层的相邻节点-----层序遍历的应用题

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

#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;}