+++

任意二叉树的层次遍历

题目描述

有若干个节点，每个节点上都有编号，把这些节点随意地构成二叉树，请编程输出该二叉树的层次遍历序列。

输入

第一行是n（n小于100）,表示有n个节点，每个节点按从1到n依次编号。第一行后有n行，每行三个正整数i、l、r，分别表示节点i及对应的左右孩子的编号，如果不存在孩子则以-1表示。三个整数之间用一个空格隔开。

输出

输出该二叉数的层次遍历序列。

样例输入

4
1 2 4
3 1 -1
2 -1 -1
4 -1 -1

样例输出

3 1 2 4

# include <bits/stdc++.h>
using namespace std;
struct A{
	int data;
	A* l;
	A* r;
	A* fa;
}BTree[100];//一个结构体存放结点
queue <A*> q;//用队列实现
void bfs(A* x)
{
	if(x==NULL)
		return;
	q.push(x);//如果不空入队
	while(!q.empty())
	{
		A* current=q.front();//队头出队
		cout<<current->data<<" ";
		q.pop();
		if(current->l)
		{
			q.push(current->l);//左孩子入队
		}
		if(current->r)
		{
			q.push(current->r);//右孩子入队
		}

	}
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		BTree[i].data=i;
		BTree[i].l=NULL;
		BTree[i].r=NULL;
		BTree[i].fa=NULL;
	}
	for(int i=1;i<=n;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		if(b!=-1)
		{
			BTree[a].l=BTree+b;
			BTree[b].fa=BTree+a;
		}
		if(c!=-1)
		{
			BTree[a].r=BTree+c;
			BTree[c].fa=BTree+a;
		}
	}
	int pos;
	for(int i=1;i<=n;i++)
	{
		if(BTree[i].fa==NULL)
		{
			pos=i;
			break;
		}
	}//找根节点
	bfs(BTree+pos);//从根节点开始搜索
	return 0;
}

小根堆的判定

题目描述

堆是以线性连续方式存储的完全二叉树，小根堆的每一个元素都不大于其左右孩子，现在给你n个完全二叉树数组存储序列，请编程判定相应完全二叉树数组存储序列是否为小根堆。

输入

第一行n（n<100），表示有n组测试用例。后边的n行，每一行都是相应完全二叉树数组存储序列(序列最长为100)。

输出

对应相应完全二叉树数组存储序列，判定为小根堆的输出True，否则输出False。

样例输入

2
30 26 27 88
5 6 7 8 9 10

样例输出

False
True

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int PD[100];
	
	while(n--)
	{
		for(int i=1;i<100;i++)
		{
			PD[i]=99999;
		}
		bool flag=0;
		int t;
		for(int i=1;;i++)
		{
			cin>>PD[i];
			if(cin.get()=='\n')
			{
				t=i;
				break;	
			}
		}
		for(int j=1;j<=(t)/2;j++)
		{
			if(PD[j]>PD[2*j]||PD[j]>PD[2*j+1])
			{
				flag++;
			}
		}		
		if(flag) cout<<"False"<<endl;
		else cout<<"True"<<endl;
	}
}

最小堆的形成

题目描述

现在给你n个结点的完全二叉树数组存储序列，请编程调整为最小堆，并输出相应最小堆的存储序列。

输入

第一行是n，第二行是n个结点的完全二叉树数组存储序列。

输出

输出相应最小堆的存储序列。

样例输入

8
53 17 78 23 45 65 87 9

样例输出

9 17 65 23 45 78 87 53

#include <bits/stdc++.h>
using namespace std;
/*1.从根结点处开始，选出左右孩子中值较小的孩子。
 2.让小的孩子与其父亲进行比较。
 若小的孩子比父亲还小，则该孩子与其父亲的位置进行交换。并将原来小的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止。
 若小的孩子比父亲大，则不需处理了，调整完成，整个树已经是小堆了。
*/
int n;
int a[205];
void down(int *ary,int pa) {
     int temp = ary[pa];
     int cld = 2*pa;
     while (cld <=n) {
     	if (cld + 1 <= n && ary[cld + 1] < ary[cld]) {
             cld++;
         }//选出根节点的左孩子右孩子里面较小的
         if (temp <= ary[cld])  break;//小孩子比父亲大，不用管
         ary[pa] = ary[cld];//小的孩子比父亲还小，则该孩子与其父亲的位置进行交换。并将原来小的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止。
         ary[cld]=temp;
         pa = cld;
         cld = 2*cld;
     }
 }
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
    for (int i= n/2; i >= 1; i--) {
        down(a,i);
    }//左子树右子树都是最小堆
    for(int i=1;i<=n;i++) cout<<a[i]<<' ';
}

无向图的深度优先搜索

题目描述

已知一个无向图G的顶点和边，顶点从0依次编号，现在需要深度优先搜索，访问任一邻接顶点时编号小的顶点优先，请编程输出图G的深度优先搜索序列。

输入

第一行是整数m和n（1<m,n<100），分别代表顶点数和边数。后边n行，每行2个数，分别表示一个边的两个顶点。

输出

该图从0号顶点开始的深度优先搜索序列。

样例输入

5 5
0 1
2 0
1 3
1 4
4 2

样例输出

0 1 3 4 2

#include <bits/stdc++.h>
using namespace std;
int n, m, sum;
int vis[101], e[101][101];
void dfs(int cur) {
	int i = 0;
	cout<<cur<<' ';
	sum++;
	if (sum == n) {
		return;
	}
	for (i = 1; i <= n; i++) {
		if (e[cur][i] == 1 && vis[i] == 0) {
			vis[i] = 1;
			dfs(i);//与广度优先搜索区别在于换结点了
		}
	}
	return;
}

int main() {
	int a,b,i,j;
	cin>>m>>n;
	for (i = 0; i < m; i++) {
		for (j = 0; j < m; j++) {
			if (i == j) {
				e[i][j] = 0;
			} else {
				e[i][j] = 999999999;
			}
		}
	}
	for (i = 0; i < n; i++) {
		cin>>a>>b;
		e[a][b] = 1;
		e[b][a] = 1;
	}//把无向图用矩阵存储起来
	vis[0] = 1;
	dfs(0);//从第一个结点开始
	return 0;
}

无向图的广度优先搜索

题目描述

已知一个无向图G的顶点和边，顶点从0依次编号，现在需要广度优先搜索，访问任一邻接顶点时编号小的顶点优先，请编程输出图G的广度优先搜索序列。

输入

第一行是整数m和n（1<m,n<100），分别代表顶点数和边数。后边n行，每行2个数，分别表示一个边的两个顶点。

输出

该图从0号顶点开始的广度优先搜索序列。

样例输入

5 5
0 1
2 0
1 3
1 4
4 2

样例输出

0 1 2 3 4

#include <bits/stdc++.h>
using namespace std;
int book[101],e[101][101];
queue<int> q;
int main()
{
	int i,j,a,b,m,n,cnt=0,cur;
	cin>>m>>n;
	for (i = 0; i < m; i++)
	{
		for (j =0; j < m; j++)
		{
			if (i == j)
			{
				e[i][j] = 0;
			}
			else
			{
				e[i][j] = 999999;
			}
		}
	}
	for (i = 0; i < n; i++)
	{
		cin>>a>>b;
		e[a][b] = 1;
		e[b][a] = 1;
 
	}//建立一个矩阵存储
	q.push(0);//输出当前结点
	book[0] = 1;//表示遍历过了这个点
	while (!q.empty())
	{
		cur =q.front();
		for (i = 0; i < m; i++)
		{
			if (e[cur][i] == 1 && book[i] == 0)//有边而且这个点没有被访问过的话
			{
				q.push(i);
				book[i] = 1;
			}
			if (q.size() > m) break;
		}
		cout<<cur<<' ';
		q.pop();
	}
	return 0;
}

最小生成树

题目描述

已知一个无向图G的顶点和边，顶点从0依次编号，请编程输出图G的最小生成树对应的边权之和。

输入

第一行是整数m和n（1<m,n<100），分别代表顶点数和边数。后边n行，每行3个数，分别表示一个边的两个顶点和该边的权值。

输出

最小生成树对应的边权之和。

样例输入

4 5
0 1 6
0 2 9
2 1 12
1 3 10
3 2 3

样例输出

18

#include <bits/stdc++.h>
using namespace std;
const int MAXV = 1000;
const int INF = 0x3fffffff;
int G[MAXV][MAXV];
int n;
bool vis[MAXV];
int d[MAXV];
int prim() {
	for(int i=0;i<1000;i++) d[i]=INF;
	d[0] = 0;
	int ans = 0;
	for (int i = 0; i < n;i++) {
		int u = -1, min = INF;
		for (int j = 0; j < n;j++) {
			if(vis[j] == false && d[j] < min) {
				u = j;
				min = d[j];
			}
		}
		if(u == -1) return -1;
		vis[u] = true;
		ans += d[u];
		for (int v = 0; v < n; v++) {
			if(vis[v] == false && G[u][v] != INF && G[u][v] < d[v]) d[v] = G[u][v];
		}
	}
	return ans;
}
int main() {
	int m, u, v, w;
	cin>>n>>m;
	for (int i = 0; i < n; i++) {
		for (int j =0; j < n; j++) {
			if (i == j) {
				G[i][j] = 0;
			} else {
				G[i][j] = 999999;
			}
		}
	}//初始化
	for (int i = 0; i < m; i++) {
		cin>>u>>v>>w;
		G[u][v]=w;
		G[v][u]=w;
	}//赋值
	cout<<prim();
	return 0;
}