关键词：二叉树的层次遍历
0. 二叉树的遍历
二叉树的遍历是指：从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次，且仅被访问一次。
1. 二叉树的层次遍历
- 设计思路（游标）
提供一组遍历相关的函数，按层次访问二叉树中的数据元素。
| 函数 | 功能说明 |
|---|---|
| begin() | 初始化，准备进行遍历访问 |
| next() | 游标移动，指向下一个结点 |
| current() | 获取游标所指向的数据元素 |
| end() | 判断游标是否到达尾部 |
2. 层次遍历算法
- 原料：
class LinkQueue<T>; - 游标：
LinkQueue<T>::front()； - 思想：
-
begin()：将根节点压入队列中 -
current()：访问队头元素指向的数据元素 -
next()：队头元素弹出，将队头元素的孩子压入队列中 -
end()：判断队列是否为空
层次遍历算法示例
-
bool begin()
{
bool ret = ( root() != NULL ); // 判断根结点不为空
if( ret )
{
m_queue.clear(); // 先清空队列
m_queue.add(root()); // 将根结点添加到队列中
}
return ret;
}
bool end()
{
return (m_queue.length() == 0);
}
bool next()
{
bool ret = (m_queue.length() > 0);
if( ret )
{
BTreeNode<T>* node = m_queue.front(); // 取出对头元素
m_queue.remove();
if( node->left )
{
m_queue.add(node->left);
}
if( node->right )
{
m_queue.add(node->right);
}
}
return ret;
}
T current()
{
if( !end() )
{
return m_queue.front()->value;
}
else
{
THROW_EXCEPTION(InvalidOperationExcetion, "No value at current position...");
}
}
声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4
