PAT-團體程序設計天梯賽-練習集- L3-010 是否完全二叉搜索樹【三星級】

時間：2019-07-10 11:19:02

關鍵字： pat 二叉樹

手機看文章

掃描二維碼
隨時隨地手機看文章

[導讀]題面：L3-010. 是否完全二叉搜索樹時間限制 400 ms內(nèi)存限制 65536 kB代碼長度限制 8000 B判題程序 Standard 作者陳越將一系列給定數(shù)字順序插入一個

題面：

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

將一系列給定數(shù)字順序插入一個初始為空的二叉搜索樹（定義為左子樹鍵值大，右子樹鍵值小），你需要判斷最后的樹是否一棵完全二叉樹，并且給出其層序遍歷的結(jié)果。

輸入格式：

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

輸出格式：

將輸入的N個正整數(shù)順序插入一個初始為空的二叉搜索樹。在第一行中輸出結(jié)果樹的層序遍歷結(jié)果，數(shù)字間以1個空格分隔，行的首尾不得有多余空格。第二行輸出“YES”，如果該樹是完全二叉樹；否則輸出“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ì)量不高，編譯器還有毒。真的如很多人所說，cccc的題目質(zhì)量有待提高，形式也有待改進，題意描述不夠清晰，全靠腦洞自行補充，前面L1完全沒必要，浪費選手精力，考察知識面也太窄，弄來弄去，總是樹啊，最短路啊什么的。不能帶模板，被好多人吐槽。題目數(shù)據(jù)太水，太容易騙分，隊友錯誤的代碼，用了點技巧，滿分了。沒有數(shù)據(jù)范圍....，服務器性能太好，完全不能用acm的方式計算復雜度.....。團體的概念完全沒有體現(xiàn)，只是簡單的1+1=2，希望能向acm區(qū)域賽看齊。不過，畢竟第一屆，考察的性質(zhì)也不一樣，和近40年歷史的acm存在差距，也是可以理解的。希望，在今后的比賽中，能更加體現(xiàn)團隊意識，比如幾個選手刷高級題，幾個選手刷中級題，或者說超大題量，五六個選手瘋狂刷，看總分，而不是僅僅每個人都刷一樣的題，沒太大趣味，也不能體現(xiàn)團隊的合作意識。言歸正傳。

解題：

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

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

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

定義：

說法一：

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

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

????

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

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

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

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

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

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

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

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

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

思路：

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

代碼：

#include#include#include#include#includeusing?namespace?std;
int?tree[200],le[200],ri[200],cnt=0,path[200],p=0,idd[200];
bool?flag;
//建樹
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();
	???//是否是完全二叉樹的判斷
	???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;
}