pat 1110. Complete Binary Tree (25)
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.
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.
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
두 갈래 나무가 완전 두 갈래 나무인지 아닌지 판단하기:
층차적으로 훑어볼 때 방문한 결점의 수를 기록하고 이 결점이 아이의 결점이 없을 때 훑어보는 것을 끝내고 방문한 노드의 수가 n이 아닐 때 완전한 두 갈래 나무가 아니다.
주의: n<20, 10보다 작은 것이 아니라 문자를 숫자로 바꿔야 합니다.
#include
#include
#include
using namespace std;
#include
#include
#include
#define MS(a,b) memset(a,b,sizeof(a))
int last,n,cnt;
vectorv;
struct node
{
int left,right,fa;
}tree[200];
void bfs(int root)
{
int rt;
queueq;
q.push(root);
while(!q.empty())
{
rt=q.front();
q.pop();
if(rt!=-1)
{
last=rt;// 。
cnt++;// 。
}
if(rt==-1)break;
q.push(tree[rt].left);
q.push(tree[rt].right);
}
}
int main()
{
/*#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif*/
int i;
char s1[5],s2[5];
scanf("%d",&n);
for(i=0;i>s1>>s2;
if(s1[0]!='-')
{ sscanf(s1,"%d",&tree[i].left);// 。
tree[tree[i].left].fa=i;
}
else tree[i].left=-1;
if(s2[0]!='-')
{ sscanf(s2,"%d",&tree[i].right);
tree[tree[i].right].fa=i;
}
else tree[i].right=-1;
}
int root=-1;
for(i=0;i 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
java 데이터 구조 2차원 트리의 실현 코드일.두 갈래 트리 인터페이스 2 노드 클래스 3. 두 갈래 나무 구현 이 글을 통해 여러분께 도움이 되었으면 좋겠습니다. 본 사이트에 대한 지지에 감사드립니다!...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
