題面：

L3-010. 是否完全二叉搜索樹(shù) 時(shí)間限制 400 ms
內(nèi)存限制 65536 kB
代碼長(zhǎng)度限制 8000 B
判題程序 Standard 作者 陳越

將一系列給定數(shù)字順序插入一個(gè)初始為空的二叉搜索樹(shù)（定義為左子樹(shù)鍵值大，右子樹(shù)鍵值?。阈枰袛嘧詈蟮臉?shù)是否一棵完全二叉樹(shù)，并且給出其層序遍歷的結(jié)果。

輸入格式：

輸入第一行給出一個(gè)不超過(guò)20的正整數(shù)N；第二行給出N個(gè)互不相同的正整數(shù)，其間以空格分隔。

輸出格式：

將輸入的N個(gè)正整數(shù)順序插入一個(gè)初始為空的二叉搜索樹(shù)。在第一行中輸出結(jié)果樹(shù)的層序遍歷結(jié)果，數(shù)字間以1個(gè)空格分隔，行的首尾不得有多余空格。第二行輸出“YES”，如果該樹(shù)是完全二叉樹(shù)；否則輸出“NO”。

輸入樣例1：

9
38?45?42?24?58?30?67?12?51

輸出樣例1：

38?45?24?58?42?30?12?67?51
YES

輸入樣例2：

8
38?24?12?45?58?67?42?51

輸出樣例2：

38?45?24?58?42?12?67?51
NO

總結(jié)：

??? cccc不堪回首，自己渣，發(fā)揮又不好，題目質(zhì)量不高，編譯器還有毒。真的如很多人所說(shuō)，cccc的題目質(zhì)量有待提高，形式也有待改進(jìn)，題意描述不夠清晰，全靠腦洞自行補(bǔ)充，前面L1完全沒(méi)必要，浪費(fèi)選手精力，考察知識(shí)面也太窄，弄來(lái)弄去，總是樹(shù)啊，最短路啊什么的。不能帶模板，被好多人吐槽。題目數(shù)據(jù)太水，太容易騙分，隊(duì)友錯(cuò)誤的代碼，用了點(diǎn)技巧，滿分了。沒(méi)有數(shù)據(jù)范圍....，服務(wù)器性能太好，完全不能用acm的方式計(jì)算復(fù)雜度.....。團(tuán)體的概念完全沒(méi)有體現(xiàn)，只是簡(jiǎn)單的1+1=2，希望能向acm區(qū)域賽看齊。不過(guò)，畢竟第一屆，考察的性質(zhì)也不一樣，和近40年歷史的acm存在差距，也是可以理解的。希望，在今后的比賽中，能更加體現(xiàn)團(tuán)隊(duì)意識(shí)，比如幾個(gè)選手刷高級(jí)題，幾個(gè)選手刷中級(jí)題，或者說(shuō)超大題量，五六個(gè)選手瘋狂刷，看總分，而不是僅僅每個(gè)人都刷一樣的題，沒(méi)太大趣味，也不能體現(xiàn)團(tuán)隊(duì)的合作意識(shí)。言歸正傳。

解題：

???? 問(wèn)給定的一棵樹(shù)，按層序遍歷輸出節(jié)點(diǎn)的值，并且判斷是不是完全二叉樹(shù)。

???? 不記得完全二叉樹(shù)的定義了，比賽的時(shí)候沒(méi)多想，畫了畫樣例，以為是某個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)為1，則不是完全二叉樹(shù)，其實(shí)，國(guó)內(nèi)外完全二叉樹(shù)的定義也是各異的，題目應(yīng)該給出詳盡的解釋，而不是讓選手去猜。

???? 前一天熬夜了，傻乎乎的，子節(jié)點(diǎn)數(shù)為0，我寫了個(gè)return.....怎么查都沒(méi)查出來(lái)，浪費(fèi)了三四十分鐘，造成后面全盤崩....

定義：

說(shuō)法一：

????? 《算法導(dǎo)論》第3版P690有定義如下：
?????? 滿二叉樹(shù)：每個(gè)節(jié)點(diǎn)是葉節(jié)點(diǎn)或者度為2.
?????? 完全二叉樹(shù)：所有葉節(jié)點(diǎn)深度相同，且所有內(nèi)部節(jié)點(diǎn)度為2. （樹(shù)的節(jié)點(diǎn)總數(shù)達(dá)到最大）

說(shuō)法二：【本題采用的是這種定義】

????

1.根二叉樹(shù)(Rooted Binary Tree)：
有一個(gè)根結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)至多有兩個(gè)孩子。
2.滿二叉樹(shù)(Full Binary Tree)：
要么是葉子結(jié)點(diǎn)(結(jié)點(diǎn)的度為0)，要么結(jié)點(diǎn)同時(shí)具有左右子樹(shù)(結(jié)點(diǎn)的度為2)。
3.完全二叉樹(shù)(Complete Binary Tree)：
每層結(jié)點(diǎn)都完全填滿，在最后一層上如果不是滿的，則只缺少右邊的若干結(jié)點(diǎn)。
4.完美二叉樹(shù)(Perfect Binary Tree)
所有的非葉子結(jié)點(diǎn)都有兩個(gè)孩子，所有的葉子結(jié)點(diǎn)都在同一層。即每層結(jié)點(diǎn)都完全填滿。
5.無(wú)限完全二叉樹(shù)(Infinite Complete Binary Tree)：
每個(gè)結(jié)點(diǎn)都有兩個(gè)孩子，結(jié)點(diǎn)的層數(shù)是無(wú)限的。
6.平衡二叉樹(shù)(Balanced Binary Tree)：
也稱為AVL樹(shù)，它是一棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。

作者：灰杉樹(shù)
鏈接：http://www.zhihu.com/question/19809666/answer/88158084
來(lái)源：知乎
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。 1.根二叉樹(shù)(Rooted Binary Tree)：
有一個(gè)根結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)至多有兩個(gè)孩子。
2.滿二叉樹(shù)(Full Binary Tree)：
要么是葉子結(jié)點(diǎn)(結(jié)點(diǎn)的度為0)，要么結(jié)點(diǎn)同時(shí)具有左右子樹(shù)(結(jié)點(diǎn)的度為2)。
3.完全二叉樹(shù)(Complete Binary Tree)：
每層結(jié)點(diǎn)都完全填滿，在最后一層上如果不是滿的，則只缺少右邊的若干結(jié)點(diǎn)。
4.完美二叉樹(shù)(Perfect Binary Tree)
所有的非葉子結(jié)點(diǎn)都有兩個(gè)孩子，所有的葉子結(jié)點(diǎn)都在同一層。即每層結(jié)點(diǎn)都完全填滿。
5.無(wú)限完全二叉樹(shù)(Infinite Complete Binary Tree)：
每個(gè)結(jié)點(diǎn)都有兩個(gè)孩子，結(jié)點(diǎn)的層數(shù)是無(wú)限的。
6.平衡二叉樹(shù)(Balanced Binary Tree)：
也稱為AVL樹(shù)，它是一棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。

作者：灰杉樹(shù)
來(lái)源：知乎
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。 1.根二叉樹(shù)(Rooted Binary Tree)：
有一個(gè)根結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)至多有兩個(gè)孩子。
2.滿二叉樹(shù)(Full Binary Tree)：
要么是葉子結(jié)點(diǎn)(結(jié)點(diǎn)的度為0)，要么結(jié)點(diǎn)同時(shí)具有左右子樹(shù)(結(jié)點(diǎn)的度為2)。
3.完全二叉樹(shù)(Complete Binary Tree)：
每層結(jié)點(diǎn)都完全填滿，在最后一層上如果不是滿的，則只缺少右邊的若干結(jié)點(diǎn)。
4.完美二叉樹(shù)(Perfect Binary Tree)
所有的非葉子結(jié)點(diǎn)都有兩個(gè)孩子，所有的葉子結(jié)點(diǎn)都在同一層。即每層結(jié)點(diǎn)都完全填滿。
5.無(wú)限完全二叉樹(shù)(Infinite Complete Binary Tree)：
每個(gè)結(jié)點(diǎn)都有兩個(gè)孩子，結(jié)點(diǎn)的層數(shù)是無(wú)限的。
6.平衡二叉樹(shù)(Balanced Binary Tree)：
也稱為AVL樹(shù)，它是一棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。

作者：灰杉樹(shù)
來(lái)源：知乎
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。 1.根二叉樹(shù)(Rooted Binary Tree)：
有一個(gè)根結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)至多有兩個(gè)孩子。
2.滿二叉樹(shù)(Full Binary Tree)：
要么是葉子結(jié)點(diǎn)(結(jié)點(diǎn)的度為0)，要么結(jié)點(diǎn)同時(shí)具有左右子樹(shù)(結(jié)點(diǎn)的度為2)。
3.完全二叉樹(shù)(Complete Binary Tree)：
每層結(jié)點(diǎn)都完全填滿，在最后一層上如果不是滿的，則只缺少右邊的若干結(jié)點(diǎn)。
4.完美二叉樹(shù)(Perfect Binary Tree)
所有的非葉子結(jié)點(diǎn)都有兩個(gè)孩子，所有的葉子結(jié)點(diǎn)都在同一層。即每層結(jié)點(diǎn)都完全填滿。
5.無(wú)限完全二叉樹(shù)(Infinite Complete Binary Tree)：
每個(gè)結(jié)點(diǎn)都有兩個(gè)孩子，結(jié)點(diǎn)的層數(shù)是無(wú)限的。
6.平衡二叉樹(shù)(Balanced Binary Tree)：
也稱為AVL樹(shù)，它是一棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。

作者：灰杉樹(shù)
來(lái)源：知乎
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。 1.根二叉樹(shù)(Rooted Binary Tree)：
有一個(gè)根結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)至多有兩個(gè)孩子。
2.滿二叉樹(shù)(Full Binary Tree)：
要么是葉子結(jié)點(diǎn)(結(jié)點(diǎn)的度為0)，要么結(jié)點(diǎn)同時(shí)具有左右子樹(shù)(結(jié)點(diǎn)的度為2)。
3.完全二叉樹(shù)(Complete Binary Tree)：
每層結(jié)點(diǎn)都完全填滿，在最后一層上如果不是滿的，則只缺少右邊的若干結(jié)點(diǎn)。
4.完美二叉樹(shù)(Perfect Binary Tree)
所有的非葉子結(jié)點(diǎn)都有兩個(gè)孩子，所有的葉子結(jié)點(diǎn)都在同一層。即每層結(jié)點(diǎn)都完全填滿。
5.無(wú)限完全二叉樹(shù)(Infinite Complete Binary Tree)：
每個(gè)結(jié)點(diǎn)都有兩個(gè)孩子，結(jié)點(diǎn)的層數(shù)是無(wú)限的。
6.平衡二叉樹(shù)(Balanced Binary Tree)：
也稱為AVL樹(shù)，它是一棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。

作者：灰杉樹(shù)
來(lái)源：知乎
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。 1.根二叉樹(shù)(Rooted Binary Tree)：
有一個(gè)根結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)至多有兩個(gè)孩子。
2.滿二叉樹(shù)(Full Binary Tree)：
要么是葉子結(jié)點(diǎn)(結(jié)點(diǎn)的度為0)，要么結(jié)點(diǎn)同時(shí)具有左右子樹(shù)(結(jié)點(diǎn)的度為2)。
3.完全二叉樹(shù)(Complete Binary Tree)：
每層結(jié)點(diǎn)都完全填滿，在最后一層上如果不是滿的，則只缺少右邊的若干結(jié)點(diǎn)。
4.完美二叉樹(shù)(Perfect Binary Tree)
所有的非葉子結(jié)點(diǎn)都有兩個(gè)孩子，所有的葉子結(jié)點(diǎn)都在同一層。即每層結(jié)點(diǎn)都完全填滿。
5.無(wú)限完全二叉樹(shù)(Infinite Complete Binary Tree)：
每個(gè)結(jié)點(diǎn)都有兩個(gè)孩子，結(jié)點(diǎn)的層數(shù)是無(wú)限的。
6.平衡二叉樹(shù)(Balanced Binary Tree)：
也稱為AVL樹(shù)，它是一棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。

作者：灰杉樹(shù)
來(lái)源：知乎
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。 1.根二叉樹(shù)(Rooted Binary Tree)：
有一個(gè)根結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)至多有兩個(gè)孩子。
2.滿二叉樹(shù)(Full Binary Tree)：
要么是葉子結(jié)點(diǎn)(結(jié)點(diǎn)的度為0)，要么結(jié)點(diǎn)同時(shí)具有左右子樹(shù)(結(jié)點(diǎn)的度為2)。
3.完全二叉樹(shù)(Complete Binary Tree)：
每層結(jié)點(diǎn)都完全填滿，在最后一層上如果不是滿的，則只缺少右邊的若干結(jié)點(diǎn)。
4.完美二叉樹(shù)(Perfect Binary Tree)
所有的非葉子結(jié)點(diǎn)都有兩個(gè)孩子，所有的葉子結(jié)點(diǎn)都在同一層。即每層結(jié)點(diǎn)都完全填滿。
5.無(wú)限完全二叉樹(shù)(Infinite Complete Binary Tree)：
每個(gè)結(jié)點(diǎn)都有兩個(gè)孩子，結(jié)點(diǎn)的層數(shù)是無(wú)限的。
6.平衡二叉樹(shù)(Balanced Binary Tree)：
也稱為AVL樹(shù)，它是一棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。

作者：灰杉樹(shù)
來(lái)源：知乎
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。 1.根二叉樹(shù)(Rooted Binary Tree)：
有一個(gè)根結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)至多有兩個(gè)孩子。
2.滿二叉樹(shù)(Full Binary Tree)：
要么是葉子結(jié)點(diǎn)(結(jié)點(diǎn)的度為0)，要么結(jié)點(diǎn)同時(shí)具有左右子樹(shù)(結(jié)點(diǎn)的度為2)。
3.完全二叉樹(shù)(Complete Binary Tree)：
每層結(jié)點(diǎn)都完全填滿，在最后一層上如果不是滿的，則只缺少右邊的若干結(jié)點(diǎn)。
4.完美二叉樹(shù)(Perfect Binary Tree)
所有的非葉子結(jié)點(diǎn)都有兩個(gè)孩子，所有的葉子結(jié)點(diǎn)都在同一層。即每層結(jié)點(diǎn)都完全填滿。
5.無(wú)限完全二叉樹(shù)(Infinite Complete Binary Tree)：
每個(gè)結(jié)點(diǎn)都有兩個(gè)孩子，結(jié)點(diǎn)的層數(shù)是無(wú)限的。
6.平衡二叉樹(shù)(Balanced Binary Tree)：
也稱為AVL樹(shù)，它是一棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。


作者：灰杉樹(shù)
來(lái)源：知乎
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。 滿二叉樹(shù)通俗理解如下：一個(gè)結(jié)點(diǎn)要么是葉結(jié)點(diǎn)，要么是有兩個(gè)子結(jié)點(diǎn)的中間結(jié)點(diǎn)。
???? 完全二叉樹(shù)通俗理解如下：從根結(jié)點(diǎn)開(kāi)始，依次從左到右填充樹(shù)結(jié)點(diǎn)。由此可見(jiàn)，滿二叉樹(shù)和完全二叉樹(shù)沒(méi)有特別的關(guān)系。

思路：

???? 按照，插入值和當(dāng)前位置值的關(guān)系，建立二叉樹(shù)，設(shè)置初始值為0，代表某節(jié)點(diǎn)為空，并同時(shí)給該點(diǎn)分配完全二叉樹(shù)下應(yīng)該為的id，用于后續(xù)判斷是否是完全二叉樹(shù)。用bfs遍歷，并用其現(xiàn)有id和應(yīng)為id比較，若不符，則不是完全二叉樹(shù)。

代碼：

#include#include#include#include#includeusing?namespace?std;
int?tree[200],le[200],ri[200],cnt=0,path[200],p=0,idd[200];
bool?flag;
//建樹(shù)
void?insert(int?x,int?v,int?id)
{
????if(tree[x]==0)
	{
		tree[x]=v;
		idd[x]=id;
		cnt++;
	}
	else
	{
		if(v>tree[x])
		{
			if(le[x]==0)
			??le[x]=cnt+1;
			insert(le[x],v,id*2);
		}
		else
		{
???????????if(ri[x]==0)
			???ri[x]=cnt+1;
		???insert(ri[x],v,id*2+1);
		}
	}
}
//層序遍歷
void?solve()
{
	int?cur;
	queueqe;
	qe.push(0);
	while(!qe.empty())
	{
???????cur=qe.front();
	???qe.pop();
	???//是否是完全二叉樹(shù)的判斷
	???if(p+1<idd[cur])
		???flag=0;
	???path[p++]=tree[cur];
	???if(le[cur]&&ri[cur])
	???{
		???qe.push(le[cur]);
		???qe.push(ri[cur]);
	???}
	???else?if(le[cur]||ri[cur])
	???{
		???if(le[cur])
		?????qe.push(le[cur]);
???????????else
			?qe.push(ri[cur]);
	???}
	}
}
int?main()
{
	int?n,tmp;
	scanf("%d",&n);
????for(int?i=1;i<=n;i++)
	{
		scanf("%d",&tmp);
		insert(0,tmp,1);
	}
	flag=1;
	solve();
	printf("%d",path[0]);
	for(int?i=1;i<p;i++)
	{
		printf("?%d",path[i]);
	}
	printf("n");
	if(flag)
		printf("YESn");
	else
		printf("NOn");
	return?0;
}