1110 Complete Binary Tree (25 分) 判断是否为一棵完全二叉树

缺乏、安全感 2024-04-17 21:28 63阅读 0赞

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: ###

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个结点，第i行就是第i个结点的左右子节点，若无则用-表示。

问该树是否为完全二叉树，若是则输出yes和最后一个节点，若否则输出no和根节点。

**思路：**结构体存树，输入时存入左右子树，用queue做层次遍历，当层次遍历到的结点不等于n时代表非完全二叉树。

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<vector>
    #include<queue>
    #include<map>
    #include<string>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    struct sb
    {
    	int l,r;
    }t[105];
    int main()
    {
    	int n,i,u;
    	map<int,int> ma;
    	char x[105],y[105];
    	scanf("%d",&n);
    	for(i=0;i<n;i++)
    	{
    		scanf("%s %s",x,y);
    		if(x[0]=='-')
    		t[i].l=-1;
    		else
    		{
    			sscanf(x,"%d",&u);
    			t[i].l=u;
    			ma[u]=1;
    		}
    		if(y[0]=='-')
    		t[i].r=-1;
    		else
    		{
    			sscanf(y,"%d",&u);
    			t[i].r=u;
    			ma[u]=1;
    		}
    	}
    	//find root
    	int root=-1;
    	for(i=0;i<n;i++)
    	{
    		if(ma[i]==0)
    		{
    			root=i;
    			break;
    		}
    	}
    	int lastnode=0,cnt=0;
    	queue<int> q;
    	q.push(root);
    	while(!q.empty())
    	{
    		int temp=q.front();
    		q.pop();
    		if(temp!=-1)
    		{
    			lastnode=temp;
    			cnt++;
    		}
    		else
    		{
    			if(cnt!=n)
    			printf("NO %d\n",root);
    			else
    			printf("YES %d\n",lastnode);
    			
    			break;
    		}
    		q.push(t[temp].l);
    		q.push(t[temp].r);		
    	}
    }