迹忆客 专注技术分享

二叉树的逐层遍历称为广度优先遍历。 本教程将教您如何使用 C++ 逐级打印二叉树中的数据，并让您熟悉执行此任务的不同方法。

使用队列是在二叉树中逐级打印数据的正确方法，就像堆栈用于深度优先遍历一样。 但是，可以通过三种不同的方法来实现此目标：使用队列（或链表节点）或使用哈希技术编写自己的算法。

用C++编写一个使用队列逐级打印二叉树数据的算法

在C++中，可以通过包含#include来使用队列的功能来编写一个算法，按排序顺序逐级打印二叉树中的数据。 由于队列遵循 FIFO（先进先出原则），因此您应该初始化一个队列并将根推送到该队列。

编写逻辑算法并将其应用于输入二叉树，并且可以使用空节点（通过换行符分隔节点）。 请记住，与空节点的交互意味着当前级别上没有保留任何未访问的节点，并且您可以打印换行符。

在每个二叉树级别的末尾，应该有一个空节点代表其末尾。 初始化一个队列来存储类型节点的数据，将root压入其中，最后将空节点压入队列，就可以向某一层插入空节点。

#include <iostream>
#include <queue>

using namespace std;

class binT_node
{
    public :

    int nodeData;

    // declare left and right nodes of the binary tree
    binT_node* left;
    binT_node* right;

    binT_node(int data, binT_node* lef, binT_node* rig)
    {
        nodeData = data;
        left = lef;
        right = rig;
    }
};

void print_dataT(binT_node* root)
{
    queue<binT_node*> que;
    que.push(root);

    while(true)
    {
        int orderLength = que.size();

        if(orderLength == 0)
        {
            break;
        }

        int i = 0;

        while(i<orderLength)
        {
            binT_node* nod = que.front();
            cout << (nod -> nodeData) << " ";

            if (nod -> left != NULL)
            {
                que.push (nod -> left);
            }

            if (nod -> right != NULL)
            {
                que.push (nod -> right);
            }

        que.pop();
        i++;
        }

    cout<<endl;
    }
}

int main()
{
    binT_node* rootNode;
    rootNode = new binT_node(1, NULL, NULL);
    rootNode -> left = new binT_node(2, NULL, NULL);
    rootNode -> right = new binT_node(3,NULL,NULL);
    rootNode -> left -> left = new binT_node(4,NULL,NULL);
    rootNode -> left -> right = new binT_node(5,NULL,NULL);
    rootNode -> right -> left = new binT_node(6,NULL,NULL);
    rootNode -> right -> right = new binT_node(7,NULL,NULL);
    print_dataT(rootNode);

    return 0;
}

输出:

1
2 3
4 5 6 7

可以在一次迭代中打印同一级别的节点，而不是在每次迭代中打印一个节点，这是在 C++ 中编写类似算法的另一种众所周知的方法。

这种方法与第一种方法有点相似，包括初始化队列并将根节点和空节点推送到队列中。

此外，如果 temp 不为 null，则打印节点 temp 的值，如果不为 null，则将 temp.left 推入队列，如果不为 null，则将 temp.right 推入队列，重复这些步骤，直到队列为空。

C++中使用链表节点逐级打印二叉树中的数据

访问节点以将其子节点放入 FIFO 队列是一种标准方法，因为您还可以将队列实现为链表。 但是，可以使用 C++ 中的函数打印二叉树的当前级别。

首先，通过创建链表节点的ArrayList，使用队列（BFS）对二叉树进行层序遍历。 变量可以存储队列大小，对于检索和操作每个二叉树级别的所有节点都很有价值。

现在，当存储队列大小的变量大于零时，访问该变量并通过将子节点添加到队列来检索、打印或操作所有节点。

这种递归解决方案功能齐全，但不如队列或散列技术那么有效。

#include <iostream>

using namespace std;

class listNode {
    public:
    int data;
    listNode *left, *right;
};

void print_data(listNode* root_node, int level_order);
int lev_height(listNode* node);
listNode* updatedNode(int data);

void printData_LevelOrder(listNode* root_node)
{
    int heig = lev_height(root_node);
    int init;
    for (init = 1; init <= heig; init++)
        print_data(root_node, init);
}

void print_data(listNode* root_node, int level_order)
{
    // in case of a `null` or empty root
    if (root_node == NULL)
        return;

    // in case if root represents `1`
    if (level_order == 1)
        cout << root_node->data << " ";

    // in case the root is greater than `1`
    else if (level_order > 1) {
        print_data(root_node->left, level_order - 1);
        print_data(root_node->right, level_order - 1);
    }
}

int lev_height(listNode* node_linkedlist)
{
    // in case of empty or `NULL`
    if (node_linkedlist == NULL)
        return 0;
    else {
        int level_leftHeight = lev_height(node_linkedlist -> left);
        int level_rightHeight = lev_height(node_linkedlist -> right);

        // in case the left node is greater than the right node
        if (level_leftHeight > level_rightHeight) {
            return (level_leftHeight + 1);
        }

        // in case the right node is greater than the left node
        else {
            return (level_rightHeight + 1);
        }
    }
}

listNode* updatedNode(int _listdata)
{
    listNode* list_node = new listNode();
    list_node -> data = _listdata;
    list_node -> left = NULL;
    list_node -> right = NULL;

    return (list_node);
}

int main()
{
    listNode* linkedlistNode = updatedNode(1);
    linkedlistNode -> left = updatedNode(2);
    linkedlistNode -> right = updatedNode(3);
    linkedlistNode -> left -> left = updatedNode(4);
    linkedlistNode -> left -> right = updatedNode(5);

    cout << "Level by Level Data Insertion to a Binary Tree is Complete! \n";
    printData_LevelOrder(linkedlistNode);

    return 0;
}

输出:

Level by Level Data Insertion to a Binary Tree is Complete!
1 2 3 4 5

printLevelOrder 和 printCurrentLevel 是该方法（使用链表打印二叉树中的数据）的子函数，它们分别打印给定级别的所有节点或打印二叉树的级别顺序遍历。

此外，printLevelOrder 子函数可以利用 printCurrentLevel 函数从根开始一一打印二叉树上各级的节点。

呼吸优先搜索（BFS）的时间复杂度为 O(n^2)，其中 n 表示二叉树节点的最大数量，O(h) 是 C++ 程序所需的辅助空间，其中 h 表示 二叉树的完整高度。

您将在本教程中找到的每种算法都可以处理每种类型的二叉树，包括： 完整的、完美的、完整的、退化的或病态的、倾斜的和平衡的二叉树。

C++中利用哈希技术逐级打印二叉树中的数据

作为散列技术的一部分，散列表能够在二叉树中逐级打印数据，并且已被证明是非常有用的数据结构，平均散列表的查找时间为 O(1)。

它可以非常有效地解决与算法和二进制数据结构相关的多个问题，以降低时间复杂度。

Hashing包括multimap，它允许将单个键映射到多个值，并使用它来存储二叉树节点及其级别。

散列技术使用二叉树的层数（存储在变量中）作为键，并从父节点或二叉树的第一层开始打印每个层的所有相应节点。

#include <iostream>

// associative container that contains key-value pairs
// search, insert and remove elements in average constant-time complexity
#include <unordered_map>

#include <vector> // initialize the vector contents

using namespace std;

// data structure creation | fulfill the purpose of storing data in a binary table
struct _hashnode
{
    int key;
    _hashnode *left, *right;

    // `key` -> `_nodekey` will contain all the binary tree info to arrange the nodes
    _hashnode(int _nodekey)
    {
        this -> key = _nodekey;
        this -> left = this -> right = nullptr;
    }
};


// enable nodes storage in a map (to traverse the tree in a pre_order fashion) corresponding to the node's level
void hash_preorder(_hashnode* hash_root, int level, auto &map)
{
    // initially: empty binary table
    if (hash_root == nullptr) {
        return;
    }

    // current node and its level insertion into the map
    map[level].push_back(hash_root -> key);

    hash_preorder(hash_root -> left, level + 1, map);
    hash_preorder(hash_root -> right, level + 1, map);
}

// recursive function | fulfill the purpose of printing binary tree's level order traversal
void traversal_throughHash(_hashnode* hash_root)
{
    // creation of a `null` or an empty map | to store nodes between the given levels of a binary tree
    unordered_map<int, vector<int>> map;

    /* level-wise insertion of nodes to the map after the tree traversal */
    hash_preorder(hash_root, 1, map);

    for (int init = 1; map[init].size() > 0; init++)
    {
        cout << "[Binary Tree] Level " << init << ":- ";
        for (int juan: map[init]) {
            cout << juan << " ";
        }
        cout << endl;
    }
}

int main()
{
    _hashnode* hash_Root = new _hashnode(15);
    hash_Root -> left = new _hashnode(10);
    hash_Root -> right = new _hashnode(20);
    hash_Root -> left -> left = new _hashnode(8);
    hash_Root -> left -> right = new _hashnode(12);
    hash_Root -> right -> left = new _hashnode(16);
    hash_Root -> right -> right = new _hashnode(25);
    hash_Root -> right -> right -> right = new _hashnode(30);

    traversal_throughHash(hash_Root);

    return 0;
}

输出:

[Binary Tree] Level 1:- 15
[Binary Tree] Level 2:- 10 20
[Binary Tree] Level 3:- 8 12 16 25
[Binary Tree] Level 4:- 30

通常，二叉树作为一种数据结构，其中最顶层的节点是父节点或根节点，每个父节点代表一对子节点。

二叉树的遍历有四种常见的方式，逐级顺序遍历是效率最高的一种。

事实上，任何基于比较排序的算法都无法比 n log n 性能更好。 二元 tee 的每个节点代表其子节点 (ai ≤ aj) 之间的比较，并且它们代表 n! 之一。

二叉树包含 n = (2^h) - 1 个节点，其中 h 表示二叉树的高度，每个非叶节点都有左右子节点。

对于具有 n! 的树，您可以通过计算 h = [log(n!)] 来确定二叉树的高度 叶节点和 h = log(n + 1) 高度。