判断两个二叉树是否相等(仅结构) -- 递归和非递归实现

╰+攻爆jí腚メ 2022-07-28 11:47 107阅读 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;
    
    /*初始化二叉树节点*/
    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);
        }
    }
    
    /*
    递归方式:
    如果两个二叉树proot都为空树，则自然相同，返回true；
    如果两个二叉树proot一个为空树，另一个不为空树，则不相同，返回false；
    如果两个二叉树都不为空树，则需要分别比较左右子树后，根据比较结果共同判定，只要有一个为false，则返回false。
    */
    /*递归判断两个二叉树是否相等（仅仅结构）*/
    bool bitree_compare(BTreeNode* proot1, BTreeNode* proot2)
    {
        if (proot1 == NULL && proot2 == NULL)//都为空
            return true;
    
        if((proot1 != NULL && proot2 == NULL) ||
            (proot1 == NULL && proot2 != NULL))//一个空，一个非空
            return false;
    
        bool left_compare = bitree_compare(proot1->pleft, proot2->pleft);
        bool right_compare = bitree_compare(proot1->pright, proot2->pright);
    
        return (left_compare && right_compare);
    }
    
    /*
    非递归方式 
    借助队列实现
    实现算法：
    首先将给定根节点proot1和proot2都入队
    第一步：当两个队列未空时，分别获取两个树的当前层次中节点总数（即当前队列中节点个数），
           先比较节点个数是否相同，如果不相同，则两个树自然不同；
           如果节点个数相同，需要出队进行比较。如果有一个队列未空，则退出比较。
    第二步：如果有一个队列未空，则清空队列并返回不同。
    */
    /*非递归方式判断两个二叉树是否相等（仅仅结构）*/
    bool bitree_compare_leveltraverse(BTreeNode* proot1, BTreeNode* proot2)
    {
        if (proot1 == NULL && proot2 == NULL)//都为空
            return true;
    
        queue <BTreeNode*> que1;
        queue <BTreeNode*> que2;
        que1.push(proot1);
        que2.push(proot2);
    
        int cur_level_nodes_num1 = 0;
        int cur_level_nodes_num2 = 0;
        bool flag = true;
        while (!que1.empty() && !que2.empty())
        {
            cur_level_nodes_num1 = que1.size();
            cur_level_nodes_num2 = que2.size();
            //节点数目不一样时flag设为false，退出循环
            if (cur_level_nodes_num1 != cur_level_nodes_num2)
            {
                flag = false;
                break;
            }
    
            int cur_level_node_count1 = 0;
            int cur_level_node_count2 = 0;
            while (cur_level_node_count1 < cur_level_nodes_num1 && 
                    cur_level_node_count2 < cur_level_nodes_num2)
            {
                ++cur_level_node_count1;
                ++cur_level_node_count2;
                proot1 = que1.front();
                que1.pop();
                proot2 = que2.front();
                que2.pop();
    
                //判断左右孩子是否相同，不同肯定结构不相同，提前break
                if( proot1->pleft == NULL && proot2->pleft != NULL   ||
                    proot1->pleft != NULL && proot2->pleft == NULL   ||
                    proot1->pright == NULL && proot2->pright != NULL ||
                    proot1->pright != NULL && proot2->pright == NULL
                  )
                {
                    flag = false;
                    break;
                }
                /*下一层的节点入队*/
                if(proot1->pleft)
                    que1.push(proot1->pleft);
                if(proot1->pright)
                    que1.push(proot1->pright);
                if(proot2->pleft)
                    que2.push(proot2->pleft);
                if(proot2->pright)
                    que2.push(proot2->pright);
            }
            if(flag == false)
                break;
        }
    
        if(flag == false)
        {
            while(!que1.empty())
                que1.pop();
            while(!que2.empty())
                que2.pop();
    
            cout << "非递归：reslut is false." << endl;
            return false;
        }else
        {
            cout << "非递归：reslut is true." << endl;
            return true;
        }
    
        return true;
    }
    
    int main()
    {
        BTreeNode *bt1;
        BTreeNode* bt2;
        bool flag;
        btree_init(bt1);//初始化根节点
        btree_init(bt2);//初始化根节点
    
        cout << "creat 1th tree:" << endl;
        pre_crt_tree(bt1);//创建二叉树
        cout << "creat 2th tree:" << endl;
        pre_crt_tree(bt2);//创建二叉树
    
        /*递归测试*/
        flag = bitree_compare(bt1, bt2);
        if(flag == true)
            cout<< "递归：result is true." << endl;
        else
            cout << "递归：result is false." << endl;
    
        /*非递归测试*/
        bitree_compare_leveltraverse(bt1, bt2);
    
        system("pause");
        return 0;
    }

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

/*
    测试结果如下：
    creat 1th tree:
    a b c # # # d e # # f # g # #
    creat 2th tree:
    a b c # # # d e # # f # g # #
    递归：result is true.
    非递归：reslut is true.
    请按任意键继续. . .
    
    ------------------分界线-----------------------
    creat 1th tree:
    a b c # # # d e # # f # g # #
    creat 2th tree:
    a b c # # # d e # # #
    递归：result is false.
    非递归：reslut is false.
    请按任意键继续. . .
    
    本例创建的二叉树形状：
    a b c # # # d e # # f # g # # 如下：
            a
        b       d   
    c         e   f
                 g
    
    a b c # # # d e # # #  如下：
            a
        b       d
    c         e
    
    参考资料：
    http://blog.csdn.net/beitiandijun/article/details/41957181
    http://yuncode.net/code/c_505ea04f8f6186
    */