07、数据结构与算法实战：基于二叉链表的树结构相等的判断-程序员江小北

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

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

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

Sample Input
abcd00e00f00ig00h00
abcd00e00f00ig00h00
abd00e00cf00g00
abd00e00cf00h00
0

Sample Output
YES
NO

参考程序（C语言实现递归思想）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ROOM sizeof(struct TreeNode)
#define LEN 2000

struct TreeNode
{
   
     
	char data;
	struct TreeNode *LeftChild;
	struct TreeNode *RightChild;
}; 

int i,flag;
char str[LEN];

struct TreeNode* CreateTree(char x)
{
   
     
	if(i<strlen(str))
	{
   
     
		struct TreeNode *p;
		p=(struct TreeNode*)malloc(ROOM);
		if(str[i]!='0')
		{
   
     
			p->data=x;
			p->LeftChild=CreateTree(str[++i]);
			p->RightChild=CreateTree(str[++i]);
		}
		else
		{
   
     
			p=NULL;
		}
		return p;
	}
}

void JudgeTreeStructure(struct TreeNode *t1,struct TreeNode *t2)
{
   
     
	if(t1&&t2)
	{
   
     
		if(t1->data==t2->data)
		{
   
     
			flag*=1;
			JudgeTreeStructure(t1->LeftChild,t2->LeftChild);
			JudgeTreeStructure(t1->RightChild,t2->RightChild);
		}
		else
		{
   
     
			flag*=0;
		}
	}
	else if(!(t1||t2))
	{
   
     
		flag*=1;
	}
	else
	{
   
     
		flag*=0;
	}
}

int main()
{
   
     
	while(1)
	{
   
     
		struct TreeNode *Tree_1,*Tree_2;
		flag=1,i=0;
		gets(str);
		if(str[0]=='0')
		{
   
     
			break;
		}
		else
		{
   
     
			Tree_1=CreateTree(str[0]);
			i=0;
			gets(str);
			Tree_2=CreateTree(str[0]);
			JudgeTreeStructure(Tree_1,Tree_2);
			if(flag)
			{
   
     
				printf("YES\n");
			}
			else
			{
   
     
				printf("NO\n");
			}
		}
	}
	return 0;
}

注意：
程序中用到了计算字符串的长度的函数strlen()，因而要包含头文件<string.h>。