链式的二叉树,注意0 ():
#include<stdio.h> #include<stdlib.h> struct Node{ int v; struct Node * l; struct Node * f; struct Node * r; }; int t,e1,e2,isfind = 0; struct Node * root = NULL; struct Node head = {0,NULL,NULL,NULL}; struct Node * Cset(struct Node * fa){ struct Node * p = (struct Node *)malloc(sizeof(struct Node)); p ->v = 0; p ->f = fa; p ->r = NULL; p ->l = NULL; return p; } struct Node * CreatT(){ int i = 0,cnt = 0,f = 1,val = 0; int flag = 0,k = 0; char ch,lc = '(',c = '('; struct Node * p = &head; head.v = 0; head.f = head.l = head.r = NULL; do { scanf("%c",&ch); if(ch == '(' || ch == ')' || ch == '-' || (ch >= '0' && ch <= '9')){ if(ch == '('){ cnt++; if(flag){ p ->v = val * f; val = 0; f = 1; flag = 0; } if(lc == '('){ p ->l = Cset(p); p = p ->l; k = 0; } else { p ->r = Cset(p); p = p ->r; k = 1; } lc = ch; } else if(ch == ')'){ cnt--; p = p ->f; if(c == '(' && k == 0){ free(p ->l); p ->l = NULL; } if(c == '(' && k == 1){ free(p ->r); p ->r = NULL; } lc = ch; } else if(ch >= '0' && ch <= '9'){ val = val * 10 + (ch - '0'); flag = 1; } else if(ch == '-'){ f = -1; } c = ch; } }while(cnt); return &head; } int dfs(struct Node * p,int path_l){ if(!isfind){ if(p == NULL)return 1; else { path_l += p->v; e1 = dfs(p->l,path_l); e2 = dfs(p->r,path_l); if(e1 && e2 && t == path_l){ isfind = 1; } return 0; } } return 1; } void destoryT(struct Node * p){ if(p == NULL)return; destoryT(p->l); destoryT(p->r); free(p); return; } int main(void){ while(scanf("%d",&t) != EOF){ getchar(); isfind = 0; root = CreatT(); dfs(root->l,0); printf("%s\n",isfind ? "yes" : "no"); destoryT(root->l); } return 0; }
直接递归的方法:
#include<stdio.h> #include<string.h> #define Max 10000 char buffer[Max] = {'\0'}; int p = 0,t,e1,e2,isfind = 0; char si; char readc(){ return buffer[p++]; } int isdig(){ char ch = buffer[p]; if(ch == '-' || (ch >= '0' && ch <= '9'))return 1; else return 0; } int readn(){ int f = 1,val = 0; if(buffer[p] == '-'){ f = -1; p ++; } while(buffer[p] <= '9' && buffer[p] >= '0') val = val * 10 + (buffer[p++] - '0'); val *= f; return val; } void input(){ int cnt = 0; char ch,* ptr = buffer; do { scanf("%c",&ch); if(ch == '(' || ch == ')' || ch == '-' || (ch >= '0' && ch <= '9')){ (*ptr++) = ch; if(ch == '(')cnt++; else if(ch == ')')cnt--; } }while(cnt); } int dfs(int path){ if(!isfind){ si = readc(); if(isdig()){ path += readn(); e1 = dfs(path); e2 = dfs(path); if(e1 && e2 && path == t) isfind = 1; si = readc(); return 0; } else{ si = readc(); return 1; } } return 0; } int main(void){ while(scanf("%d",&t) != EOF){ isfind = p = 0; getchar(); input(); dfs(0); printf("%s\n",isfind ? "yes" : "no"); } return 0; }
poj可以过的二叉堆:
#include<stdio.h> #include<string.h> #define Max 1000000 #define Left(n) (2*(n)) #define Right(n) (2*(n)+1) #define Father(n) (n/2) int node,t,isfind = 0; int e1,e2,Max_lf = 0; int Tree[Max] = {0}; int sign[Max] = {0}; void csigned(int k,int * fl,int * f){ Tree[k] = (*f) * Tree[k]; (*fl) = 0; (*f) = 1; } void slove(){ int cnt = 0,i = 0,f = 1,flag = 0,k = 1; char ch,lc = '('; do { scanf("%c",&ch); if(ch == '(' || ch == ')' || (ch >= '0' && ch <= '9') || ch == '-'){ if(ch == '('){ cnt++; if(!i)continue; if(flag)csigned(k,&flag,&f); if(lc == ')')k = Right(k); else if(lc == '(')k = Left(k); lc = ch; } else if(ch == ')'){ cnt--; if(flag)csigned(k,&flag,&f); k = Father(k); lc = ch; } else if(ch >= '0' && ch <= '9'){ Tree[k] = Tree[k] * 10 + (ch - '0'); sign[k] = 1; i = k; flag = 1; } else if(ch == '-'){ f = - 1; } } }while(cnt); Max_lf = i; } int dfs(int n,int path_l){ if(!isfind){ if(!sign[n])return 1; else { path_l += Tree[n]; e1 = dfs(Left(n),path_l); if(isfind)return 0; e2 = dfs(Right(n),path_l); if(isfind)return 0; if(e1 && e2 && t == path_l){ isfind = 1; } sign[n] = 0; Tree[n] = 0; return 0; } } return 0; } int main(void){ while(scanf("%d",&t) != EOF){ isfind = 0; memset(sign,0,sizeof(int) * (Max_lf + 1)); memset(Tree,0,sizeof(int) * (Max_lf + 1)); getchar(); slove(); dfs(1,0); printf("%s\n",isfind ? "yes" : "no"); } return 0; }