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;
}

到此这篇关于c++实现版本层次遍历功能的文章就介绍到这了,更多相关c++层次遍历内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！