二叉树第K层的第M个节点 -- 采用非递归层次遍历实现

迷南。 2022-07-28 10:57 121阅读 0赞

/*二叉树第K层的第M个节点 -- 采用非递归层次遍历实现
    经调试可运行源码及分析如下：
    ***/
    #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入队：
    第一步：如果队列未空，获取当前队列的长度，即当前层的节点总数；
    第二步：记录当前遍历的层数，判断是否超出指定层数，如果超出则退出；
            如果小于指定层数，则对当前层的所有左右节点入队操作；如果等于指定 层数，则进行第三步；
    第三步：获取当前队列中节点总数，如果当前节点总数小于指定节点数，则退出；
            如果节点总数大于指定节点数，则进行第四步；
    第四步：遍历当前层节点，如果节点数等于指定节点数，则放回此节点。
    第三步：循环结束后，如果没有符合条件的节点就返回NULL。
    */
    
    /*非递归求二叉树第K层的第M个节点*/
    BTreeNode* get_klevel_mth_node(BTreeNode* proot, int k, int m)
    {
        if (proot == NULL || k <= 0 || m <= 0)
            return NULL;
    
        queue <BTreeNode* > que;
        que.push(proot);
    
        int cur_level_size = 0;
        int cur_level = 0;
        int cur_level_node_count = 0;
    
        while (!que.empty())
        {
            ++cur_level;
            if (cur_level > k)
                break;
    
    
            cur_level_node_count = 0;
            cur_level_size = que.size();
    
            while (cur_level_node_count < cur_level_size)
            {
                ++cur_level_node_count;
                proot = que.front();
                que.pop();
                /*when k level and mth, break*/
                if (cur_level == k && cur_level_node_count == m)
                    break;
    
                if(proot->pleft != NULL)
                    que.push(proot->pleft);
                if(proot->pright != NULL)
                    que.push(proot->pright);
            }
            /*第k层时 break;*/
            if (cur_level == k)
                    break;
        }
    
        while (!que.empty())
        {
            que.pop();
        }
        if (cur_level == k && cur_level_node_count == m)
        {
            cout << "节点elem值为:" << proot->elem << endl;
            return proot;
        }
        return NULL;
    }
    
    /*初始化二叉树节点*/
    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 k, m;
        BTreeNode *bt;
        btree_init(bt);//初始化根节点
        pre_crt_tree(bt);//创建二叉树
    
        cout << "请输入层数k:"  << endl;
        cin >> k;
        cout << "请输入计数m:"  << endl;
        cin >> m;
        get_klevel_mth_node(bt, k, m);
    
        system("pause");
        return 0;
    }
    
    
    /*
    运行结果：
    a b c # # # d e # # f # g # #
    请输入层数k:
    3
    请输入计数m:
    2
    ---以上为输入---
    ---以下为输出---
    节点elem值为:e
    请按任意键继续. . .
    
    本例创建的二叉树形状：
            a
        b       d   
    c         e   f
                 g
    
    
    参考资料：
    http://blog.csdn.net/beitiandijun/article/details/41942429
    http://yuncode.net/code/c_505ea04f8f6186
    */