66_二叉树结构的层次遍历

关键词：二叉树的层次遍历

0. 二叉树的遍历

二叉树的遍历是指：从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次，且仅被访问一次。

1. 二叉树的层次遍历

• 设计思路（游标）

提供一组遍历相关的函数，按层次访问二叉树中的数据元素。

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