判断完全二叉搜索树技巧

#include<bits/stdc++.h> using namespace std; const int maxn = 5e6+5; int tree[maxn], n; void add(int r, int v) {     if(tree[r]==-1)     {         tree[r]=v;         return;     }     else if(val > tree[r]) add(r*2, val);     else add(r*2+1, val); }   int main() {     while(cin >> n)     {         int t;         memset(tree,-1,sizeof(tree));         for(int i=1;i<=n;i++)         {                          cin>>t;             add(1,t);         }         int flag=1;         int r=1<<n;         for(int i=1;i<=r;i++)         {             if(i<=n&&tree[i]==-1)flag=0;             else if(tree[i]!=-1)             printf("%s%d", i==1 ? "" : " ", tree[i]);         }         printf("\n%s\n",flag? "YES":"NO");     }     return 0; }

核心思路：

首先我们用数组模拟建树，左子树建立在2*a，右子树建立在2*a+1以此完成二叉搜索树的建立。

那么根据完全二叉搜索树的特性，如果 在1-n号节点之间，每个数组都不为空，这个二叉搜索树就是完全二叉搜索树了。