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.
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:
|
1 2 3 4 5 6 7 8 9 10 |
9 7 8 - - - - - - 0 1 2 3 4 5 - - - - |
Sample Output 1:
|
1 |
YES 8 |
Sample Input 2:
|
1 2 3 4 5 6 7 8 9 |
8 - - 4 5 0 6 - - 2 3 - 7 - - - - |
Sample Output 2:
|
1 |
NO 1 |
仿效了二项堆的存储方式来存储 Complete Binary Tree ，这样就可以很方便的判断是否是一颗 Complete Binary Tree 以及确定最后一个节点是什么……
代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
#include<stdio.h> #include<stdlib.h> int count[21],cbt[21]; typedef struct tree_ { int left; int right; } tree; int main() { tree node[21]; int n,i,left,right,root,temp,parent,child,stack[20],top=-1; char buf[6]; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%s",buf); cbt[i]=-1; if(buf[0]=='-') { node[i].left=-1; } else { sscanf(buf,"%d",&(node[i].left)); node[i].left++; count[node[i].left]=1; } scanf("%s",buf); if(buf[0]=='-') { node[i].right=-1; } else { sscanf(buf,"%d",&(node[i].right)); node[i].right++; count[node[i].right]=1; } } for(i=1;i<=n;i++) { if(count[i]==0) { root=i; break; } } parent=1; cbt[parent]=root; stack[++top]=parent; while(top>=0) { parent=stack[top--]; temp=cbt[parent]; child=2*parent; if(child<=n&&node[temp].left!=-1) { cbt[child]=node[temp].left; stack[++top]=child; } if(child+1<=n&&node[temp].right!=-1) { cbt[child+1]=node[temp].right; stack[++top]=child+1; } } for(i=1;i<=n;i++) { if(cbt[i]<=0) { printf("NO %d\n",root-1); return 0; } } printf("YES %d\n",cbt[n]-1); } |