binary tree is_subtree
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
// clang-format off
#define struct(x) typedef struct x x; struct x
// clang-format on
struct(node) {
char c;
node *l, *r;
};
#define Z NULL
node *C(char c, node *l, node *r) {
node *n = calloc(1, sizeof(node));
*n = (node){ c, l, r };
return n;
}
void D(node *n) {
if (n) D(n->l), D(n->r), free(n);
}
// a == b ?
int g(node *a, node *b) {
if (a == Z && b == Z) return 1;
if (a == Z || b == Z) return 0;
return a->c == b->c && g(a->l, b->l) && g(a->r, b->r);
}
// a 包含 b ?
int f(node *a, node *b) {
return g(a, b) || (a && (f(a->l, b) || f(a->r, b)));
}
// 简单递归解析
node *S_(const char *s, int *i) {
#define peek s[*i]
#define step (*i += 1)
#define match(c) (peek == c)
char c = peek;
step; // skip "A", maybe ',' '(' ')'
if (match(',') || match(')')) return C(c, Z, Z);
step; // skip "(", maybe ',' 'B'
node *l = match(',') ? Z : S_(s, i);
step; // skip ",", maybe ')', 'C'
node *r = match(')') ? Z : S_(s, i);
step; // skip ")"
return C(c, l, r);
#undef match
#undef step
#undef peek
}
// "A(B,C)" -> C('A', C('B', Z, Z), C('C', Z, Z))
node *S(const char *s) {
int i = 0;
return S_(s, &i);
}
int main(void) {
node *a = S("A(B(D,E),C(F,G(,I)))");
node *b = S("C(F,G(,I)))");
printf("%d\n", f(a, b));
D(b), D(a);
return 0;
}
C
INFO