树学习总结_C/C++/C#

1.1020 Tree Traversals
题目大意：给定二叉树的后序遍历和中序遍历，请输出层序遍历。
只要给定中序遍历，然后搭配其余的一个遍历就可以唯一的确定一个唯一的二叉树。
算法的思想主要是进行左右子树的划分，一共有prel,prer,inl,inr四个比较关键的参数
使用指针的方式实现树的构建

#include 
#include
#include
#include
#include
#include
#include
#include
//1020 Tree Traversals复习 

using namespace std; 
typedef struct Node
{
	Node *lchild;
	Node *rchild;
	int date;
 } node;

 node *NewNode(int a)
 {
 	node *root=new node;
 	root->date=a;
 	root->lchild=root->rchild=NULL;
 	return root;
 }
 int n;
 vector temp,post,in;
 node *solve(int postl,int postr,int inl,int inr)
 {
 	if(postl>postr)
 	{
 		return NULL;
	 }
	 node *root=NewNode(post[postl]);
	 int i;
	 for(i=inl;i<=inr;i++)
	 {
	 	if(post[postl]==in[i])
	 	{
	 		break;
		 }
	 }
	 int rightnum=inr-i;
	 root->lchild=solve(postl+rightnum+1,postr,inl,i-1);
	 root->rchild=solve(postl+1,postl+rightnum,i+1,inr);
	 return root;
 }
 int k=0;
 void layerorder(node *root)
 {
 	queue q;
 	q.push(root);
 	while(!q.empty())
 	{
 		node *top=q.front();
 		q.pop();
 		if(k==0)
 		{
		 printf("%d",top->date);
		 k++;
	   }
 		else
 		{
		printf(" %d",top->date);
	    }
 		
 		if(top->lchild!=NULL) 
		 {
		 q.push(top->lchild);
	    }
 	 	if(top->rchild!=NULL) 
		  q.push(top->rchild);
 		
	 }
 }
int main()
{
	cin>>n;
	for(int i=0;i
		int a;
		scanf("%d",&a);
		temp.push_back(a);
	}
	for(int i=n-1;i>=0;i--)
	{
		post.push_back(temp[i]);
	}
	for(int i=0;i
		int a;
		scanf("%d",&a);
		in.push_back(a);
	}
	node *root=solve(0,n-1,0,n-1);
	layerorder(root);
	system("pause");
	return 0;
}

1086 Tree Traversals Again
树可以由栈的操作唯一确定，将前序和中序提取出来就可以完成本题。

#include 
#include
#include
#include
#include
#include
#include
#include
#include
//1086 Tree Traversals Again复习 

using namespace std; 
typedef struct Node
{
	Node *lchild;
	Node *rchild;
	int date;
 } node;

 node *NewNode(int a)
 {
 	node *root=new node;
 	root->date=a;
 	root->lchild=root->rchild=NULL;
 	return root;
 }
 int n; 
 vector in,pre;
node *creat(int prel,int prer,int inl,int inr)
{
	if(prel>prer)
	{
		return NULL;
	}
	node *root=NewNode(pre[prel]);
	int k;
	for(k=inl;k<=inr;k++)
	{
		if(in[k]==pre[prel])
		{
			break;
		}
	}
	int leftnum=k-inl;
	root->lchild=creat(prel+1,prel+leftnum,inl,k-1);
	root->rchild=creat(prel+leftnum+1,prer,k+1,inr);
	return root;
}
int m=1;
 void postorder(node *root)
 {
 	if(root==NULL)
 	{
 		return;
	 }
	 postorder(root->lchild);
	 postorder(root->rchild);
	 if(m==1)
	 {
	 	printf("%d",root->date);
	 	m++;
	 }
	 else
	 {
	 	printf(" %d",root->date);
	 }
 }
int main()
{
	cin>>n;
	stack sta;
	for(int i=0;i<2*n;i++)
	{
		char s[20];
		int num;
		scanf("%s",s);
		if(s[1]=='u')
		{
			scanf("%d",&num);
			pre.push_back(num);
			sta.push(num);
		}
		else
		{
			num=sta.top();
			in.push_back(num);
			sta.pop();
		}
	}
	node *root=creat(0,n-1,0,n-1);
	postorder(root);
	

	system("pause");
	return 0;
}

1102 Invert a Binary Tree
由题目给定的条件创造一个树，然后输出树左右子树翻转后的层序和中序遍历。本次使用静态树来实现比较简单。
最后要寻找根节点，根节点一定满足不是其它节点的孩子。用一个bool型的数组判断即可。
需要注意的是scanf对于字符型会将换行符和空白符也吸收，需要进行getchar的吸收。

#include 
#include
#include
#include
#include
#include
#include
#include
#include
//1086 Tree Traversals Again复习 

using namespace std; 
const int inf=0x3fffffff;
const int maxn=20;
struct Node
{
	int lchild;
	int rchild;

 } node[maxn];
int n;
bool judge[maxn]={false};
int c=1;
void layerorder(int root)
{
	queue q;
	q.push(root);
	while(!q.empty())
	{
		int top=q.front();
		q.pop();
		if(c==1)
		{
			c++;
			printf("%d",top);
		
		}
		else
		{
			printf(" %d",top);	
		}
		if(node[top].rchild!=inf)
		q.push(node[top].rchild);
		if(node[top].lchild!=inf)
		q.push(node[top].lchild);
	}
}
int c1=1;
void inorder(int root)
{
	if(root==inf)
	{
		return;
	}
	inorder(node[root].rchild);
	    if(c1==1)
		{
			c1++;
			printf("%d",root);
		
		}
		else
		{
			printf(" %d",root);	
		}
		inorder(node[root].lchild);
}
int main()
{
	cin>>n;
	getchar();
	for(int i=0;i
		char c1,c2;
		scanf("%c %c",&c1,&c2);
		if(c1=='-')
		{
			node[i].lchild=inf;
		}
		else
		{
			int w=c1-'0';
			node[i].lchild=w;
			judge[w]=true;
		}
		if(c2=='-')
		{
			node[i].rchild=inf;
		}
		else
		{
			int w=c2-'0';
			node[i].rchild=w;
			judge[w]=true;
		}
		getchar();
	}
	int root;
    for(root=0;root
    	if(judge[root]==false)
    	{
    		break;
		}
	}
    layerorder(root);
    cout<
#include
#include
#include
#include
#include
#include
#include
#include
//1086 Tree Traversals Again复习 

using namespace std; 
const int inf=0x3fffffff;
const int maxn=100010;
struct node
{
	vector child;
	double price;
	int number;
}tree[maxn]; 
int n;
double price,c;
double all=0;
void layerorder(int s)
{
	queue q;
	q.push(s);
	while(!q.empty())
	{
		int top=q.front();
		q.pop();
		for(int i=0;i
			int v=tree[top].child[i];
			tree[v].price=tree[top].price+tree[top].price*c*0.01;
			q.push(v);
		}
	}
}
void preorder(int s)
{
	if(tree[s].child.size()==0)
	{
		all+=tree[s].number*tree[s].price;
	}
	for(int i=0;i
		preorder(tree[s].child[i]);
	}
}
int main()
{
	cin>>n>>price>>c;
	tree[0].price=price;
	for(int i=0;i
		int k;
		scanf("%d",&k); 
	    for(int j=0;j
	    	int input;
	    	scanf("%d",&input);
	    	tree[i].child.push_back(input);
		}
		if(k==0)
		{
			scanf("%d",&tree[i].number);
		}
	}
    layerorder(0);
    preorder(0);
    printf("%0.1lf",all);
	system("pause");
	return 0;
}

1090 Highest Price in Supply Chain

#include 
#include
#include
#include
#include
#include
#include
#include
#include
//1086 Tree Traversals Again复习 

using namespace std; 
const int inf=0x3fffffff;
const int maxn=100010;
struct node
{
	vector child;
	double price;
}tree[maxn]; 
int n;
double price,c;
double high=-5;
int num=0;
void layerorder(int s)
{
	queue q;
	q.push(s);
	tree[s].price=price;
	while(!q.empty())
	{
		int top=q.front();
		q.pop();
		for(int j=0;j
			int v=tree[top].child[j];
			tree[v].price=tree[top].price+tree[top].price*c*0.01;
			q.push(v);
		}
	}
}
void preorder(int s)
{
	if(tree[s].child.size()==0)
	{
		if(tree[s].price>high)
		{
			num=1;
			high=tree[s].price;
		}
		else if(tree[s].price==high)
		{
			num++;
		}
	}
	for(int i=0;i
		preorder(tree[s].child[i]);
	}
}
int main()
{
	cin>>n>>price>>c;
	int root=0;
	for(int i=0;i
		int input;
		scanf("%d",&input);
		if(input!=-1)
		{
			tree[input].child.push_back(i);
		 } 
		 else
		 {
		 	root=i;
		 }
	}
	layerorder(root);
	preorder(root);
	printf("%0.2lf %d",high,num);
	system("pause");
	return 0;
}

1094 The Largest Generation

#include 
#include
#include
#include
#include
#include
#include
#include
#include
//1094 The Largest Generation

using namespace std;
const int inf=0x3fffffff;
const int maxn=100010;
struct node
{
	vector child;
	int layer;
}tree[maxn]; 
struct Save
{
	int layer;
	int num;
	Save()
	{
		layer=0;
		num=0;
	}
}save[maxn];
int n,m; 

void layerorder(int s)
{
	queue q;
	q.push(s);
	tree[s].layer=1;
	save[tree[s].layer].num++;
	save[tree[s].layer].layer=1;
	while(!q.empty())
	{
		int top=q.front();
		q.pop();
	
		for(int i=0;i
			
			int v=tree[top].child[i];
			tree[v].layer=tree[top].layer+1;
			q.push(v);
			save[tree[v].layer].num++;
			save[tree[v].layer].layer=tree[v].layer;
		}
	}
}

bool cmp(Save a,Save b)
{
	
	return a.num>b.num;
}

int main()
{
  cin>>n>>m;
  for(int i=0;i
  	int id,num;
  	scanf("%d %d",&id,&num);
  	for(int j=0;j
  		int input;
  		scanf("%d",&input);
  		tree[id].child.push_back(input);
	  }
  }
  layerorder(1);
  sort(save,save+n+1,cmp);
  cout< 
1106 Lowest Price in Supply Chain 
#include 
#include
#include
#include
#include
#include
#include
#include
#include
//1094 The Largest Generation

using namespace std;
const int inf=0x3fffffff;
const int maxn=100010;
struct node
{
	vector child;
	double price;
}tree[maxn]; 
int n;
double price,c;
double mina=inf;
int num=0;
void layerorder(int s)
{
	queue q;
	q.push(s);
	tree[s].price=price;
	while(!q.empty())
	{
		int top=q.front();
		q.pop();
		for(int i=0;i
			int v=tree[top].child[i];
			tree[v].price=tree[top].price+tree[top].price*c*0.01;
			q.push(v);
		}
	}
}
void preorder(int s)
{
	if(tree[s].child.size()==0)
	{
		if(tree[s].price
			mina=tree[s].price;
			num=1;
		}
		else if(tree[s].price==mina)
		{
			num++;
		}
	}
	   for(int i=0;i
			preorder(tree[s].child[i]);
		}
}
int main()
{
  cin>>n>>price>>c;
  for(int i=0;i
  	int num;
  	scanf("%d",&num);
  	for(int j=0;j
  		int input;
  		scanf("%d",&input);
  		tree[i].child.push_back(input);
	  }
  }
  layerorder(0);
  preorder(0);
  printf("%0.4lf %d",mina,num);
	system("pause");
	return 0;
}

树学习总结

C/C++/C#相关栏目本月热门文章