1159.cpp

来自「哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码」· C++ 代码 · 共 90 行

/*  This Code is Submitted by wywcgs for Problem 1159 on 2005-11-10 at 21:51:36 */ 
#include <cstdio>

class BSTree {
private:
	BSTree *left;
	BSTree *right;
	int v;
public:
	BSTree(int n) {
		v = n;
	}
	void build();
	bool travel(int, int);
};
void BSTree::build() {
	int n;
	while(getchar() != '(')
		;
	if(scanf("%d", &n) == 0) {
		left = NULL;
	} else {
		left = new BSTree(n);
		left->build();
	}
	while(getchar() != ')')
		;
	while(getchar() != '(')
		;
	if(scanf("%d", &n) == 0) {
		right = NULL;
	} else {
		right = new BSTree(n);
		right->build();
	}
	while(getchar() != ')')
		;
}
bool BSTree::travel(int n, const int tar) {
	bool leaf = true;
	bool can = false;
	n += v;
	if(left != NULL) {
		if(left->travel(n, tar)) {
			can = true;
		}
		delete left;
		leaf = false;
	}
	if(right != NULL) {
		if(right->travel(n, tar)) {
			can = true;
		}
		delete right;
		leaf = false;
	}
	if(leaf && n == tar) {
		return true;
	} else {
		return can;
	}
}

int main()
{
	BSTree *root;
	int m, n;
	
	while(scanf("%d", &n) == 1) {
		root = NULL;
		while(getchar() != '(')
			;
		if(scanf("%d", &m) == 1) {
			root = new BSTree(m);
			root->build();
			if(root->travel(0, n)) {
				printf("yes\n");
			} else {
				printf("no\n");
			}
		} else {
			printf("no\n");
		}
		while(getchar() != ')')
			;
	}
	
	return 0;
}