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

忘是亡心i 2022-07-28 09:54 162阅读 0赞

/*求二叉树叶子节点个数 -- 采用递归和非递归方法
    经调试可运行源码及分析如下：
    ***/
    #include <stdlib.h>
    #include <iostream>
    #include <stack>
    
    using std::cout;
    using std::cin;
    using std::endl;
    using std::stack;
    
    /*二叉树结点定义*/
    typedef struct BTreeNode
    {
        char elem;
        struct BTreeNode *pleft;
        struct BTreeNode *pright;
    }BTreeNode;
    
    /*
    求二叉树叶子节点数
    叶子节点：即没有左右子树的结点
    
    递归方式步骤：
    如果给定节点proot为NULL，则是空树，叶子节点为0，返回0；
    如果给定节点proot左右子树均为NULL，则是叶子节点，且叶子节点数为1，返回1；
    如果给定节点proot左右子树不都为NULL，则不是叶子节点，以proot为根节点的子树叶子节点数=proot左子树叶子节点数+proot右子树叶子节点数。
    /*递归实现求叶子节点个数*/
    int get_leaf_number(BTreeNode *proot)
    {
        if(proot == NULL)
            return 0;
        if(proot->pleft == NULL && proot->pright == NULL)
            return 1;
    
        return (get_leaf_number(proot->pleft) + get_leaf_number(proot->pright));
    }
    
    
    /*非递归：本例采用先序遍历计算
    判断当前访问的节点是不是叶子节点，然后对叶子节点求和即可。
     **/
    int preorder_get_leaf_number(BTreeNode* proot)
    {
        if(proot == NULL)
            return 0;
        int num = 0;
        stack <BTreeNode*> st;
        while (proot != NULL || !st.empty())
        {
            while (proot != NULL)
            {
                cout << "节点：" << proot->elem << endl;
                st.push(proot);
                proot = proot->pleft;
            }
    
            if (!st.empty())
            {
                proot = st.top();
                st.pop();
                if(proot->pleft == NULL && proot->pright == NULL)
                    num++;
                proot = proot -> pright;
            }
        }
    
        return num;
    }
    
    /*初始化二叉树根节点*/
    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_leaf_number = 0;
        BTreeNode *bt;
        btree_init(bt);//初始化根节点
        pre_crt_tree(bt);//创建二叉树
        tree_leaf_number = get_leaf_number(bt);//递归
        cout << "二叉树叶子节点个数为:" << tree_leaf_number << endl;
        cout << "非递归先序遍历过程如下：" << endl;
        tree_leaf_number = preorder_get_leaf_number(bt);//非递归
        cout << "二叉树叶子节点个数为:" << tree_leaf_number << endl;
    
        system("pause");
        return 0;
    }
    
    
    /*
    运行结果：
    a b c # # # d e # # f # #
    
    ---以上为输入---
    ---以下为输出---
    
    二叉树叶子节点个数为:3
    非递归遍历过程如下：
    节点：a
    节点：b
    节点：c
    节点：d
    节点：e
    节点：f
    二叉树叶子节点个数为:3
    请按任意键继续. . .
    
    
    本例创建的二叉树形状：
            a
        b       d   
    c         e   f
    参考资料：
    http://blog.csdn.net/beitiandijun/article/details/41940715
    http://yuncode.net/code/c_505ea04f8f6186
    */