求二叉树深度 -- 递归和非递归实现

曾经终败给现在 2022-07-28 09:46 194阅读 0赞

/*求二叉树深度 -- 采用递归和非递归方法
    **经调试可运行源码及分析如下：
    */
    #include <stdio.h>
    #include <stdlib.h>
    #include <iostream>
    #include <queue>
    
    using namespace std;
    /*二叉树结点定义*/
    typedef struct BTreeNode
    {
        char elem;
        struct BTreeNode *pleft;
        struct BTreeNode *pright;
    }BTreeNode;
    
    /*
    *如果根节点为NULL，则深度为0
    *如果根节点不为NULL，则深度 = 左右子树的深度的最大值+1
    */
    
    /*递归实现求深度*/
    int get_depth(BTreeNode *proot)
    {
        if (proot == NULL)
        {
            return 0;
        }
    
        int left_depth = get_depth(proot->pleft);
        int right_depth = get_depth(proot->pright);
    
        return (((left_depth > right_depth) ? left_depth:right_depth) + 1);
    }
    /**********************************************************/
    /*非递归：借助队列，在进行按层遍历时，记录遍历的层数即可。
     **/
    /*非递归实现求深度*/
    int get_depth2(BTreeNode* proot)
    {
        int depth = 0;
        if (proot == NULL)
        {
            return 0;
        }
    
        queue <BTreeNode *> que;
        que.push(proot);
        while (!que.empty())
        {
            ++depth;
            int cur_level_nodes_count = que.size();//当前层节点数量
            int temp_count = 0;//计数器：当前层次节点个数
            while (temp_count < cur_level_nodes_count)
            {
                ++temp_count;
                proot = que.front();
                que.pop();
                if (proot->pleft != NULL)
                {
                    que.push(proot->pleft);
                }
                if (proot->pright != NULL)
                {
                    que.push(proot->pright);
                }
            }
        }
        return depth;
    }
    /**********************************************************/
    
    /*初始化二叉树根节点*/
    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_depth = 0;
        BTreeNode *bt;
        btree_init(bt);//初始化根节点
        pre_crt_tree(bt);//创建二叉树
        tree_depth = get_depth(bt);//递归
        cout << "二叉树深度为:" << tree_depth << endl;
        tree_depth = get_depth2(bt);//非递归
        cout << "二叉树深度为:" << tree_depth << endl;
    
        system("pause");
        return 0;
    }
    
    
    /*
    运行结果：
    
    a b c # # # d # #
    
    ---以上为输入---
    ---以下为输出---
    
    二叉树深度为:3
    二叉树深度为:3
    请按任意键继续. . .
    
    
    本例创建的二叉树形状：
            a
        b       d   
    c
    
    参考资料：
    http://blog.csdn.net/beitiandijun/article/details/41930583
    http://yuncode.net/code/c_505ea04f8f6186
    */