首页 > 代码库 > hdu3791静态链表解二叉搜索树
hdu3791静态链表解二叉搜索树
查看原题
题意
先给你一个数字n,接着是一串数字,你把它顺序扫描后建立一棵二叉搜索树。然后再陆续给你n串数字,判断它们尽力的二叉树和第一个二叉树是否相同。
题目保证给出的字符串长度不大于10.每个数字在0~9之间。且给出的数字不会有重复。
分析
很明显,这是一个数据结构的题目,很容易想到的就是直接自定义个二叉树结点的结构来做了。但是我感觉那样好麻烦,题目已经给出了数字长度不会大于10.所以直接用静态的链表也就是数组来解就可以了。要是数字的个数太多就不能这样做了。来看二叉树中结点与数组下标的对应关系。
注意!上图中结点中的数字并不代表结点的值,而是代表与保存结点值的数组的下标之间的对应关系。
- 假设用于存储的数组为node。那么根节点保存在node[0],而左儿子保存在node[1],右儿子保存在node[2]。
- 可知父节点与子节点之间的换算关系是这样的:若父节点为 i ,那么左儿子为(i+1)*2-1,右儿子为(i+1)*2。
- 所以我们要做的就是分别用两个int数组来保存前后两个字符串建立的二叉树。然后去比较这两个数组是否相等就可以了。
- 那么我们的node数组需要多大呢?10?9?错错错。这里要考虑所有可能的结点插入情况。其中最极端一种就是有9个结点,但是全部是右子树,这是最浪费空间的情况。此时树的深度是9。考虑深度为9的满二叉树的结点个数:2^9-1。只要大于这个数字就好了。
代码
#include <iostream> using namespace std; #include <cstring> #define MAX 512 int node[MAX]; int node2[MAX]; void makeTree(char *str,int *node) { for(int i=0;str[i]!=‘\0‘;i++) { int j=0; int t=str[i]-‘0‘; while(node[j]!=-1) { if(t>node[j]) j=(j+1)*2; if(t<node[j]) j=(j+1)*2-1; } node[j]=t; } } void compare() { for(int i=0;i<MAX;i++) if(node[i]!=node2[i]) { cout<<"NO"<<endl; return; } cout<<"YES"<<endl; } int main() { int n; char str[12],str2[12]; cin>>n; if(!n) return 0; memset(node,-1,sizeof(node)); cin>>str; makeTree(str,node); int len=strlen(str); while(n--) { memset(node2,-1,sizeof(node2)); cin>>str2; int len2=strlen(str2); if(len!=len2) { cout<<"NO"<<endl; continue; } makeTree(str2,node2); compare(); } main(); return 0; }
PS:
这里因为n有多个,一般的main函数章写法就是while(cin>>n){ }了,但是我不想套这么大的一个花括号,于是就写了个递归调用main()。哈哈O(∩_∩)O~
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。