子树问题数的525subsize.cpp

设计一个算法

#include<iostream>
#include<fstream>
using namespace std;

template <class T>//二叉树结点类
class BinaryTreeNode
{
	public:
		BinaryTreeNode()
		{
			LeftChild=RightChild=0;	
		}
		BinaryTreeNode(const T& e)
		{
			data=e;
			LeftChild=RightChild=0;
		
		}
		BinaryTreeNode(const T& e,BinaryTreeNode *l,BinaryTreeNode *r)
		{
			data=e;
			LeftChild=l;
			RightChild=r;
		}
		T data;
		BinaryTreeNode<T> *LeftChild,*RightChild;
};


template<class T>
class BinaryTree
{
	public:
		BinaryTree()
		{
			root=0;
		}
		~BinaryTree()
		{
		}
		bool Empty()const
		{
			return ((root)?false:true);
		}
		bool Root(T& x)const;
		void MakeTree(const T&element,BinaryTree<T>&left,BinaryTree<T>&right);
		void BreakTree(const T&element,BinaryTree<T>&left,BinaryTree<T>&right);
		bool ReadBinaryTree(istream&in,int n);
		bool OutputTree(int n,ostream&out);
		
	private:
		
		BinaryTreeNode<T> *root;
		BinaryTreeNode<T> Input(T data)
		{	
			BinaryTreeNode<T> *p;
			p=new BinaryTreeNode<T>(data);
			return *p;
		}
		int preorder(BinaryTreeNode<T> k,int putorder[],int value[],int *count,int n);
};

template<class T>
bool BinaryTree<T>::Root(T &x)const
{
	if(root)
	{
		x=root.data;
		return true;
	}
	else
		return flase;
}
template<class T>
bool BinaryTree<T>::ReadBinaryTree(istream&in,int n)
{
	int count,mid,left,right;
	BinaryTreeNode<T> *a;
	a=new BinaryTreeNode<T> [n+1];
	for(count=1;count<=n;count++)
	{
		a[count]=Input(count);
	}
	in>>mid>>left>>right;
	if(left==0)
	{
		a[mid].LeftChild=0;
	}
	else
		a[mid].LeftChild=&a[left];
	if(right==0)
	{
		a[mid].RightChild=0;
	}
	else
		a[mid].RightChild=&a[right];
	root=&a[mid];
	for(count=2;count<=n;count++)
	{
		in>>mid>>left>>right;
		if(left==0)
		{
			a[mid].LeftChild=0;
		}
		else
			a[mid].LeftChild=&a[left];
		if(right==0)
		{
			a[mid].RightChild=0;
		}
		else
			a[mid].RightChild=&a[right];
	}
	//delete a;
	if(root)
		return true;
	else
		return false;
}
template<class T>
bool BinaryTree<T>::OutputTree(int n,ostream&out)
{
	BinaryTreeNode<T> k=*root;
	int *putorder,*value,*count;
	putorder=new int[n+1];
	value=new int[n+1];
	for(int s=0;s<=n;s++)
	{
		putorder[s]=0;
		value[s]=0;
	}
	count=new int(1);
	//*count=1;
	preorder(k,putorder,value,count,n);
	for(int i=1;i<=n;i++)
	{
		out<<value[putorder[i]]<<' ';
	}
	out<<endl;
	delete [] putorder;
	delete [] value;
	return true;
}
template<class T>
int BinaryTree<T>::preorder(BinaryTreeNode<T> k,int putorder[],int value[],int *count,int n)
{
	int l=0,r=0,t=*count;
	if(t<=n)
	{
		putorder[t]=k.data;
		t++;
		*count=t;
	}
	if(k.LeftChild==0&&k.RightChild==0)
	{
		value[k.data]+=1;
		return 1;
	}
	else
	{
		if(k.RightChild==0)
		{
			value[k.data]+=(preorder(*(k.LeftChild),putorder,value,count,n)+1);
			l=value[k.data];
			return l;
		}
		else
		{
			if(k.LeftChild==0)
			{
				value[k.data]+=(preorder(*(k.RightChild),putorder,value,count,n)+1);
				r=value[k.data];
				return r;
			}
			else
			{
				value[k.data]+=preorder(*(k.LeftChild),putorder,value,count,n);
				l=value[k.data];
				value[k.data]+=preorder(*(k.RightChild),putorder,value,count,n);
				r=value[k.data];
				value[k.data]++;
				return value[k.data];
			}
		}
	}
}




int main()
{
	ifstream in("input.txt");
	ofstream out("output.txt");
	if(in.fail())
	{
		cout<<"the input.txt is not exist!"<<endl;
		exit(1);
	}
	BinaryTree<int> tree;
	int n;
	in>>n;
	tree.ReadBinaryTree(in,n);
	tree.OutputTree(n,out);
	return 1;
}