nyoj-1278-Prototypes analyze（二叉排序树模板）

思路：建树之后，判断有多少种不同的树。
判断不同的树，简单的思路是遍历数组，判断数组后面是否存在一样的树
  1 /*
  2     Name:NYOJ-1278-Prototypes analyze
  3     Copyright:
  4     Author:
  5     Date: 2018/4/14 19:19:03
  6     Description:
  7     二叉排序树模板 
  8 */
  9 #include<cstdio>
 10 #include<iostream>
 11 using namespace std;
 12 
 13 /*模板---------------------------------------------------------------*/
 14 typedef int ElemType;//定义ElemType的类型，可自己更改 
 15 template<typename T>
 16 int getArrayLength(T &array) {
 17     return (sizeof(array) / sizeof(array[0]));
 18 }
 19 //设计数据结构，构造二叉树
 20 typedef struct node {
 21     ElemType data;
 22     struct node *lchild, *rchild;
 23 }*BST;
 24 //插入元素
 25 bool insertBST(BST &T, ElemType element) {
 26     if (T==NULL)
 27     {
 28         T = new node;
 29         T->data = element;
 30         T->lchild = T->rchild = NULL;
 31         return true;
 32     }
 33     if (T->data==element)   //元素的值不能和树中已有的值相等
 34     {
 35         return false;
 36     }
 37     if (element<T->data)
 38     {
 39         insertBST(T->lchild,element);
 40     }
 41     else
 42     {
 43         insertBST(T->rchild,element);
 44     }
 45 }
 46 //创建二叉排序树
 47 void createBST(BST &T,ElemType array[],int len){   //Debug模式下，未初始化的栈内存上的指针全部填成0xcccccccc;
 48     T = NULL;
 49     for (int i = 0; i < len; i++)
 50     {
 51         insertBST(T,array[i]);
 52     }
 53 }
 54 //访问，可改为数组保存 
 55 void visit(ElemType elem) {
 56     cout << elem << "  ";
 57 }
 58 //中序遍历
 59 void preOrderTraverse(BST &T) {
 60     if (T!=NULL)
 61     {
 62         preOrderTraverse(T->lchild);
 63         visit(T->data);
 64         preOrderTraverse(T->rchild);
 65     }
 66 }
 67 //释放内存
 68 void relese(BST &T) {
 69     if (T==NULL)
 70     {
 71         return;
 72     }
 73     relese(T->lchild);
 74     relese(T->rchild);
 75     delete T;
 76 }
 77 //删除某个结点
 78 bool deleteNode(BST &T, ElemType element) {
 79     if (T==NULL)
 80     {
 81         return false;
 82     }
 83     BST p,q,s,parent;
 84     p = T;
 85     while (p!=NULL)
 86     {
 87         if (p->data == element)  break;
 88         parent = p;
 89         p = (p->data < element) ? p->rchild: p->lchild;
 90     }
 91     if (p==NULL)
 92     {
 93 //        cout << "该二叉排序树中无您要删除的值！"<<endl;
 94         return false;
 95     }
 96     if ((p->lchild==NULL)&&(p->rchild==NULL))
 97     {
 98         //重置其父亲结点的左右子孩子
 99         if (parent->lchild != NULL&&parent->lchild->data==element)
100         {
101             parent->lchild = NULL;
102         }
103         if (parent->rchild!=NULL&&parent->rchild->data==element)
104         {
105             parent->rchild = NULL;
106         }
107         return true;
108     }
109     else if (p->lchild!=NULL&&p->rchild==NULL)
110     {
111         //要让p的左孩子接上
112         s=p->lchild;
113         p ->data= s->data;
114         p->lchild = s->lchild;
115         delete s;
116         return true;
117     }
118     else if (p->lchild==NULL&&p->rchild!=NULL)
119     {
120         //要让p的右孩子接上
121         s = p->rchild;
122         p->data = s->data;
123         p->rchild = s->rchild;
124         delete s;
125         return true;
126     }
127     else
128     {
129         q = p;
130         s = p->lchild;
131         while (s->rchild!=NULL)
132         {
133             q = s;
134             s = s->rchild;
135         }
136         p->data = s->data;
137         if (q!=p)
138         {
139             q->rchild = s->lchild;
140         }
141         else
142         {
143             q->lchild = s->lchild;
144         }
145         delete s;
146         return true;
147     }
148 }
149 /*模板-------------------------------------------------------------结束*/
150 
151 int flag;
152 void judge(BST T1,BST T2)  //判断形状；
153 {
154     if(T1==NULL&&T2==NULL)
155         return;
156     else if(T1&&T2)
157     {
158         judge(T1->lchild,T2->lchild);
159         judge(T1->rchild,T2->rchild);
160     }
161     else
162         flag=0;
163 }
164 int main()
165 {
166     int t,n,k,x;
167     BST tree[55];
168 
169     scanf("%d",&t);
170     while(t--)
171     {
172         scanf("%d%d",&n,&k);
173         for(int i=0; i<n; i++)  
174         {
175             BST T=NULL; 
176             for(int j=0; j<k; j++)  //建树；
177             {
178                 scanf("%d",&x);
179                 insertBST(T,x);
180             }
181             tree[i]=T;
182         }
183         //找形状种类数；
184         int ans=0;
185         for(int i=0; i<n; i++)
186         {
187             int flog=1;
188             for(int j=i+1; j<n; j++)
189             {
190                 flag=1;
191                 judge(tree[i],tree[j]);
192                 if(flag)
193                 {
194                     flog=0;
195                     break;
196                 }
197             }
198             if(flog)
199                 ++ans;
200         }
201         printf("%d
",ans);
202     }
203     return 0;
204 }