第五章学习小结

#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<string.h>
#include<queue>
using namespace std;

typedef struct {
	int doors;//门的数量
	int *p;//p指向具体们的编号，把p看作一个整型数组
}node;

int input(node*&a) {
	int n, i;
	bool *vi = NULL;//定义布尔数组
	cin >> n;
	a = new node[n+1];//创建a结构体数组
	vi = new bool[n + 1];//定义一个布尔类型的数组
	for (int i = 1; i <= n; i++) {//将vi数组初始化为false
		vi[i] = false;
	}

	for (int i = 1; i <= n; i++) {
		cin >> a[i].doors;
		a[i].p = new int[a[i].doors];//为数组申请空间
		for (int j = 0; j <a[i].doors;j++) {
			cin >> a[i].p[j];
			vi[a[i].p[j]] = true;//若门存在，则置1
		}
	}
	//找出根在i数组的下标
	for (i = 1; i <= n; i++) {
		if (!vi[i]) break;
	}
	return i;
}

int find(node*a, int root) {
	//从a数组的下标往下搜索
	queue<int> q;//定义用于存放带访问的门编号和队列
	int x, i;
	//根编号入队
	q.push(root);
	//当队列不为空 出队一个元素，x->出队

	while (!q.empty()) {
		x = q.front();//取队头元素
		q.pop();//队头元素出队
		for (i = 0; i < a[x].doors; i++) {
			q.push(a[x].p[i]);
		}
	}
	return x;
}

int main()
{
	//变量的定义
	node*a;//定义一个动态的整型数组
	int root;//定义辅助变量以及root
	root = input(a);
	cout << find(a, root) << endl;//输出答案
	system("pause");
	return 0;
}

#include<iostream>
#include<queue>
using namespace std;

typedef struct {
	int name;
	int lch;
	int rch;
}node;

int BulidTree(node t[]);
void levelOrderTraverse(node t[], int x); //层次遍历 

int main()
{
	node t[100];
	int x;
	x = BulidTree(t);//建立二叉树
	levelOrderTraverse(t, x);//层次遍历二叉树
	system("pause");
	return 0;
}

int BulidTree(node t[])
{//建立二叉树的函数
	bool check[100] = { false };//置零
	int n;
	char x, y;
	cin >> n;
	for (int i = 0; i < n; i++) {//循环输入x,y
		t[i].name = i;
		cin >> x >> y;
		if (x != ‘-‘) {//
			t[i].lch = x - ‘0‘;
			check[t[i].lch] = true;
		}
		else
			t[i].lch = -1;
		if (y != ‘-‘) {
			t[i].rch = y - ‘0‘;
			check[t[i].rch] = true;
		}
		else
			t[i].rch = -1;
	}
	for (int i = 0; i < n; i++) {
		if (!check[i]) return i;
	}
}


void levelOrderTraverse(node t[], int x)
{//层次遍历t[x]为根结点的树t
	int tmp;
	queue<int> q;
	q.push(x); //根结点所在下标入栈 
	int che = 0;
	while (!q.empty()) {
		tmp = q.front();
		q.pop();
		if (tmp != -1) {
			if (t[tmp].lch == -1 && t[tmp].rch == -1) {
				if (che == 0) {
					cout << t[tmp].name;
					che = 1;
				}
				else cout << " " << t[tmp].name;
			}
			q.push(t[tmp].lch);
			q.push(t[tmp].rch);
		}
	}
}