69_二叉树的线索化实现

关键词：二叉树的额线索化

0. 什么是线索化二叉树？

• 将二叉树转换为双向链表的过程（非线性==》线性）
• 能够反映某种二叉树的遍历次序（结点的先后访问次序）
  利用结点的right指针指向遍历中的后继结点，利用结点的left指针指向遍历中的前驱结点。

1. 如何对二叉树进行线索化？

二叉树线索化的思维过程
二叉树的线索化

2. 课程目标

• 新增功能函数traversal(order, queue)
• 新增遍历方式：BTTraveral::LevelOrder
• 新增共有函数：BTreeNode<T>* thread(BTraversal order)
• 消除遍历和线索化的代码冗余（代码重构）

3. 新增功能函数traversal(order, queue)

    void traversal(BTTraversal order, LinkQueue<BTreeNode<T>*>& queue)
    {
        switch(order)
        {
            case PreOrder:
                PreOrderTraversal(root(),queue);
                break;
            case InOrder:
                InOrderTraversal(root(), queue);
                break;
            case PostOrder:
                PosOrderTraversal(root(), queue);
                break;
            default:
                THROW_EXCEPTION(InvalidParameterExcetion, "Parameter order is invalid...");
                break;
        }
    }

4. 新增遍历方式：BTTraveral::LevelOrder

层次遍历流程图

    void LevelOrderTraversal(BTreeNode<T>* node,LinkQueue<BTreeNode<T>*>& queue)
    {
        if( node != NULL )
        {
            LinkQueue<BTreeNode<T>*> tmp;

            tmp.add(node);

            while( tmp.length() > 0 )
            {
                BTreeNode<T>* n = tmp.front();

                if( n->left != NULL )
                {
                    tmp.add(n->left);
                }

                if( n->right != NULL )
                {
                    tmp.add(n->right);
                }

                tmp.remove();

                queue.add(n);
            }
        }
    }

5. 新增共有函数：BTreeNode<T>* thread(BTraversal order)

• 函数接口设计：BTreeNode<T>* thread(BTTraversal order)
  • 根据参数order选择线索化的次序（先序、中序、后序、层次）
  • 返回值为线索化之后指向链表首结点的指针
  • 线索化执行结束之后对应的二叉树变为空树
    线索化流程图
    conect算法示意图

    BTreeNode<T>* connect(LinkQueue<BTreeNode<T>*>& queue)
    {
        BTreeNode<T>* ret = NULL;

        if( queue.length() > 0 )
        {
            ret = queue.front();

            BTreeNode<T>* slider = queue.front();
            queue.remove();
            slider->left = NULL;

            while( queue.length() > 0 )
            {
                slider->right = queue.front();
                queue.front()->left = slider;
                slider = queue.front();
                queue.remove();
            }

            slider->right = NULL;
        }

        return ret;
    }

    BTreeNode<T>* thread(BTTraversal order)
    {
        BTreeNode<T>* ret = NULL;

        LinkQueue<BTreeNode<T>*> queue;

        traversal(order, queue);

        ret = connect(queue);

        this->m_root = NULL;

        this->m_queue.clear();

        return ret;
    }

6. 小结

• 线索化是将二叉树转化为双向链表的过程
• 线索化之后结点间的先后次序符合某种遍历次序
• 线索化操作将破坏原二叉树结点间的父子关系
• 线索化之后二叉树将不再管理结点的生命周期

声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4