c++层次遍历 c++实现版本层次遍历功能

时间:2021-08-06 花与不易🐟 人气:0

想了解c++实现版本层次遍历功能的相关内容吗，花与不易🐟在本文为您仔细讲解c++层次遍历的相关知识和一些Code实例，欢迎阅读和指正，我们先划重点：c++层次遍历,c++遍历，下面大家一起来学习吧。

采用队列实现，BFS，功能：BFS层次遍历打印、按照节点将BFS序列化成一个字符。

#include <iostream>
#include <string>
#include <queue>
using namespace std;
struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};

//迭代打印层次遍历
void BFSTraverse(TreeNode* root)
{
    queue<TreeNode*> nodeQueue;
    nodeQueue.push(root);//先把第一个先放到列表里面
    while (!nodeQueue.empty())
    {
        int sz = nodeQueue.size();//这个是为了一层一层的数值进行处理
        for (int i = 0; i < sz; i++)
        {
            //那就取出那个节点进行处理
            TreeNode* node = nodeQueue.front();
            cout << node->val << ", ";
            nodeQueue.pop();
            if (node->left)
            {
                nodeQueue.push(node->left);
            }
            if (node->right)
            {
                nodeQueue.push(node->right);
            }
        }
    }
}


//按照节点进行序列化成一个字符串
string serialByBFS(TreeNode* root)
{
    if (root == nullptr)
        return "#!";
    queue<TreeNode*> nodeQueue;
    nodeQueue.push(root);
    string res;
    while (!nodeQueue.empty())
    {
        int sz = nodeQueue.size();
        for (int i = 0; i < sz; i++)
        {
            TreeNode* node = nodeQueue.front();
            nodeQueue.pop();
            if (node)
            {
                res = res + std::to_string(node->val) + '!';
                nodeQueue.push(node->left);
                nodeQueue.push(node->right);
            }
            else
            {
                res = res + "#!";
            }
        }
    }
    return res;
}


int main3()
{
    TreeNode* head = new TreeNode(5);
    head->left = new TreeNode(3);
    head->right = new TreeNode(8);
    head->left->left = new TreeNode(1);
    head->left->right = new TreeNode(2);
    head->right->left = new TreeNode(4);
    head->right->right = new TreeNode(5);
    head->right->left->left = new TreeNode(6);
    head->right->right->left = new TreeNode(9);
    head->right->right->right = new TreeNode(11);

    cout << "traverse1:";
    BFSTraverse(head);
    cout << "\nserial binary:";
    string res = serialByBFS(head);
    cout << res << endl;

    return 0;
}

ps：下面看下C++层次遍历

/*
*   description:层次遍历
*   writeby:    nick
*   date:       2012-10-22 23:56
*/
#include <iostream>
#include <queue>

using namespace std;

struct node
{
    int item;
    node *l, *r;
    node(int n)
    {
        item=n;
        l=0;
        r=0;
    }
};
typedef node *link;


void traverse(link h, void visit(link))
{
    queue<link> q;
    q.push(h);
    while(!q.empty())
    {
        h = q.front();
        q.pop();
        visit(h);
        if(h->l != 0) q.push(h->l);
        if(h->r !=0) q.push(h->r);
    }
}

void visit(link p)
{
    cout << p->item <<  " ";
}

int main()
{
    link root = new node(4);
    root->l = new node(5);
    root->r = new node(6);
    root->l->l = new node(7);
    root->l->r = new node(8);

    cout << "中文";
    traverse(root, visit);

    return 0;
}

加载全部内容