67_二叉树的典型遍历方式

关键词：先序遍历、中序遍历、后序遍历

0. 先序遍历（Pre-Order Traversal)

• 二叉树为空：
  无操作，直接返回
• 二叉树不为空：
  1. 访问根结点中的数据元素
  2. 先序遍历左子树
  3. 先序遍历右子树

先序遍历示意图

1. 中序遍历（In-Order Traversal）

• 二叉树为空：
  无操作，直接返回
• 二叉树不为空：
  1. 中序遍历左子树
  2. 访问根结点中的数据元素
  3. 中序遍历右子树

中序遍历示意图

2. 后序遍历（Post-Order Traversal）

• 二叉树为空：
  无操作，直接返回
• 二叉树不为空：
  1. 后序遍历左子树
  2. 后序遍历右子树
  3. 访问根结点中的数据元素

后序遍历示意图

3. 如何将二叉树中典型遍历算法集成到BTree中？

设计要点：

• 不能与层次遍历函数冲突，必须设计新的函数接口
• 算法执行完成后，能够方便的获得遍历结果
• 遍历结构能够反映结点访问的先后次序

函数接口设计:
SharedPointer< Array<T> > traversal(BTTraversal order)

• 根据参数order选择执行遍历算法（先序，中序，后序）
• 返回值为堆空间中的数组对象（生命周期由智能指针管理）
• 数组元素的次序反映遍历的先后次序

    void preOrderTraversal(BTreeNode<T>* node, LinkQueue<BTreeNode<T>*>& queue)
    {
        if( node != NULL )
        {
            queue.add(node);
            preOrderTraversal(node->left, queue);
            preOrderTraversal(node->right, queue);
        }
    }

    void inOrderTraversal(BTreeNode<T>* node, LinkQueue<BTreeNode<T>*>& queue)
    {
        if( node != NULL )
        {
            inOrderTraversal(node->left, queue);
            queue.add(node);
            inOrderTraversal(node->right, queue);
        }
    }

    void postOrderTraversal(BTreeNode<T>* node, LinkQueue<BTreeNode<T>*>& queue)
    {
        if( node != NULL )
        {
            postOrderTraversal(node->left, queue);
            postOrderTraversal(node->right, queue);
            queue.add(node);
        }
    }

    SharedPointer< Array<T> > traversal(BTTraversal order)
    {
        DynamicArray<T>* ret = NULL;
        LinkQueue<BTreeNode<T>*> queue;

        switch(order){
        case PreOrder:
            preOrderTraversal(root(), queue);
            break;
        case InOrder:
            inOrderTraversal(root(), queue);
            break;
        case PostOrder:
            postOrderTraversal(root(), queue);
            break;
        default:
            THROW_EXCEPTION(InvalidParameterExcetion, "Parameter order is invalid ...");
            break;
        }

        ret = new DynamicArray<T>(queue.length());

        if( ret != NULL )
        {
            for(int i=0; i<ret->length(); ++i, queue.remove())
            {
                ret->set(i, queue.front()->value);
            }
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryExcetion, "No memory to create a dynamic array ...");
        }

        return ret;
    }

4. 小结

• 二叉树的典型遍历都是以递归方式执行的
• BTree以不同的函数接口支持典型遍历
• 层次遍历与典型遍历互不冲突
• 遍历结果能够反映树结点访问的先后次序

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