烟台网站制作设计/精准客户截流软件

这题也太坑了，编号还有两位数的，因此测试点2 3 答案错误

思路：

1.存储结点：

用静态二叉链表数组的方式存储；

2.找根结点：

遍历，hashTable数组，没有被指向过的就是根结点；

判断完全二叉树

3.编号，从左到右、从上到下，从1开始编号。这个顺序正好符合层序遍历。

4.判断：遍历每个结点，看它的左右孩子（若存在）是否符合编号 2*i，2*i+1的规则

5.输出时的最后一个结点怎么找

在层序遍历时，最后记一下last的下标

#define _CRT_SECURE_NO_WARNINGS 1
/*** 02.25 14:12* 给出一个树，判断是否为一个完整的二叉树* 输入：* N：结点总数，结点从0编号* N行，每个结点的左右孩子，如果孩子不存在就是 -* 输出：* 如果树是一个完整的二叉树，输出YES 和 最后一个结点下标* 如果不是，输出NO 和 根结点的下标
**/
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 25; //结点的最大个数
int n; //结点个数
bool hashTable[maxn] = { false };//找根结点用，记录该结点是否被指向过
int last; //记录最后一个结点struct node {int data;int id; //该结点的编号int lchild;int rchild;
} Node[maxn]; // 存放结点的node型数组// 层序遍历，对结点进行编号（从左到右、从上到下，从1开始）
int number = 1;
void layerOrder(int root) {queue<int> q;q.push(root);while (!q.empty()) {int now = q.front();q.pop();Node[now].id = number++;if (number == n + 1)last = now;if (Node[now].lchild != -1)q.push(Node[now].lchild);if (Node[now].rchild != -1)q.push(Node[now].rchild);}
}int main() {scanf("%d", &n);getchar();// 录入结点数据for (int i = 0; i < n; i++) { //数组下标从1开始Node[i].data = i; //该节点的值char str[5];// 输入结点的左右孩子，可能2位数scanf("%s", str);if (str[0] == '-') { // 如果第一个输入的是 -Node[i].lchild = -1;}else { // 如果输入的不是-，而是数字int num;if (strlen(str) == 1) { // 如果是一位数字num = str[0] - '0';}else { // 如果是两位数字num = (str[0] - '0') * 10 + (str[1] - '0');}Node[i].lchild = num; //赋值给当前结点的左孩子hashTable[num] = true; // 说明这个结点被指向过，不可能是根结点}// 同理，录入右孩子 数据scanf("%s", str);if (str[0] == '-') {Node[i].rchild = -1;}else {int num;if (strlen(str) == 1) {num = str[0] - '0';}else {num = (str[0] - '0') * 10 + (str[1] - '0');}Node[i].rchild = num;hashTable[num] = true;}}// 找根结点int root;for (int i = 0; i < n; i++) {if (hashTable[i] == false) {root = i;break;}}// 层序遍历进行编号layerOrder(root);//遍历每个结点，看是否符合完全二叉树的条件，左孩子编号为2x，右孩子编号为2x+1bool flag = true;for (int i = 0; i < n; i++) {//判断左孩子int left = Node[i].lchild;if (left != -1) {if (Node[i].id * 2 != Node[left].id) {flag = false;break;}}// 判断右孩子int right = Node[i].rchild;if (right != -1) {if (Node[i].id * 2 + 1 != Node[right].id) {flag = false;break;}}}if (flag == true)printf("YES %d\n", last);elseprintf("NO %d\n", root);return 0;
}