新建 文本文档 (6).txt

该软件会在用户的使用过程中自动进行调整达到最佳状态

二叉树遍历算法集合

费了两天时间写的,包括前中后序遍历的递归和非递归算法,还有层序遍历总共2*3 + 1 = 7中遍历二叉树的算法,感觉其中后序遍历的非递归算法比较困难,想了很久最后的实现还是不够优雅,请大家指正~~

总共三个文件,一个头文件,一个对应的cpp文件,还有一个用于测试的文件.

BinaryTree.h:

[code]
/********************************************************************
        created:        2006/07/04
        filename:         BinaryTree.h
        author:                李创
                http://www.cppblog.com/converse/

        purpose:        演示二叉树的算法
*********************************************************************/

#ifndef BinaryTree_H
#define BinaryTree_H

#include <stdlib.h>
#include <stack>

class BinaryTree
{
private:
        typedef int Item;
    typedef struct TreeNode
    {
        Item        Node;
        TreeNode*   pRight;
        TreeNode*   pLeft;

        TreeNode(Item node = 0, TreeNode* pright = NULL, TreeNode* pleft = NULL)
            : Node(node)
            , pRight(pright)
            , pLeft(pleft)
        {
        }

    }TreeNode, *PTreeNode;

public:
        enum TraverseType
        {
                PREORDER        = 0,                // 前序
                INORDER                = 1,                // 中序
                POSTORDER        = 2,                // 后序
                LEVELORDER        = 3                        // 层序
        };

    BinaryTree(Item Array[], int nLength);
    ~BinaryTree();

        PTreeNode GetRoot()
        {
                return m_pRoot;
        }

        // 遍历树的对外接口
        // 指定遍历类型和是否是非递归遍历,默认是递归遍历
        void Traverse(TraverseType traversetype, bool bRec = true);

private:
    PTreeNode   CreateTreeImpl(Item Array[], int nLength);
    void        DetroyTreeImpl(PTreeNode pTreenode);

    void        PreTraverseImpl(PTreeNode pTreenode);                // 递归前序遍历树
        void        InTraverseImpl(PTreeNode pTreenode);                // 递归中序遍历树
        void        PostTraverseImpl(PTreeNode pTreenode);                // 递归后序遍历树

        void        NoRecPreTraverseImpl(PTreeNode pTreenode);        // 非递归前序遍历树
        void        NoRecInTraverseImpl(PTreeNode pTreenode);        // 非递归中序遍历树
        void        NoRecPostTraverseImpl(PTreeNode pTreenode);        // 非递归后序遍历树

        void                LevelTraverseImpl(PTreeNode pTreenode);

    PTreeNode   m_pRoot;        // 根结点

        // 采用STL里面的stack作为模拟保存链表结点的stack容器
        typedef std::stack<BinaryTree::PTreeNode> TreeNodeStack;
};

#endif
[/code] 

converse 2006-7-8 06:50 
 
BinaryTree.cpp:
[code]
/********************************************************************
        created:        2006/07/04
        filename:         BinaryTree.cpp
        author:                李创
                                http://www.cppblog.com/converse/

        purpose:        演示二叉树的算法
*********************************************************************/

#include <iostream>
#include <assert.h>
#include <queue>
#include "BinaryTree.h"

BinaryTree::BinaryTree(Item Array[], int nLength)
        : m_pRoot(NULL)
{
        assert(NULL != Array);
        assert(nLength > 0);

        m_pRoot = CreateTreeImpl(Array, nLength);
}

BinaryTree::~BinaryTree()
{
        DetroyTreeImpl(m_pRoot);
}

// 按照中序递归创建树
BinaryTree::PTreeNode BinaryTree::CreateTreeImpl(Item Array[], int nLength)
{
        int mid = nLength / 2;
        PTreeNode p = new TreeNode(Array[mid]);

        if (nLength > 1)
        {
                p->pLeft    = CreateTreeImpl(Array, nLength / 2);
                p->pRight   = CreateTreeImpl(Array + mid + 1, nLength / 2 - 1);
        }

        return p;
}

void BinaryTree::DetroyTreeImpl(PTreeNode pTreenode)
{
        if (NULL != pTreenode->pLeft)
        {
                DetroyTreeImpl(pTreenode->pLeft);
        }
        if (NULL != pTreenode->pRight)
        {
                DetroyTreeImpl(pTreenode->pRight);
        }

        delete pTreenode;
        pTreenode = NULL;
}

// 遍历树的对外接口
// 指定遍历类型和是否是非递归遍历,默认是递归遍历
void BinaryTree::Traverse(TraverseType traversetype, bool bRec /*= true*/)
{
        switch (traversetype)
        {
        case PREORDER:        // 前序
                {                        
                        if (true == bRec)
                        {
                                std::cout << "递归前序遍历树\n";
                                PreTraverseImpl(m_pRoot);
                        }
                        else
                        {
                                std::cout << "非递归前序遍历树\n";
                                NoRecPreTraverseImpl(m_pRoot);
                        }
                }
                break;

        case INORDER:        // 中序
                {                        
                        if (true == bRec)
                        {
                                std::cout << "递归中序遍历树\n";
                                InTraverseImpl(m_pRoot);
                        }
                        else
                        {
                                std::cout << "非递归中序遍历树\n";
                                NoRecInTraverseImpl(m_pRoot);
                        }
                }
                break;

        case POSTORDER:        // 后序
                {                        
                        if (true == bRec)
                        {
                                std::cout << "递归后序遍历树\n";
                                PostTraverseImpl(m_pRoot);
                        }
                        else
                        {
                                std::cout << "非递归后序遍历树\n";
                                NoRecPostTraverseImpl(m_pRoot);
                        }
                }
                break;

        case LEVELORDER:        // 层序
                {
                        std::cout << "层序遍历树\n";
                        LevelTraverseImpl(m_pRoot);
                }
        }

        std::cout << std::endl;
}

// 递归前序遍历树
void BinaryTree::PreTraverseImpl(PTreeNode pTreenode)
{
        if (NULL == pTreenode)
                return;

        std::cout << "Item = " << pTreenode->Node << std::endl;

        PreTraverseImpl(pTreenode->pLeft);

        PreTraverseImpl(pTreenode->pRight);
}

// 非递归前序遍历树
void BinaryTree::NoRecPreTraverseImpl(PTreeNode pTreenode)
{
        if (NULL == pTreenode)
                return;

        TreeNodeStack NodeStack;
        PTreeNode pNode;
        NodeStack.push(pTreenode);

        while (!NodeStack.empty())
        {
                while (NULL != (pNode = NodeStack.top()))        // 向左走到尽头
                {
                        std::cout << "Item = " << pNode->Node << std::endl;        // 访问当前结点
                        NodeStack.push(pNode->pLeft);                                        // 左子树根结点入栈
                }
                NodeStack.pop();                                                                        // 左子树根结点退栈
                if (!NodeStack.empty())
                {
                        pNode = NodeStack.top();
                        NodeStack.pop();                                                                // 当前结点退栈