基于二叉链表的树结构相等的判断

描述

设二叉树中每个结点的元素均为一个字符，按先序遍历的顺序建立二叉链表，按此方法创建两棵二叉树，然后编写递归算法判断这两棵树是否相等。

输入

多组数据，每组数据有两行。每行为一个二叉树的先序序列（序列中元素为‘0’时，表示该结点为空）。当输入只有一个“0”时，输入结束。

输出

每组数据输出一行。若两个二叉树相等输出“YES”，否则输出“NO”。

输入样例 1

abcd00e00f00ig00h00
abcd00e00f00ig00h00
abd00e00cf00g00
abd00e00cf00h00
0

输出样例 1

YES
NO

AC 代码

#include <iostream>
#include <cstring>

using namespace std;

bool flag;                                      // 递归经常需要定义全局变量

typedef struct BiTNode
{
    char data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

void createBiTree(BiTree &t, string s, int &i)  // 递归创建二叉树
{
    if (s[i] == '0')                            // 递归终止条件为叶结点为空
        t = NULL;
    else 
    {
        t = new BiTNode;
        t -> data = s[i];
        createBiTree(t -> lchild, s, ++ i);
        createBiTree(t -> rchild, s, ++ i);
    }
    
}

void compare(BiTree t1, BiTree t2)
{
    if ((!t1 && t2) || (t1 && !t2))
        flag = 0;
    
    if (t1 && t2)
    {
        if (t1 -> data != t2 -> data)
            flag = 0;
        compare(t1 -> lchild, t2 -> lchild);
        compare(t1 -> rchild, t2 -> rchild);
    }
}

int main()
{
    string s1, s2;
    while (cin >> s1, cin >> s2, s1[0] != '0')
    {
        int i = -1, j = -1;                     
        BiTree t1, t2;
        createBiTree(t1, s1, ++ i);             // 传入每一个字符
        createBiTree(t2, s2, ++ j);
        
        flag = 1;
        compare(t1, t2);
        if (flag)
            cout << "YES" << endl;
        else 
            cout << "NO" << endl;
    }
    
    return 0;
}