本文主要是介绍【PAT】1110. Complete Binary Tree (25)【完全二叉树】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
Given a tree, you are supposed to tell if it is a complete binary tree.
翻译：给定一棵树，你需要说出它是否是一棵完全二叉树。
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤20) which is the total number of nodes in the tree – and hence the nodes are numbered from 0 to N−1. Then N lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a - will be put at the position. Any pair of children are separated by a space.
翻译：每个输入文件包含一组测试数据。对于每组测试数据，第一行包括一个正整数N(≤20) ，代表树的总结点数——假设所有节点被标记为0到N-1。接下来N行，每一行描述一个节点，给出节点左右孩子的编号。如果孩子不存在，则在该位置输出‘-‘。任何一对孩子节点之间用空格隔开。
Output Specification:
For each case, print in one line YES and the index of the last node if the tree is a complete binary tree, or NO and the index of the root if not. There must be exactly one space separating the word and the number.
翻译：对于每组输入数据，如果该树是一棵完全二叉树，输出YES和最后一个节点的编号。否则输出NO和根节点的编号。在单词和数字之间必须有一个空格。
Sample Input 1:
9
7 8
- -
- -
- -
0 1
2 3
4 5
- -
- -
Sample Output 1:
YES 8
Sample Input 2:
8
- -
4 5
0 6
- -
2 3
- 7
- -
- -
Sample Output 2:
NO 1
解题思路
首先读入数据时由于可能为’-’，所以用%s读取，然后提取出数字，不用%c的原因是可能为两位数字。然后记录每个节点的父节点，然后找出根节点。判断是否为完全二叉树的方法有很多，我的作法是将每个点重新编号，左孩子节点的编号为父节点的2倍，右孩子节点的编号为父节点的2倍+1，然后在对编号进行搜索，如果是完全二叉树则从1—N每个编号都应存在。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#define INF 99999999
using namespace std;
int N;
int a[21][2];
int f[21],troot;
int ans[21],v[21];
void Judge(int root,int vocation,int parent){ans[root]=parent*2+vocation;int lc=a[root][0],rc=a[root][1];if(lc>=0)Judge(lc,0,ans[root]);if(rc>=0)Judge(rc,1,ans[root]);
}
int main(){scanf("%d",&N);for(int i=0;i<N;i++)f[i]=-1;char l[3],r[3];for(int i=0;i<N;i++){scanf("\n%s %s",l,r);if(l[0]=='-')a[i][0]=-1;else {int tmp=0;for(int j=0;j<strlen(l);j++){tmp=tmp*10+(l[j]-'0'); }a[i][0]=tmp;f[tmp]=i;}if(r[0]=='-')a[i][1]=-1;else {int tmp=0;for(int j=0;j<strlen(r);j++){tmp=tmp*10+(r[j]-'0'); }a[i][1]=tmp;f[tmp]=i;}}for(int i=0;i<N;i++){if(f[i]==-1)troot=i;}int temp=0;Judge(troot,1,0);int i,lastNode;for(i=0;i<N;i++){if(ans[i]>N)continue;else if(!v[ans[i]])v[ans[i]]=1;if(ans[i]==N)lastNode=i;}for(i=1;i<=N;i++){if(!v[i])break;}if(i==N+1)printf("YES %d\n",lastNode);else printf("NO %d\n",troot);return 0;
}这篇关于【PAT】1110. Complete Binary Tree (25)【完全二叉树】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
