[数据结构与算法]PTA写BUG日志——关于数据结构里面的“树”（算法笔记上机实战）

二叉树的遍历

• 先序遍历
• 中序遍历
• 后序遍历
• 层序遍历

经典问题1：给出两个遍历树的序列，如何复现树？🎄
答：一定会需要中序遍历来区分左右子树，中序遍历+（剩余3种任一遍历的数组即可复现原来的树的结构）

练习1

PTA甲级1020

这题是根据中序和后序来复现树的结构，再用层次遍历输出即可，思路不是特别难，主要涉及复现函数create以及层次遍历函数levelTravel

复现函数《算法笔记》给了先序+中序的版本，可以参考画图加深理解

//1020
#include<bits/stdc++.h>
using namespace std;
int n;
int pos[100];
int in[100]; 
//定义树的结构体 
struct node{
	int data;
	node*lchild;
	node*rchild;
};
//给出后序遍历+中序遍历->层序遍历
void levelTravel(node*root){
	int count=0;
	//层序遍历
	queue<node*>q;
	node*temp=new node;
	q.push(root);
	while(!q.empty()){
		count++;
		temp=q.front();
		printf("%d",temp->data);//这里需要注意输出格式 
		if(count<n)printf(" ");
		q.pop();
		if(temp->lchild!=NULL){
			q.push(temp->lchild);
		}
		if(temp->rchild!=NULL){
			q.push(temp->rchild);
		}
	} 
	return ;
} 
node*create(int posL,int posR,int inL,int inR){
	//递归：复现树
	if(posL>posR){
		return NULL;//递归边界 
	} 
	//递归
	node*root=new node;
	//根节点是后序遍历最后一个元素
	root->data=pos[posR];
	int k;
	for(k=inL;k<=inR;k++){
		if(root->data==in[k]){
			break;
		}
	} 
	//中序，左子树元素个数 
	int left_num=k-inL;
	//debug
	//printf("中序：%d个左子树\n",left_num); 
	root->lchild=create(posL,posL+left_num-1,inL,k-1);
	root->rchild=create(posL+left_num,posR-1,k+1,inR);
	return root;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&pos[i]);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&in[i]);
	}
	//根据后序遍历+中序遍历求树
	node*root=create(1,n,1,n);
	//debug
	//printf("root=%d\n",root->data); 
	//中序遍历
	levelTravel(root); 
	return 0;
} 

练习2

PTA甲级1086
这题的思路在于，列出题干中的输入顺序：

• push依次输入的顺序，单独看就是先序遍历树的结果
• pop出栈的顺序，也就是自己写一个栈，按照题目输入输出操作一波得到的数列，就是中序遍历的结果
• 我们已经知道中序+任一其他遍历结果即可复现原来的树（这也是本题为什么会想到上两个点的突破口）

代码不难，和上一题几乎一样,只不过多了栈的处理以及输入的对于先序、中序数列的存储问题😊

//1086
#include<bits/stdc++.h>
using namespace std;
int pre[100];
int in[100];
struct node{
	int data;
	node*rchild;
	node*lchild;
};
//解题思路：
//push 的顺序是先序
//pop的顺序是中序 
//给出后序遍历
node*create(int preL,int preR,int inL,int inR){
	if(preL>preR)return NULL;
	node*root=new node;
	root->data=pre[preL];
	int k;
	for(k=inL;k<=inR;k++){
		if(in[k]==root->data)
			break; 
	}
	int num_left=k-inL;
	root->lchild=create(preL+1,preL+num_left,inL,k-1);
	root->rchild=create(preL+num_left+1,preR,k+1,inR);
	return root;
}
int flag=0;
int n;
void posTravel(node*root){
	if(root==NULL){
		return;
	}
	posTravel(root->lchild);
	posTravel(root->rchild);
	if(flag==0){
		printf("%d",root->data);
		flag=1;}
	else{
		printf(" %d",root->data);
	}
} 
int main(){
	stack<int>st;
	int data;
	string op;
	
	int countpre=0;
	int countin=0;
	scanf("%d",&n);
	while(!(countpre==n&&countin==n)){
		cin>>op;
		if(op=="Push"){
			cin>>data;
			pre[++countpre]=data;
			st.push(data);
		}else{
			data=st.top();
			st.pop();
			in[++countin]=data;
		}	
	}
	/*debug
	for(int i=1;i<=n;i++){
		printf("%d ",pre[i]);
	} 
	printf("\n");
	for(int i=1;i<=n;i++){
		printf("%d ",in[i]);
	} */
	node*root=create(1,n,1,n);
	posTravel(root);
	return 0;
}

练习3

PTA甲级1102
这题考的是：

• 静态二叉树的定义
• 静态二叉树的层次遍历以及中序遍历（虽然不太清楚为啥遍历输出的时候，左右位置得颠倒~昂）

难点我觉得是如何寻找根节点，因为题目N的最大值为10吗，所以我用中序遍历遍历每一个结点，哪个能遍历完整个树，哪个结点就是根节点，当然这样写在题目大的时候肯定超时啦~

下面是AC代码：
今天三题目都是一次AC的，说明上学期数据结构理论课我学的不错~

//1102
#include<bits/stdc++.h>
using namespace std;
//考察的是静态树
struct Tree{
	int data;
	int rchild=-1;
	int lchild=-1;
}node[100];
int ccount;
//寻找根节点
void rootfind(int root){
	if(root==-1)return ;
	rootfind(node[root].lchild);
	ccount++;
	rootfind(node[root].rchild);
	return ;
}  
bool flag=false;
//中序遍历
void inTravel(int root){
	if(root==-1)return ;

	inTravel(node[root].rchild);
	if(flag==false){
		flag=true;
		printf("%d",node[root].data);
	}else
		printf(" %d",node[root].data);
	inTravel(node[root].lchild);
	return ;
} 
//层序遍历
void levelTravel(int root) {
	queue<int>q;
	q.push(root);
	int temp;
	while(!q.empty()){
		temp=q.front();
		if(flag==false){
			flag=true;
			printf("%d",node[temp].data);
		}else{
			printf(" %d",node[temp].data);
		}
		q.pop();
		if(node[temp].rchild!=-1)q.push(node[temp].rchild );
		if(node[temp].lchild!=-1)q.push(node[temp].lchild);
	}
}
int main(){
	int n;
	scanf("%d",&n);
	string ch1,ch2;
	int r,l;
	for(int i=0;i<n;i++){
		cin>>ch1>>ch2;
		if(ch1!="-"){
			l=stoi(ch1);
			node[i].lchild=l;
		}
		if(ch2!="-"){
			r=stoi(ch2);
			node[i].rchild=r;
		}
		node[i].data=i;
	}
	//如何找到根节点
	int root=-1;
	for(int i=0;i<n;i++){
		ccount=0;
		rootfind(i);
		if(ccount==n){
			root=i;
			break;
		}
	}
	levelTravel(root);
	printf("\n");
	flag=false;
	inTravel(root);
	
	return 0;
} 

树的遍历

结构体中，子节点用vector实现以便节省空间，本书中树的遍历利用的是静态的写法
PTA甲级1079
这题考察的是静态树的层次遍历
傻了傻了，阅读理解的问题，卡在p+r还是p+r%这个问题上半天~完全做题做傻了😂

//1079,1090
#include<bits/stdc++.h>
using namespace std;
int n;
double p,r;
const int maxn=200000;
struct Node{
	double price;
	int amount=0;
	vector<int>child;
}node[maxn];
bool isc[maxn]; 
//层序遍历，解决每一层的价值:难点，如何找到根节点 
double sum=0;
void levelTravel(int root){
	queue<int>q;
	q.push(root);
	while(!q.empty()){
		int top=q.front();
		q.pop();
		for(int i=0;i<node[top].child.size();i++){
			//遍历子节点，将子节点加入队列中
			int child=node[top].child[i] ;
			q.push(child);
			node[child].price=node[top].price*(1+r/100);
		}
		if(node[top].child.size()==0){
			//叶子结点
			//printf("叶子: p=%.2f amount=%d\n",node[top].price,node[top].amount); 
			sum+=(node[top].price*node[top].amount);
		}
	}
	return;
} 
int main(){
	memset(isc,false,sizeof(isc));
	scanf("%d %lf %lf",&n,&p,&r);
	int num;
	int temp;
	for(int i=0;i<n;i++){
		scanf("%d",&num);
		if(num!=0){
			for(int j=0;j<num;j++){
			scanf("%d",&temp);
			node[i].child.push_back(temp);//保存子节点的位置 
			isc[temp]=true;
			}
		}
		else{
			scanf("%d",&node[i].amount);
		}
	}
	
	int root=-1;
	for(int i=0;i<n;i++){
		if(!isc[i]){
			root=i;
			break;
		}
	}
	//printf("root=%d\n",root);
	node[root].price=p;
	levelTravel(root);
	printf("%.1f",sum);
	
	return 0;
}