旋转变换642rotation.cpp

来自「设计一个算法」· C++ 代码 · 共 80 行

#include<fstream>
#include<iostream>
using namespace std;
struct TreeNode
{
	int data;
	TreeNode*left,*right;
};	
ifstream in("input.txt");
ofstream out("output.txt");
int count1=0,count2=0;
void main()
{

	void Inorder_Store(TreeNode*,int*);
	void Preorder(TreeNode*);
	void Tree_Fill(TreeNode*,int*);
	void MakeTree(int,TreeNode**,TreeNode*&);
	int num;
	in>>num;
	TreeNode**a=new TreeNode*[num],*root;
	MakeTree(num,a,root);
	int*b=new int[num];
	Inorder_Store(root,b);
	in>>num;
	MakeTree(num,a,root);
	Tree_Fill(root,b);
	Preorder(root);
}
void MakeTree(int num,TreeNode**a,TreeNode*&root)
{
	for(int i=0;i<num;i++)
	{
		a[i]=new TreeNode;
		a[i]->data=i+1;
		a[i]->left=a[i]->right=0;
	}
	for(i=0;i<num;i++)
	{
		int Father,LeftChild,RightChild;
		in>>Father>>LeftChild>>RightChild;
		if(i==0)
			root=a[Father-1];
		if(LeftChild)
			a[Father-1]->left=a[LeftChild-1];
		if(RightChild)
			a[Father-1]->right=a[RightChild-1];
	}
}
void Inorder_Store(TreeNode*root,int*b)
{
	if(root)
	{
		Inorder_Store(root->left,b);
		b[count1]=root->data;
		count1++;
		Inorder_Store(root->right,b);
	}
}
void Tree_Fill(TreeNode*root,int*b)
{
	if(root)
	{
		Tree_Fill(root->left,b);
		root->data=b[count2];
		count2++;
		Tree_Fill(root->right,b);
	}
}
void Preorder(TreeNode*root)
{
	
	if(root)
	{
		out<<root->data<<' ';
		Preorder(root->left);
		Preorder(root->right);
	}
}