c++實現(xiàn)版本層次遍歷功能

更新時間：2021年08月06日 11:15:45 作者：花與不易🐟

這篇文章主要介紹了c++實現(xiàn)版本層次遍歷功能,本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下

采用隊列實現(xiàn)，BFS，功能：BFS層次遍歷打印、按照節(jié)點將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();//這個是為了一層一層的數(shù)值進行處理
        for (int i = 0; i < sz; i++)
        {
            //那就取出那個節(jié)點進行處理
            TreeNode* node = nodeQueue.front();
            cout << node->val << ", ";
            nodeQueue.pop();
            if (node->left)
            {
                nodeQueue.push(node->left);
            }
            if (node->right)
            {
                nodeQueue.push(node->right);
            }
        }
    }
}


//按照節(jié)點進行序列化成一個字符串
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++實現(xiàn)版本層次遍歷功能的文章就介紹到這了,更多相關c++層次遍歷內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: