c 中逐级打印二叉树中的数据-ag捕鱼王app官网

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

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

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

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

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

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

#include 
#include 
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 que;
    que.push(root);
    while(true)
    {
        int orderlength = que.size();
        if(orderlength == 0)
        {
            break;
        }
        int i = 0;
        while(ifront();
            cout << (nod -> nodedata) << " ";
            if (nod -> left != null)
            {
                que.push (nod -> left);
            }
            if (nod -> right != null)
            {
                que.push (nod -> right);
            }
        que.pop();
        i  ;
        }
    cout<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）对二叉树进行层序遍历。 变量可以存储队列大小，对于检索和操作每个二叉树级别的所有节点都很有价值。

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

这种递归ag捕鱼王app官网的解决方案功能齐全，但不如队列或散列技术那么有效。

#include 
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 
// associative container that contains key-value pairs
// search, insert and remove elements in average constant-time complexity
#include 
#include  // 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) 高度。