关键词：层次遍历
0. 问题：如何按层次遍历通用树结构中的每一个数据元素？
- 当前的事实：树是非线性的数据结构，树的结点没有固定的编号方式
- 新的需求：为通用树结构提供新的方法，快速遍历每一个结点
1. 设计思路（游标）
- 在树中定义一个游标（
GTreeNode<T>*） - 遍历开始前将游标指向根结点（
root()） - 获取游标指向的数据元素
- 通过结点中的
child成员移动游标
提供一组遍历相关的函数，按层次访问树中的数据元素
| 函数 | 功能说明 |
|---|---|
| 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 )
{
GTreeNode<T>* node = m_queue.front(); // 取出对头元素
m_queue.remove();
for(node->child.move(0); !node->child.end(); node->child.next()) // 将对头元素的子结点压入队列中
{
m_queue.add(node->child.current());
}
}
return ret;
}
T current()
{
if( !end() )
{
return m_queue.front()->value;
}
else
{
THROW_EXCEPTION(InvalidOperationExcetion, "No value at current position...");
}
}
3. 小结
- 树中的结点没有固定的编号方式
- 可以按照层次关系对树中的结点进行遍历
- 通过游标的思想设计遍历成员函数
- 遍历成员函数是相互依赖，相互配合的关系
- 遍历算法的核心为队列的使用
声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4
