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

輸入格式：

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

輸出格式：

將輸入的N個正整數順序插入一個初始為空的二叉搜索樹。在第一行中輸出結果樹的層序遍歷結果，數字間以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

題意是輸入一個n，再輸入n個數，輸出按這個序列插入一個左大右小的BST，試著去判斷這個bst是不是一顆完全的bst，符不符合完全樹的定義，再輸出層序遍歷序列

如何判斷一棵樹是否是完全二叉樹？我們從條件入手

1 完全二叉樹倒數第二層以上包括倒數第二層全滿。

2 最后一層的最后一個節點左邊全滿

于是我們不妨先把最大層數找出來，然后用搜索帶個層數的參數，每次搜索判斷如果這一層不是最后一層而少點 那么就不是完全二叉樹? 滿足第一點的判斷

我們按照先右后左的順序搜索，如果走到最后一層的第一個點一定是最右點 標記一下 再走到后面的這一層的節點時如果不存在 就不是完全二叉樹 滿足第二點判斷

如果剛才兩點都沒問題 就符合完全二叉樹。

code:

#include<bits/stdc++.h> using namespace std; typedef struct bst {int d;bst *l,*r; }NN,*NNN; int flo; NNN insert(NNN p,int t,int lev) {if(p){if(t > p->d)p->l = insert(p->l,t,lev+1);else p->r=insert(p->r,t,lev+1);return p;}else{NNN q = (NNN)malloc(sizeof(NN));// cout<<t<<endl;q->d=t;q->l=q->r=NULL;flo = max(flo,lev);return q; } } bool flag; bool judge1(NNN p,int lev) {if(p){if(lev == flo)flag=1;bool a,b;a = judge1(p->r,lev+1);b = judge1(p->l,lev+1);return a&b;}else if(lev<=flo-1||(lev==flo&&flag))return 0;else return 1; } void levelTre(NNN p) {queue<NNN>q;q.push(p);while(q.size()){NNN a = q.front();q.pop();printf("%d",a->d);if(a->l)q.push(a->l);if(a->r)q.push(a->r);if(q.size())printf(" ");else puts("");} } int main() {int n;cin>>n;NNN p = NULL;for(int i=1;i<=n;i++){int t;scanf("%d",&t);p=insert(p,t,1);} // cout<<flo<<endl;levelTre(p);bool res = judge1(p,1);if(res)puts("YES");else puts("NO");return 0; }

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的天梯赛-是否完全二叉搜索树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。