绘制一颗折半查找判定树

编译器: std=c++14 or higher；环境：Mac OS X (M1 Core)；
通过define UPPERBOUND和LOWERBOUND可以绘制向上取整、向下取整的判定树。
和王道所讲的规律是一致的；
2017的真题，或者用这个性质去做，或者根据判定树的构造方法去做，即，先标好中序遍历的次序，然后去看每次生成的新节点是不是都遵循相同的生成规则。

#include 
#include 
using namespace std;
#define UPPERBOUND
const int N = 1005;int lchild[N], rchild[N];int draw(int l, int r) {if (l > r) return -1;if (l == r) return l;#ifdef UPPERBOUNDint mid = (l + r + 1) >> 1;#endif#ifdef LOWERBOUNDint mid = (l + r) >> 1;#endifint L = draw(l, mid - 1), R = draw(mid + 1, r);if (L != -1)lchild[mid + 1] = L + 1;if (R != -1)rchild[mid + 1] = R + 1;//printf("%d, %d, %d\n", L + 1, mid + 1, R + 1);return mid;
}vector<pair<int, int>> ret;int dfs(int u, int depth, int ind) {int p = 0;if (lchild[u]) {p = max(p, dfs(lchild[u], depth + 1, ind * 2 - 1));} else {ret.push_back({depth + 1, ind * 2 - 1});}if (rchild[u]) {p = max(p, dfs(rchild[u], depth + 1, ind * 2));} else {ret.push_back({depth + 1, ind * 2});}//cout << u << ' ' << p << endl;return p + 1;
}typedef short unsigned int hu;
enum { M = 10 };//中间这一段输出是抄的洛谷输出二叉树的题解int k,n,m,p,x,y;
char c[800][1600];
bool f[800][1600];//在第x,y点,a,b是用来判节点的,k表示点还是边，xx,yy表示这个点或这个边的父亲void dfs1(int x,int y,int a,int b,int k,int xx,int yy){if(x==n){c[x][y]='o';return;}if(k==1){c[x][y]='o';int X=xx+1,Y=(yy-1)*2+1;//左儿子if(!f[X][Y])dfs1(x+1,y-1,a+1,b,2,X,Y);X=xx+1,Y=yy*2;//又儿子if(!f[X][Y])dfs1(x+1,y+1,a+1,b,3,X,Y);}elseif(k==2){c[x][y]='/';if(a*2==b)dfs1(x+1,y-1,1,a,1,xx,yy);//这个就是判断接下来是边还是点else    dfs1(x+1,y-1,a+1,b,2,xx,yy);}elseif(k==3){c[x][y]=92;if(a*2==b)dfs1(x+1,y+1,1,a,1,xx,yy);else    dfs1(x+1,y+1,a+1,b,3,xx,yy);}
}
void make(int k){n=3;for(int i=3;i<=k;i++)n*=2;m=6*(1<<(k-2))-1;//计算画布大小for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)c[i][j]=' ';//填充画布dfs1(1,m/2+1,1,n,1,1,1);
}void toTerminal(vector<pair<int, int>> got) {memset(f, 0, sizeof f);memset(c, 0, sizeof c);for (int i = 0; i < p; i ++) {int x = got[i].first, y = got[i].second;f[x][y] = 1;}if(k==1)n=m=1,c[1][1]='o';else make(k);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)cout<<c[i][j];cout<<endl;}
}int main() {for (int i = 1; i < 50; i ++) {memset(lchild, 0, sizeof lchild);memset(rchild, 0, sizeof rchild);int root = draw(0, i - 1) + 1;ret.clear();int depth = dfs(root, 1, 1);int ans = 0;for (auto [a, b]: ret) {if (a <= depth)ans ++;}k = depth, p = ans;vector<pair<int, int>> gotcha;for (auto [a, b]: ret) {if (a > depth)continue;gotcha.push_back({a, b});}printf("Case %d:: \n", i);toTerminal(gotcha);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！