1612.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1612 on 2006-03-03 at 13:40:58 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

class BSTree {
public:
	int w;
	BSTree *left, *right;
	BSTree(int wei) : w(wei), left(NULL), right(NULL) {}
	~BSTree();
	void insert(int);
	int travel() const;
};
BSTree::~BSTree() {
	if(left != NULL) delete left;
	if(right != NULL) delete right;
}
void BSTree::insert(int v) {
	if(v < w) {
		if(left == NULL) left = new BSTree(v);
		else left->insert(v);
	} else {
		if(right == NULL) right = new BSTree(v);
		else right->insert(v);
	}
}
int BSTree::travel() const {
	int cnt = 1;
	if(left != NULL) cnt += left->travel();
	if(right != NULL) cnt += right->travel();
	return cnt;
}

bool make(BSTree*&);
int compare(BSTree*, BSTree*);

int main()
{
	BSTree *aTree, *bTree;
	int t;
	
	for(t = 1; make(aTree) && make(bTree); t++) {
		int r = compare(aTree, bTree);
		printf("Case %d: %d command%s.\n", t, r, (r == 1) ? "" : "s");
		if(aTree != NULL) delete aTree;
		if(bTree != NULL) delete bTree;
	}
	
	return 0;
}

bool make(BSTree*& root)
{
	int n, i;
	scanf("%d", &n);
	if(n < 0) return false;
	root = NULL;
	for(i = 0; i < n; i++) {
		int a; scanf("%d", &a);
		if(root == NULL) root = new BSTree(a);
		else root->insert(a);
	}
	return true;
}
int compare(BSTree* a, BSTree* b)
{
	if(a == NULL && b == NULL) return 0;
	else if(a == NULL && b != NULL) return b->travel();
	else if(a != NULL && b == NULL) return 1;
	else if(a->w != b->w) return b->travel()+1;
	else return compare(a->left, b->left)+compare(a->right, b->right);
}