PIPI OJ 1303: 判断树的子树

2024-04-02 11:08

文章标签 判断子树 oj 1303 pipi

本文主要是介绍PIPI OJ 1303: 判断树的子树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

菜鸟生成记(13)

PIPI OJ 1303: 判断树的子树

思路:大树的每一个结点为根结点形成的一个子树,获取该子树的中序序列；

再获取小树的中序序列;然后让每个子树的序列与之比较;有一次序列比较相同，小树就是大树的子树;否则不是；

#include<bits/stdc++.h>//以大树的每个节点作为根节点的子树与小树比较
using namespace std;
typedef struct st{int data;struct st *l,*r;st(){l=r=0;}
}*link,AK;
int a[1001];//动态存储大树的子树的中序序列
int b[1001];//存储小树的中序序列
int flag=0;//标记
int len2=0;//小树的中序序列长度
void create(link &T)//建树
{int n;cin>>n;if(n==-1)T=NULL;else{T=new AK;T->data=n;create(T->l);create(T->r);}
}
void fun(link T,int &len,int a[])//数组a动态记录大树的子树的中序序列
{if(T){fun(T->l,len,a);a[len++]=T->data;fun(T->r,len,a);}
}
int sx(int a[],int len)//大树的子树的中序序列与小树的中序序列比较
{if(len!=len2)//长度不一样，序列肯定不一样return 0;else{for(int i=0;i<len;i++)if(a[i]!=b[i])return 0;return 1;}
}
void fa(link T)//确定小树是否是大树的子树
{if(T){int len=0;memset(a,0,sizeof(a));fun(T,len,a);//获取一颗子树的中序序列if(sx(a,len)==1)//大树的子树的中序序列与小树的中序序列比较{flag=1;//序列一样，标记return;}fa(T->l);//fa(T->r);//}
}
int main()
{link T1=NULL,T2=NULL;create(T1);//大树 create(T2);//小树 fun(T2,len2,b);//小树序列fa(T1);//大树的子树与小树对比 if(flag==1)cout<<"yes"<<endl;elsecout<<"no"<<endl;return 0;
}