当前位置:   article > 正文

数据结构——二叉树的操作 (层序遍历)(C++实现)

数据结构——二叉树的操作 (层序遍历)(C++实现)

我们今天接着来看二叉树的操作,如果还没有看过上一篇的可以点击这里:

https://blog.csdn.net/qq_67693066/article/details/138163494

统计叶子结点个数

叶子结点就是左右孩子都没有的结点:
在这里插入图片描述判断叶子结点就是判断是否有左右孩子,如果都没有就为叶子结点:

        if(root->_leftChild== nullptr && root->_rightChild == nullptr)
        {
            return 1;
        }
  • 1
  • 2
  • 3
  • 4

除了判断本身是否为叶子结点,我们也要到它的左右子树去看是否有叶子结点:

       if(root->_leftChild== nullptr && root->_rightChild == nullptr)
        {
            return 1;
        }

        return _TotalLeaves(root->_leftChild) +
        _TotalLeaves(root->_rightChild);
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

同时,我们要防止空树的情况:

    //叶子结点
    int _TotalLeaves( _Node* const& root)
    {
        if(root == nullptr)
        {
            return 0;
        }

        if(root->_leftChild== nullptr && root->_rightChild == nullptr)
        {
            return 1;
        }

        return _TotalLeaves(root->_leftChild) +
        _TotalLeaves(root->_rightChild);
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

我们再封装一次:

    //叶子结点个数
    int TotalLeaves()
    {
        return _TotalLeaves(_root);
    }
  • 1
  • 2
  • 3
  • 4
  • 5

我们可以测试一下:

#include "BTree.h"

int main()
{
    BTree<int> bt;

    bt.Insert(20);
    bt.Insert(12);
    bt.Insert(35);
    bt.Insert(22);
    bt.Insert(1);

    bt.PrveOrder();
    std::cout<<std::endl;
    bt.InOrder();
    std::cout<<std::endl;
    bt.PostOrder();
    std::cout<<std::endl;

    std::cout <<"叶子结点个数:" << bt.TotalLeaves() << std::endl;

    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

在这里插入图片描述

统计结点个数

统计结点个数,相对来说更简单,只要是一个结点,我们就返回1,表示一个结点:

    //统计结点个数
    int _NodeNumbers( _Node* const& root)
    {
        //防止空树的情况
        if(root == nullptr)
        {
            return 0;
        }

        return 1;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

统计完当前结点,还要统计它的左右子树的结点个数:

    int _NodeNumbers( _Node* const& root)
    {
        //防止空树的情况
        if(root == nullptr)
        {
            return 0;
        }

        return 1 + _NodeNumbers(root->_leftChild)
        + _NodeNumbers(root->_rightChild); //本身 + 它的左右子树
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
#include "BTree.h"

int main()
{
    BTree<int> bt;

    bt.Insert(20);
    bt.Insert(12);
    bt.Insert(35);
    bt.Insert(22);
    bt.Insert(1);

    bt.PrveOrder();
    std::cout<<std::endl;
    bt.InOrder();
    std::cout<<std::endl;
    bt.PostOrder();
    std::cout<<std::endl;

    std::cout <<"叶子结点个数:" << bt.TotalLeaves() << std::endl;
    std::cout <<"结点个数:" << bt.NodeNumber() << std::endl;

    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

在这里插入图片描述

层序遍历

层序遍历是一种较为特殊的遍历方式,它不依靠根,左子树,右子树的顺序,它是依靠二叉树的层数来遍历:
在这里插入图片描述
层次遍历是依次遍历各层的元素的算法,这种算法遍历出来就是每层的元素顺序。

层次遍历算法中我们要借助我们之前学过的数据结构——队列,因为在层次遍历算法中,我们依次要打印左孩子,右孩子,所以我们借助队列的性质,先入左孩子,然后出队时,左孩子最先被处理:

首先,每一层我们都可以用一个vector来储存:
在这里插入图片描述
然后用一个大的vector来储存这些vector:
在这里插入图片描述
然后我们用queue先压入根节点:
在这里插入图片描述然后20是第一层的vector,我们就压入第一层的vector:
在这里插入图片描述然后弹出20,将20的左孩子右孩子压入queue中:
在这里插入图片描述
然后将12压入vector[1],然后将12的左右孩子压入queue:

在这里插入图片描述然后将35压入vector[1]中,然后同样将35的左右孩子压入queue:
在这里插入图片描述然后同样的方法,将剩下的元素压入下一层的vector。了解了思想之后,我们开始写代码:

非递归方式

    // 定义一个函数 LevelOrder,用于实现二叉树的层序遍历
    std::vector<std::vector<T>> _LevelOrder(_Node* const& root)
    {

        // 初始化结果容器,用于存放层序遍历得到的数据,每一层数据作为一个子向量存入
        std::vector<std::vector<T>> result;
        // 使用队列辅助遍历,初始时仅包含根节点
        std::queue<_Node*> queue;

        // 如果根节点为空,则直接返回空结果集
        if (!root)
        {
            return result;
        }

        // 将根节点压入队列
        queue.push(root);
        
        // 当队列非空时,继续进行遍历
        while (!queue.empty())
        {
            // 初始化一个临时向量,用于存储当前层的所有节点数据
            std::vector<T> curResult;

            // 记录当前层队列的大小(即节点数)
            int curSize = queue.size();
            // 遍历当前层的所有节点
            for (int i = 0; i < curSize; i++)
            {
                // 弹出队首节点
                _Node* front = queue.front();
                queue.pop();

                // 将当前节点的数据添加到当前层结果向量中
                curResult.push_back(front->_data);

                // 若当前节点有左子节点,将其压入队列,等待下一层遍历
                if (front->_leftChild)
                    queue.push(front->_leftChild);

                // 若当前节点有右子节点,将其压入队列,等待下一层遍历
                if (front->_rightChild)
                    queue.push(front->_rightChild);
            }

            // 将当前层遍历结果添加到总结果集中
            result.push_back(curResult);
        }

        // 遍历完成后,返回层序遍历结果集
        return result;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53

递归方式

除了非递归方式,我们发现上面的方式都是一个模子里面刻出来的,所以我们也可以用递归的方式:

如果用递归方式,我们就不用队列来辅助了,因为每一次递归都会开一个新的函数栈帧,我们可以利用这个栈帧来区分层次:

// 定义一个成员函数 LevelOrder,用于获取二叉树的层序遍历结果
std::vector<std::vector<T>> LevelOrder()
{
    // 初始化结果容器,用于存放层序遍历得到的数据,每一层数据作为一个子向量存入
    std::vector<std::vector<T>> result;

    // 调用辅助递归函数,从根节点开始遍历
    LevelOrderHelper(_root, 0, result);

    // 返回层序遍历结果集
    return result;
}

// 定义一个私有辅助递归函数 LevelOrderHelper,用于实现二叉树的层序遍历
void LevelOrderHelper(_Node* root, int level, std::vector<std::vector<T>>& result)
{
    // 如果当前节点为空,直接返回
    if (!root)
    {
        return;
    }

    // 如果当前层级超出了结果容器的范围,添加一个新的子向量
    if (result.size() <= level)
    {
        result.push_back(std::vector<T>());
    }

    // 将当前节点的数据添加到对应层级的子向量中
    result[level].push_back(root->_data);

    // 递归遍历左子树,传入下一层级编号
    LevelOrderHelper(root->_leftChild, level + 1, result);

    // 递归遍历右子树,传入下一层级编号
    LevelOrderHelper(root->_rightChild, level + 1, result);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37

这段代码定义了一个成员函数 LevelOrder,用于获取当前二叉树的层序遍历结果。它首先初始化一个结果容器,然后调用私有辅助递归函数 LevelOrderHelper,从根节点开始遍历,并将遍历结果存储在结果容器中。最后返回这个结果容器。

辅助递归函数 LevelOrderHelper 接收当前节点、所在层级以及结果容器作为参数。递归过程中,首先检查当前节点是否为空,若为空则直接返回。接着检查当前层级是否已存在于结果容器中,若不存在则添加一个新子向量。然后将当前节点数据添加到对应层级的子向量中。最后分别递归遍历左、右子树,传入下一层级编号。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小蓝xlanll/article/detail/496082
推荐阅读
相关标签
  

闽ICP备14008679号