二叉树第K层叶子节点个数 -- 采用递归和非递归方法实现

ゝ一纸荒年。 2022-07-28 09:59 145阅读 0赞

/*二叉树第K层叶子节点个数 -- 采用递归和非递归方法
    经调试可运行源码及分析如下：
    ***/
    #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;
    
    /*
    求二叉树第K层叶子节点数
    
    递归方式思想：
    给定节点proot：
    如果proot为空，或者层数k <= 0, 则为空树或者是层数非法，则返回0；
    如果proot不为空，且此时层数k==1时，需要判断是否为叶子节点：
    如果proot左右子树均为空，则proot为第k层叶子节点之一，则返回1；
    如果proot左右子树之一存在，则proot不是叶子节点，则返回0；
    如果proot不为空，且此时层数k > 1，需要返回 k-1层的左子树和右子树结点数。
    */
    /*递归实现求二叉树第k层的节点数*/
    int get_klevel_leaf_number(BTreeNode *proot, int k)
    {
        if (proot == NULL || k <= 0)
            return 0;
        if (proot != NULL && k == 1)
        {
            if(proot->pleft == NULL && proot->pright == NULL)
                return 1;
            else
                return 0;
        }
    
        return (get_klevel_leaf_number(proot->pleft, k-1) + 
                get_klevel_leaf_number(proot->pright, k-1));
    }
    
    /*非递归：按层次遍历
    找到第k层，借助队列实现。
    然后对第k层节点判断是不是叶子结点，若是计数+1
     **/
    /*非递归实现求二叉树第k层的叶子节点数*/
    int get_klevel_leaf_number_bylevelorder(BTreeNode* proot, int k)
    {
        if(proot == NULL || k == 0)
            return 0;
    
        int cur_level_size = 0;//当前层的节点个数
        int cur_level = 0;     //当前层数
    
        queue <BTreeNode*> que;
        que.push(proot);
        while (!que.empty())
        {
            ++cur_level;
            cur_level_size = que.size();
            if(cur_level == k)//当到第k层时
                break;
    
            int temp_count = 0;
            //当前层的所有节点出队，下一层的结点入队
            while (temp_count < cur_level_size) 
            {
                ++temp_count;
                proot = que.front();
                que.pop();
                if (proot->pleft != NULL)
                    que.push(proot->pleft);
                if (proot->pright != NULL)
                    que.push(proot->pright);
            }       
        }
        if(cur_level == k)//求叶子结点
        {
            int node_count = 0;
            int leaf_num = 0;
            while (node_count < cur_level_size)
            {
                ++node_count;
                proot = que.front();
                que.pop();
    
                if (proot->pleft == NULL && proot->pright == NULL)
                    leaf_num++;
            }
            return leaf_num;
        }
        while(!que.empty())
            que.pop();//清空队列
        return 0;
    }
    
    /*初始化二叉树节点*/
    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_level_leaf_num = 0;
        int k;
        BTreeNode *bt;
        btree_init(bt);//初始化根节点
        pre_crt_tree(bt);//创建二叉树
    
        cout << "请输入层数k:"  << endl;
        cin >> k;
        cout << "递归遍历结果：" << endl;
        k_level_leaf_num = get_klevel_leaf_number(bt, k);
        cout << "第" << k << "层的叶子节点个数为：" << k_level_leaf_num << endl;
    
        cout << "非递归遍历结果：" << endl;
        k_level_leaf_num = get_klevel_leaf_number_bylevelorder(bt, k);
        cout << "第" << k << "层的叶子节点个数为：" << k_level_leaf_num << endl;
    
        system("pause");
        return 0;
    }
    
    
    /*
    运行结果：
    a b c # # # d e # # f # g # #
    请输入层数k:
    3
    
    ---以上为输入---
    ---以下为输出---
    
    递归遍历结果：
    第3层的叶子节点个数为：2
    非递归遍历结果：
    第3层的叶子节点个数为：2
    请按任意键继续. . .
    
    本例创建的二叉树形状：
            a
        b       d   
    c         e   f
                 g
    参考资料：
    http://blog.csdn.net/beitiandijun/article/details/41941211
    http://yuncode.net/code/c_505ea04f8f6186
    */