求二叉树镜像 -- 采用递归和非递归方法

左手的ㄟ右手 2022-07-28 11:55 205阅读 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为NULL，则为空树，返回；
    如果proot不为NULL，交换proot左右结点，然后分别求左右子树的镜像；
    */
    /*递归求二叉树镜像*/
    void get_bitree_mirror(BTreeNode* proot)
    {
        if (proot == NULL)
            return ;
    
        BTreeNode* temp_node = proot->pleft;
        proot->pleft = proot->pright;
        proot->pright = temp_node;
    
        get_bitree_mirror(proot->pleft);
        get_bitree_mirror(proot->pright);
    
        return ;
    }
    
    /*
    非递归方式步骤如下：
    借助队列
    首先，将根节点proot入队；
    第一步：当队列非空时，获取当前层次的节点总数，即当前队列的长度；执行第二步；
    第二步：按照当前层的节点总数，出队进行遍历节点，在遍历时，
           交换左右节点，如果左右节点存在，则入队；
           当遍历完当前层所有节点时，遍历下一层，执行第一步。
    */
    void get_bitree_mirror_leveltraverse(BTreeNode* proot)
    {
        if(proot == NULL)
            return ;
    
        queue <BTreeNode*> que;
        que.push(proot);
        int level_nodes_number = 0;
        while (!que.empty())//层次遍历
        {
            level_nodes_number = que.size();
    
            int level_count = 0;
            while (level_count < level_nodes_number)
            {
                ++level_count;
                proot = que.front();
                que.pop();
                //交换左右子节点
                BTreeNode* temp_node = proot->pleft;
                proot->pleft = proot->pright;
                proot->pright = temp_node;
    
                if(proot->pleft != NULL)
                    que.push(proot->pleft);
                if(proot->pright != NULL)
                    que.push(proot->pright);
            }
        }
    
        return ;
    }
    
    
    /*初始化二叉树根节点*/
    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);
        }
    }
    /*先序遍历*/
    void pre_order_traverse(BTreeNode* proot)
    {
        if(proot == NULL)
            return;
    
        cout<< proot->elem << " ";
        pre_order_traverse(proot->pleft);
        pre_order_traverse(proot->pright);
    
        return;
    }
    
    int main()
    {
        int tree_node_number = 0;
        BTreeNode *bt;
        btree_init(bt);//初始化根节点
        pre_crt_tree(bt);//创建二叉树
    
        cout << "先序遍历输出如下：" << endl;
    
        cout << "调用镜像函数前："  << endl;
        pre_order_traverse(bt);
        cout << endl;
    
        get_bitree_mirror(bt);
        cout << "递归调用镜像函数后："  << endl;
        pre_order_traverse(bt);
        cout << endl;
    
        cout << "非递归调用镜像函数后："  << endl;
        get_bitree_mirror_leveltraverse(bt);
        pre_order_traverse(bt);
        cout << endl;
    
        system("pause");
        return 0;
    }

--------------------

/*
    运行结果：
    a b c # # # d e # # #
    ------以上为输入-----------
    ------以下为输出-----------
    先序遍历输出如下：
    调用镜像函数前：
    a b c d e
    递归调用镜像函数后：
    a d e b c
    非递归调用镜像函数后：
    a b c d e
    请按任意键继续. . .
    
    ---------------------------------
    本例创建的二叉树形状：
            a
        b       d   
    c         e
    
    调用递归求二叉树镜像形状：
         a
    d        b
        e        c
    再次调用非递归求二叉树镜像形状（即镜像的镜像）:
            a
        b       d   
    c         e
    
    参考资料：
    http://blog.csdn.net/beitiandijun/article/details/41958885
    http://yuncode.net/code/c_505ea04f8f6186
    */