二叉树层次遍历(借助队列实现)

╰半夏微凉° 2022-07-28 09:52 147阅读 0赞

/*按层次遍历二叉树
     *经调试可运行源码及分析如下：
    ***/
    #include <stdlib.h>
    #include <iostream>
    #include <queue>
    
    using std::cout;
    using std::cin;
    using std::endl;
    using std::queue;
    
    /*二叉树结点定义*/
    typedef struct BTreeNode
    {
        char elem;
        struct BTreeNode *pleft;
        struct BTreeNode *pright;
    }BTreeNode;
    
    /*
    按层次遍历二叉树步骤： 
    第一步：借助队列，首先将根节点proot入队；
    第二步：当队列不空时，获得队首元素并出队，赋给proot，执行第三步；
    第三步：如果proot左节点存在，则入队；如果proot右节点存在，则入队；执行第二步。
    */
    
    /*按层次遍历二叉树*/
    void level_traverse(BTreeNode* proot)
    {
        if (proot == NULL)
            return;
    
        queue <BTreeNode*> que;
        que.push(proot);
        while (!que.empty())
        {
            proot = que.front();
            que.pop();
            cout << "遍历节点：" << proot->elem << endl;
            if (proot->pleft != NULL)
            {
                que.push(proot->pleft);//左孩子入队
            }
            if (proot->pright != NULL)
            {
                que.push(proot->pright);//右孩子入队
            }
        }
    }
    
    /*初始化二叉树根节点*/
    BTreeNode* btree_init(BTreeNode* &bt)
    {
        bt = NULL;
        return bt;
    }
    
    /*先序创建二叉树*/
    void pre_crt_tree(BTreeNode* &bt)
    {
        char ch;
        cin >> ch;
        if (ch == '#')
        {
            bt = NULL;
        }
        else
        {
            bt = new BTreeNode;
            bt->elem = ch;
            pre_crt_tree(bt->pleft);
            pre_crt_tree(bt->pright);
        }
    }
    
    int main()
    {
        int tree_node_number = 0;
        BTreeNode *bt;
        btree_init(bt);//初始化根节点
        pre_crt_tree(bt);//创建二叉树
        level_traverse(bt);//递归
    
    
        system("pause");
        return 0;
    }
    
    /*
    运行结果：
    a b c # # # d e # # #
    
    ---以上为输入---
    ---以下为输出---
    
    遍历节点：a
    遍历节点：b
    遍历节点：d
    遍历节点：c
    遍历节点：e
    请按任意键继续. . .
    
    
    本例创建的二叉树形状：
            a
        b       d   
    c        e
    参考资料：
    http://blog.csdn.net/beitiandijun/article/details/41940417
    http://yuncode.net/code/c_505ea04f8f6186
    */