7-5 玩转二叉树

给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

输入格式：

输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。

输出格式：

在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

7
1 2 3 4 5 6 7
4 1 3 2 6 5 7

输出样例：

4 6 1 7 5 3 2

代码实现：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int pre[33],in[33],cnt[33];

struct node{
	int data;
	struct node *lch,*rch;
};
typedef struct node *tree;

tree build(int pre[],int in[],int n){
	if(n<=0) return NULL;
	node *t=new node;
	t->data=pre[0];
	t->lch=t->rch=NULL;
	int i;
	for(i=0;i<n;i++){
		if(in[i]==pre[0]) break;
	} 
	t->lch=build(pre+1,in,i);
	t->rch=build(pre+1+i,in+1+i,n-1-i);
	return t;
}

void trans(tree t){
	if(t==NULL) return;
	swap(t->lch,t->rch);
	trans(t->lch);
	trans(t->rch);
}

void order(tree t){
	if(t==NULL) return;
	queue<tree> q;
	tree p;
	q.push(t);
	while(q.size()){
		p=q.front();
		q.pop();
		cnt[m++]=p->data;
		if(p->lch) q.push(p->lch);
		if(p->rch) q.push(p->rch);
	}
}

int main(){
	cin>>n;
	for(int i=0;i<n;i++) cin>>in[i];
	for(int i=0;i<n;i++) cin>>pre[i];
	tree t=build(pre,in,n);
	trans(t);
	order(t);
	for(int i=0;i<n;i++){
		cout<<cnt[i];
		if(i<n-1) cout<<" ";
	}
	return 0;
}

7-6 部落

在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。

输入格式：

输入在第一行给出一个正整数N（≤104），是已知小圈子的个数。随后N行，每行按下列格式给出一个小圈子里的人：

K P[1] P[2] ⋯ P[K]

其中K是小圈子里的人数，P[i]（i=1,⋯,K）是小圈子里每个人的编号。这里所有人的编号从1开始连续编号，最大编号不会超过104。

之后一行给出一个非负整数Q（≤104），是查询次数。随后Q行，每行给出一对被查询的人的编号。

输出格式：

首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询，如果他们属于同一个部落，则在一行中输出Y，否则输出N。

输入样例：

4
3 10 1 2
2 3 4
4 1 5 7 8
3 9 6 4
2
10 5
3 7

输出样例：

10 2
Y
N

代码实现：

#include<bits/stdc++.h>
using namespace std;
int n;
const int N=1e4+10;
int fa[N];

int find(int x){
	if(fa[x]!=x) fa[x]=find(fa[x]);
	return fa[x];
}

void un(int x,int y){
	int dl=find(x);
	int dr=find(y);
	if(dl!=dr){
		fa[dr]=dl;
	}
}

int main(){
	for(int i=1;i<=1e4+10;i++){
		fa[i]=i;
	}
	cin>>n;
	int maxn=0,sum=0;
	while(n--){
		int t,x,y;
		cin>>t>>x;
		maxn=max(x,maxn);
		for(int i=1;i<t;i++){
			cin>>y;
			maxn=max(y,maxn);
			un(x,y);
		}
	}
	for(int i=1;i<=maxn;i++){
		if(fa[i]==i) sum++;
	}
	cout<<maxn<<" "<<sum<<endl;
	int m;
	cin>>m;
	while(m--){
		int a,b;
		cin>>a>>b;
		if(find(a)==find(b)) cout<<"Y"<<endl;
		else cout<<"N"<<endl;
	}
	return 0;
} 

7-7 列出叶结点

对于给定的二叉树，本题要求你按从上到下、从左到右的顺序输出其所有叶结点。

输入格式：

首先第一行给出一个正整数 n（≤10），为树中结点总数。树中的结点从 0 到 n−1 编号。随后 n 行，每行给出一个对应结点左右孩子的编号。如果某个孩子不存在，则在对应位置给出 "-"。编号间以 1 个空格分隔。

输出格式：

在一行中按规定顺序输出叶结点的编号。编号间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6

输出样例：

4 1 5

代码实现：

#include<bits/stdc++.h>
using namespace std;
struct node
{
    char l,r;
};
node tree[11];
queue<int> leaves;
map<int,bool> not_root;
void find_leave(int r)
{
    leaves.push(r);
    bool first=true;
    while(!leaves.empty())
    {
        int t=leaves.front();
        leaves.pop();
        if(tree[t].l!='-')leaves.push(tree[t].l-'0');
        if(tree[t].r!='-')leaves.push(tree[t].r-'0');
        if(tree[t].l=='-'&&tree[t].r=='-'){
            if(first){cout<<t;first=false;}
        
           else cout<<" "<<t;}
    }
}
int main()
{
    int N;
    cin>>N;
    for(int i=0;i<N;i++)
    {
        cin>>tree[i].l>>tree[i].r;
        if(tree[i].l!='-')not_root[tree[i].l-'0']=true;
        if(tree[i].r!='-')not_root[tree[i].r-'0']=true;
    }
    int root;
    for(int i=0;i<N;i++)
    {
        if(!not_root[i]){
            root=i;
            break;
        }
    }
    find_leave(root);
}

7-8 完全二叉树的层序遍历

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是完美二叉树。对于深度为 D 的，有 N 个结点的二叉树，若其结点对应于相同深度完美二叉树的层序遍历的前 N 个结点，这样的树就是完全二叉树。

给定一棵完全二叉树的后序遍历，请你给出这棵树的层序遍历结果。

输入格式：

输入在第一行中给出正整数 N（≤30），即树中结点个数。第二行给出后序遍历序列，为 N 个不超过 100 的正整数。同一行中所有数字都以空格分隔。

输出格式：

在一行中输出该树的层序遍历序列。所有数字都以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

8
91 71 2 34 10 15 55 18

输出样例：

18 34 55 71 2 10 15 91

实现代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int *tree;

void dfs(int x){
	if(x<=n){
		dfs(2*x);
		dfs(2*x+1);
		cin>>tree[x];
	}
}

int main(){
	cin>>n;
	tree =new int[n+1];
	dfs(1);
	for(int i=1;i<=n;i++){
		cout<<tree[i];
		if(i<n) cout<<" ";
	}
	return 0;
}

7-9 交换二叉树中每个结点的左孩子和右孩子

以二叉链表作为二叉树的存储结构，交换二叉树中每个结点的左孩子和右孩子。

输入格式:

输入二叉树的先序序列。

提示：一棵二叉树的先序序列是一个字符串，若字符是‘#’,表示该二叉树是空树，否则该字符是相应结点的数据元素。

输出格式:

输出有两行：

第一行是原二叉树的中序遍历序列；

第二行是交换后的二叉树的中序遍历序列。

输入样例:

ABC##DE#G##F###

输出样例:

CBEGDFA

AFDGEBC

实现代码：

#include<bits/stdc++.h>
using namespace std;

struct node{
	char data;
	struct node *lch,*rch;
};
typedef struct node *tree;

tree build(){
	node *t=new node;
	char a;
	cin>>a;
	if(a=='#') return NULL;
	t->data=a;
	t->lch=build();
	t->rch=build();
	return t;
}

void order(tree t){
	if(t==NULL) return;
	order(t->lch);
	cout<<t->data;
	order(t->rch);
}

void trans(tree t){
	if(t==NULL) return;
	swap(t->lch,t->rch);
	trans(t->lch);
	trans(t->rch);
}

int main(){
	tree t=build();
	order(t);
	cout<<endl;
	trans(t);
	order(t);
	return 0;
} 

7-10 建立与遍历二叉树

以字符串的形式定义一棵二叉树的先序序列，若字符是‘#’, 表示该二叉树是空树，否则该字符是相应结点的数据元素。读入相应先序序列，建立二叉链式存储结构的二叉树，然后中序遍历该二叉树并输出结点数据。

输入格式:

字符串形式的先序序列（即结点的数据类型为单个字符）

输出格式:

中序遍历结果

输入样例:

在这里给出一组输入。例如：

ABC##DE#G##F###

输出样例:

在这里给出相应的输出。例如：

CBEGDFA

实现代码：

#include<bits/stdc++.h>
using namespace std;

struct node{
	char data;
	struct node *lch,*rch;
};
typedef struct node *tree;

tree build(){
	node *t=new node;
	char a;
	cin>>a;
	if(a=='#') return NULL;
	t->data=a;
	t->lch=build();
	t->rch=build();
	return t;
}

void order(tree t){
	if(t==NULL) return;
	order(t->lch);
	cout<<t->data;
	order(t->rch);
}

int main(){
	tree t=build();
	order(t); 
	return 0;
}

7-11 树的遍历

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式：

输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式：

在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例：

4 1 6 3 5 7 2

实现代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int post[33],in[33],cnt[33];

struct node{
	int data;
	struct node *lch,*rch;
};
typedef struct node *tree;

tree build(int post[],int in[],int root,int start,int end){
	if(root<0||start>=end) return NULL;
	node *t=new node;
	t->data=post[root];
	t->lch=t->rch=NULL;
	int i;
	for(i=0;i<n;i++){
		if(in[i]==post[root]) break;
	}
	t->lch=build(post,in,root-end+i,start,i);
	t->rch=build(post,in,root-1,i+1,end);
	return t;
}

void order(tree t){
	if(t==NULL) return;
	queue<tree> q;
	tree p;
	q.push(t);
	while(q.size()){
		p=q.front();
		q.pop();
		cnt[m++]=p->data;
		if(p->lch) q.push(p->lch);
		if(p->rch) q.push(p->rch);
	}
}

int main(){
	cin>>n;
	for(int i=0;i<n;i++) cin>>post[i];
	for(int i=0;i<n;i++) cin>>in[i];
	tree t=build(post,in,n-1,0,n);
	order(t);
	for(int i=0;i<n;i++){
		cout<<cnt[i];
		if(i<n-1) cout<<" ";
	}
	return 0;
}

7-12 哈夫曼树

哈夫曼树，第一行输入一个数n，表示叶结点的个数。

需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出哈夫曼树的带权路径长度（WPL）。

输入格式:

第一行输入一个数n，第二行输入n个叶结点（叶结点权值不超过1000，2<=n<=1000）。

输出格式:

在一行中输出WPL值。

输入样例:

5
1 2 2 5 9

输出样例:

37

实现代码：

#include<bits/stdc++.h>
using namespace std;
int n;
priority_queue<int,vector<int>,greater<int>> q;


int main(){
	cin>>n;
	while(n--){
		int a;
		cin>>a;
		q.push(a); 
	}
	int sum=0;
	while(q.size()){
		int x=q.top();
		q.pop();
		if(q.empty()) break;
		int y=q.top();
		q.pop();
		sum+=x+y;
		q.push(x+y);
	}
	cout<<sum;
	return 0;
}

7-13 树层次遍历

我们已知二叉树与其自然对应的树相比，二叉树中结点的左孩子对应树中结点的左孩子，二叉树中结点的右孩子对应树中结点的右兄弟。进而我们可以利用“基于带空指针信息的先根序列构建二叉树”的方法来构建其对应的树的左孩子-右兄弟存储结构。如8 5 1 0 6 0 2 0 0 3 4 0 0 7 0 0 0对应图1(a)所示的树，1 2 0 3 0 4 0 0 0对应如图1(b)所示的树。

请编写程序用上述方法构建树，并给出树的层次遍历序列。

输入格式:

输入为一组用空格间隔的整数，个数不超过100个，表示带空指针信息的二叉树先根序列。其中空指针信息用0表示

输出格式:

输入为一组整数，每个整数后一个空格，表示该树的层次遍历序列。

输入样例:

1 2 0 3 0 4 0 0 0

输出样例:

1 2 3 4 

实现代码：

#include<bits/stdc++.h>
using namespace std;
int a[111];
stack<int> st;
vector<vector<int>> v(111);

void dj(){
	st.push(a[0]);
	int i=1;
	while(st.size()){
		if(a[i]!=0){
			st.push(a[i]);
			i++;
		}
		else{
			int m=st.size();
			int n=st.top();
			st.pop();
			i++;
			v[m].push_back(n);
		}
	}
}

int main(){
	int i=0;
	int n;
	while(cin>>n){
		a[i++]=n;
	}
	dj();
	for(int i=0;i<v.size();i++){
		for(int j=0;j<v[i].size();j++){
			cout<<v[i][j]<<" ";
		}
	}
	return 0;
}