C++数据结构：二叉树（二）——二叉树的遍历

逃离我推掉我的手 2022-06-06 04:27 308阅读 0赞

## 一、序言 ##

在上一篇文章中[《二叉树的先序创建》][Link 1]，我们介绍了二叉树的基本结构以及先序建立二叉树，在本篇文章中，我们要对二叉树进行遍历，包括：

*  层序遍历
 *  递归先序遍历、递归中序遍历、递归后序遍历
 *  非递归中序遍历

--------------------

## 二、二叉树的遍历 ##

BiTree.h 头文件新增定义如下，其余部分不变，请参考[《二叉树的先序创建》][Link 1]：

class BiTree
    {
    public:
        void LevelOrder();                  //层序遍历
        void PreOrder();                    //先序递归遍历二叉树
        void InOrder();                     //中序递归遍历二叉树
        void PostOrder();                   //后序递归遍历二叉树
    
        void InOrder2();                    //中序非递归遍历二叉树
    
    };

BiTree.cpp 文件新增定义如下，其余部分不变

#include "BiTree.h"
    #include <iostream>
    #include <queue>
    #include <stack>
    using namespace std;
    static void LevelTraverse(BiTNode *ptree);  //层序遍历二叉树
    static void PreTraverse(BiTNode *ptree);    //递归先序遍历二叉树
    static void InTraverse(BiTNode *ptree);     //递归中序遍历二叉树
    static void PostTraverse(BiTNode *ptree);   //递归后序遍历二叉树
    static void visit(BiTNode *ptree);          //打印数据
    
    //操作：  层序遍历二叉树
    //操作前：无参数
    //操作后：打印出层序遍历结果
    void BiTree::LevelOrder()
    {
        cout << "层序遍历二叉树:";
        if (this->root != nullptr)
            LevelTraverse(this->root);      //调用层序遍历二叉树函数
        else
            cout << "二叉树为空" << endl;
        cout << endl;
    
    }
    static void LevelTraverse(BiTNode *ptree)
    {
        /*
        1.构造辅助队列(我们将直接使用queue库中提供的函数)
        2.先将二叉树的根节点入队，然后出队，访问该节点
        3.如果它有左子树，则将左子树根节点入队
        4.如果它有右子树，则将右子树根节点入队
        5.出队，访问出队节点，如此反复，直到队列为空
        */
        queue<BiTNode *> BiTNodeQueue;                      //队列类型是指向节点的指针类型
        BiTNodeQueue.push(ptree);                           //指向头节点的指针入队
        while (!BiTNodeQueue.empty())                       //队列不为空
        {
            BiTNode *FrontNode = BiTNodeQueue.front();      //队首元素
            visit(FrontNode);                               //访问队首元素
            BiTNodeQueue.pop();                             //队首元素出队
            if (FrontNode->lchild != nullptr)               //如果队首元素这个指针有左孩子则让其入队列
                BiTNodeQueue.push(FrontNode->lchild);
            if (FrontNode->rchild != nullptr)               //如果队首元素这个指针有右孩子则让其入队列
                BiTNodeQueue.push(FrontNode->rchild);
        }//while
    }
    
    //操作：  先序递归遍历二叉树
    //操作前：无参数
    //操作后：打印出先序遍历结果
    void BiTree::PreOrder()
    {
        cout << "先序遍历二叉树:";
        if (this->root != nullptr)
            PreTraverse(this->root);    //调用先序遍历二叉树函数
        else
            cout << "二叉树为空" << endl;
        cout << endl;
    
    }
    static void PreTraverse(BiTNode *ptree)
    {
        if (ptree != nullptr)
        {
            visit(ptree);
            PreTraverse(ptree->lchild);
            PreTraverse(ptree->rchild);
        }
    }
    
    //操作：  中序递归遍历二叉树
    //操作前：无参数
    //操作后：打印出中序遍历结果
    void BiTree::InOrder()
    {
        cout << "中序遍历二叉树:";
        if (this->root != nullptr)
            InTraverse(this->root);     //调用中序遍历二叉树函数
        else
            cout << "二叉树为空" << endl;
        cout << endl;
    }
    static void InTraverse(BiTNode *ptree)
    {
        if (ptree != nullptr)
        {
            InTraverse(ptree->lchild);
            visit(ptree);
            InTraverse(ptree->rchild);
        }
    }
    //操作：  后序递归遍历二叉树
    //操作前：无参数
    //操作后：打印出后序遍历结果
    void BiTree::PostOrder()
    {
        cout << "后序遍历二叉树:";
        if (this->root != nullptr)
            PostTraverse(this->root);       //调用后序遍历二叉树函数
        else
            cout << "二叉树为空" << endl;
        cout << endl;
    }
    static void PostTraverse(BiTNode *ptree)
    {
        if (ptree != nullptr)
        {
            PostTraverse(ptree->lchild);
            PostTraverse(ptree->rchild);
            visit(ptree);
        }
    }
    
    //操作：  中序非递归遍历二叉树
    //操作前：无参数
    //操作后：打印出中序遍历结果
    void BiTree::InOrder2()
    {
        cout << "中序非递归遍历二叉树:";
        if (this->root != nullptr)
        {
            stack<BiTNode *> BiTNodeStack;
            BiTNode *ptree = this->root;
            while (ptree != nullptr || !BiTNodeStack.empty())   //栈不为空或者ptree不为空时则循环
            {
                if (ptree != nullptr)                           //每当根节点不为空时
                {
                    BiTNodeStack.push(ptree);                   //根节点入栈
                    ptree = ptree->lchild;                      //ptree指向左子树的根，遍历左子树
                }
                else                                            //每当根节点为空，说明左子树到头了
                {
                    BiTNode *TopStack = BiTNodeStack.top();     //当前栈顶元素为最左节点
                    visit(TopStack);                            //访问栈顶元素
                    BiTNodeStack.pop();                         //栈顶元素出栈，出栈后的新栈顶元素为刚出栈元素的根节点
                    ptree = TopStack->rchild;                   //遍历刚出栈元素的右子树
                }
            }//while
    
        }
        else
            cout << "二叉树为空" << endl;
        cout << endl;
    }
    
    static void visit(BiTNode *ptree)
    {
        cout << ptree->data << " ";
    }

BiTree.cpp 文件定义如下

#include "BiTree.h"
    #include <iostream>
    using namespace std;
    int main()
    {
        BiTree tree;
        tree.CreateBiTree();    //先序建立二叉树
        tree.GetBiTRoot();      //获取二叉树的根节点数据
        tree.GetBiTNum();       //获取二叉树的总节点个数
        tree.GetBiTDepth();     //获取二叉树的深度
        tree.LevelOrder();      //二叉树的层序遍历
        tree.PreOrder();        //二叉树的递归先序遍历
        tree.InOrder();         //二叉树的递归中序遍历
        tree.InOrder2();        //二叉树的非递归中序遍历
        tree.PostOrder();       //二叉树的递归后序遍历
        system("pause");
        return EXIT_SUCCESS;
    }

## 三、运行结果 ##

输入二叉树如下图所示  
  
![输入二叉树][SouthEast]  
运行结果  
  
![这里写图片描述][SouthEast 1]

--------------------

如有不对的地方欢迎大家指正交流

[Link 1]: http://blog.csdn.net/S_a_b_e_r_/article/details/78394033
[SouthEast]: /images/20220606/2aac6803eabb4fa5ae753b31f65b47ae.png
[SouthEast 1]: /images/20220606/367edb983be442d2ac8c9230b85a8934.png