数据结构练习--判断两个序列是否属于同一棵树

蔚落 2023-10-01 17:02 10阅读 0赞

*  判断两个序列是不是属于相同的树
 *  首先输入序列的长度和需要比较的序列个数，然后输入序列，如果属于相同的树，则输出yes，否则输出no

//判断一个序列和后面的几个序列是不是属于相同的树
    //输入一个序列的长度和要比较的序列个数。然后建树，再用后面的序列和前面的树进行比较
    #include <stdio.h>
    #include <stdlib.h>
    typedef struct TreeNode* Tree;
    struct TreeNode
    {
        
    	int v;
    	Tree Left, Right;
    	int flag;		//flag为0表示未访问过此节点；1表示访问过此节点
    };
    Tree newNode(int V)
    {
        
    	Tree T = (Tree)malloc(sizeof(struct TreeNode));
    	T->v = V;
    	T->Left = T->Right = NULL;
    	T->flag = 0;
    	return T;
    }
    Tree insert(Tree T, int V)
    {
        
    	if (!T) T = newNode(V);
    	else
    	{
        
    		if (V > T->v)
    			T->Right = insert(T->Right, V);
    		else
    			T->Left = insert(T->Left, V);
    	}
    	return T;
    }
    Tree makeTree(int N)
    {
        
    	Tree T;
    	int i, V;
    	scanf("%d", &V);
    	T = newNode(V);
    	for (i = 1; i < N; i++)
    	{
        
    		scanf("%d", &V);
    		T = insert(T, V);
    	}
    	return T;
    }
    int check(Tree T, int V)
    {
        
    	if (T->flag)
    	{
        
    		if (V < T->v) return check(T->Left, V);
    		else if (V > T->v) return check(T->Right, V);
    		else return 0;
    	}
    	else
    	{
        
    		if (V == T->v) {
         T->flag = 1; return 1; }
    		else return 0;
    	}
    }
    int judge(Tree T, int N)
    {
        
    	int i, V, flag = 0;
    	scanf("%d", &V);
    	if (V != T->v) flag = 0;
    	else T->flag = 1;
    	for (i = 1; i < N; i++)
    	{
        
    		scanf("%d", &V);
    		if ((!flag) && (!check(T, V))) flag = 1;
    	}
    	if (flag) return 0;
    	else return 1;
    }
    void resetT(Tree T)
    {
        
    	if (T->Left) resetT(T->Left);
    	if (T->Right) resetT(T->Right);
    	T->flag = 0;
    }
    void freeTree(Tree T)
    {
        
    	if (T->Left) freeTree(T->Left);
    	if (T->Right) freeTree(T->Right);
    	free(T);
    }
    int main()
    {
        
    	int N, L, i;
    	Tree T;
    	scanf("%d", &N);
    	while (N)
    	{
        
    		scanf("%d", &L);
    		T = makeTree(N);
    		for (i = 0; i < L; i++)
    		{
        
    			if (judge(T, N)) printf("Yes\n");
    			else printf("No\n");
    			resetT(T);
    		}
    		freeTree(T);
    		scanf("%d", &N);
    	}
    	return 0;
    }