关于二叉树的层次遍历的花样(c++实现)

本文主要是介绍关于二叉树的层次遍历的花样(c++实现)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

花样变形1：:二叉树层次遍历但是分层打印

分析：与普通打印多了一个分层打印，其实只要在在层次遍历中多设置一个标记变量即可
代码如下:

//二叉树的层次遍历
void levelTravel(BTNode *bt)
{if (bt == NULL){return;}queue<BTNode *> nodeQueue;nodeQueue.push(bt);nodeQueue.push(NULL); //放入空节点，作为层的结束符while (nodeQueue.size()){BTNode *pNode = nodeQueue.front(); //取队首元素nodeQueue.pop();  //必须出队列if (pNode)  //该节点非空{cout << pNode->data << ' ';if (pNode->lchild)  //左孩子{nodeQueue.push(pNode->lchild);}if (pNode->rchild)   //右孩子{nodeQueue.push(pNode->rchild);}}//如果结点为空并且队列非空，则是一行访问结束，下一行的入队列结束，因此压入一个空指针  //若队列也是空，则说明已访问完毕else if (nodeQueue.size()){nodeQueue.push(NULL);cout << endl;}}
}

可以看出我们通过设置了空节点来表示一层的结束，这样就可以很好的实现分层打印。

花样变形2：将二叉树分层打印的同时，将每层的数据保存下来

void levelTravel2(BTNode *bt)
{vector<vector<int>> result; //存放所有层的节点vector<int> cur; //存放每一层的节点if (bt == NULL){return;}queue<BTNode *> nodeQueue;nodeQueue.push(bt);nodeQueue.push(NULL); //放入空节点，作为层的结束符while (nodeQueue.size()){BTNode *pNode = nodeQueue.front(); //取队首元素nodeQueue.pop();  //必须出队列if (pNode)  //该节点非空{cout << pNode->data << ' ';cur.push_back(pNode->data);if (pNode->lchild)  //左孩子{nodeQueue.push(pNode->lchild);}if (pNode->rchild)   //右孩子{nodeQueue.push(pNode->rchild);}}//如果结点为空并且队列非空，则是一行访问结束，下一行的入队列结束，因此压入一个空指针  //若队列也是空，则说明已访问完毕else {result.push_back(cur);cur.resize(0);if (nodeQueue.size())nodeQueue.push(NULL);cout << endl;}}//for (int i = 0; i < result.size(); i++)//{//  vector<int>a = result[i];//  for (int j = 0; j < a.size(); j++)//  {//      //cout << a[j] << ' ';//      printf("%c ", a[j]);//  }//  cout << endl;//}
}