子树问题数的539subsize.cpp

设计一个算法

#include<iostream>
#include<fstream>
using namespace std;
#include "time.h"
clock_t start,finish;
ifstream in("input.txt");
ofstream out("output.txt");
class BtreeNode{
	friend class Btree;
public:
	BtreeNode(){childl=childr=0;}
	void MakeNode(int e){
		data=e;
		childl=childr=0;
	}
private:
	int data;
	BtreeNode *childl,*childr;
};
class Btree{
public:
	Btree(){root=0;}
	~Btree(){};
	void GetRoot(BtreeNode *e){root=e;}
	void MakeBtree(BtreeNode *e,BtreeNode *l,BtreeNode *r);
	void PreOutput(){
		PreOrder(Output,root);
	}
private:
	BtreeNode *root;
	void PreOrder(void (*Visit)(BtreeNode *u),BtreeNode *t){
		if(t){
			Visit(t);
			PreOrder(Visit, t->childl);
			PreOrder(Visit, t->childr);
		}
}
	static void Output(BtreeNode *t){
		out<<BtreeCount(t)<<' ';
	}
	static int BtreeCount(BtreeNode *t){
		if(t)
			return BtreeCount(t->childl)+BtreeCount(t->childr)+1;
		else
			return 0;
	}
};
void Btree::MakeBtree(BtreeNode *e,BtreeNode *l,BtreeNode *r){
	if(l->data==0)
		e->childl=0;
	else 
		e->childl=l;
	if(r->data==0)
		e->childr=0;
	else
		e->childr=r;
}
void main()
{
	start=clock();
	if(in.fail()){
		cout<<"the input.txt is not exist!";
		exit(1);
	}
	Btree sub;
	int num,i,dad,cl,cr;
	in>>num;
	BtreeNode *Node=new BtreeNode[num+1];
	Node[0].MakeNode(0);
	for(i=1;i<=num;i++)
		Node[i].MakeNode(i);
	in>>dad>>cl>>cr;
	sub.GetRoot(&Node[dad]);
	sub.MakeBtree(&Node[dad],&Node[cl],&Node[cr]);
	for(i=2;i<=num;i++){
		in>>dad>>cl>>cr;
		sub.MakeBtree(&Node[dad],&Node[cl],&Node[cr]);
	}
	sub.PreOutput();
	finish=clock();
	cout<<finish-start<<endl;
}