如何预测protein sequences# Biology - 生物学
h*g
1 楼
7
/ \
8 9
\ / \
5 4 6
inorder: 857496
BFS: 789645
如何 重构这个二叉树，然后求树的宽度（哪一层node最多？）
/ \
8 9
\ / \
5 4 6
inorder: 857496
BFS: 789645
如何 重构这个二叉树，然后求树的宽度（哪一层node最多？）
c*y
2 楼
low coverage genome assembly,想预测蛋白编码序列，有哪些工具可以用？因为是low
coverage, 序列肯定有错误，所以想找具有纠错功能的蛋白翻译工具
多谢了
coverage, 序列肯定有错误，所以想找具有纠错功能的蛋白翻译工具
多谢了
l*1
3 楼
写了个练手，求牛人指正
public static TreeNode rebuild(int[] inorder,int[] bfs,int bfsl,int bfsh,int
inorderl, inorderh){
//base case
if(bsfl>=bfsh||inorderl>inorderh) return null;
TreeNode root=new TreeNode();
root.value=bfs[bfsl];
//find the index of root value in inorder array
int cutoff=findCut(inorder,inorderl,inorderh,bfs[bfsl]);
//build the tree recursively
root.right=rebuild(inorder,bfs,bfsl+1,bfsh,inorderl,cutoff-1);
root.left=rebuild(inorder,bfs,bfsl+2,bfsh,cutoff+1,inorderh);
return root;
}
public static int findCut(int[] array, int l, int h, int x){
for(int i=0;i<=h,i++){
if(array[i]==x)
return i;
}
return -1;
}
//API call
//rebuild(inorder,bfs,0,bfs.length,0,inorder.length-1);
public static TreeNode rebuild(int[] inorder,int[] bfs,int bfsl,int bfsh,int
inorderl, inorderh){
//base case
if(bsfl>=bfsh||inorderl>inorderh) return null;
TreeNode root=new TreeNode();
root.value=bfs[bfsl];
//find the index of root value in inorder array
int cutoff=findCut(inorder,inorderl,inorderh,bfs[bfsl]);
//build the tree recursively
root.right=rebuild(inorder,bfs,bfsl+1,bfsh,inorderl,cutoff-1);
root.left=rebuild(inorder,bfs,bfsl+2,bfsh,cutoff+1,inorderh);
return root;
}
public static int findCut(int[] array, int l, int h, int x){
for(int i=0;i<=h,i++){
if(array[i]==x)
return i;
}
return -1;
}
//API call
//rebuild(inorder,bfs,0,bfs.length,0,inorder.length-1);
s*n
4 楼
楼上完全错误，不能用root分两段，这办法只适合preorder+inorder
l*1
5 楼
请问为什么不能用root分两段？inorder不是所有左子树全在左边，右子树全在右边么
？
？
s*n
6 楼
BFS没法一刀切割成左右树
【在 l**********1 的大作中提到】
: 请问为什么不能用root分两段？inorder不是所有左子树全在左边，右子树全在右边么
: ？
【在 l**********1 的大作中提到】
: 请问为什么不能用root分两段？inorder不是所有左子树全在左边，右子树全在右边么
: ？
h*y
7 楼
题目没有看清楚
是BFS and inorder
【在 l**********1 的大作中提到】
: 请问为什么不能用root分两段？inorder不是所有左子树全在左边，右子树全在右边么
: ？
是BFS and inorder
【在 l**********1 的大作中提到】
: 请问为什么不能用root分两段？inorder不是所有左子树全在左边，右子树全在右边么
: ？
c*w
8 楼
preorder+inorder 和 BFS+inorder没有本质区别
【在 s******n 的大作中提到】
: 楼上完全错误，不能用root分两段，这办法只适合preorder+inorder
【在 s******n 的大作中提到】
: 楼上完全错误，不能用root分两段，这办法只适合preorder+inorder
e*e
9 楼
我觉得这题得用queue.
随便乱写了点，运行没有问题：
typedef struct bfs_binary_tree_info
{
binary_tree * parent;
//true for left child, false for right child
bool left_flag;
int * inorder;
int m;
int BFS_index;
}bfs_binary_tree_info;
binary_tree * build_binary_tree_from_inorder_BFS2 ( int inorder[], int m,
int BFS[], int BFS_index )
{
//verify input, make sure they are all valid
int root = BFS[BFS_index];
int root_in_index = -1;
queue tree_queue;
int prev_lvl_count = 0;
int cur_lvl_count = 0;
int child_count = 0;
binary_tree * return_tree = NULL;
bfs_binary_tree_info * tmp_info;
bfs_binary_tree_info * info = (bfs_binary_tree_info * )malloc (sizeof (
bfs_binary_tree_info ));
info->parent = NULL;
info->left_flag = true;///we dont care since parent is NULL, this is
root
info->m = m;
info->inorder = inorder;
info->BFS_index =BFS_index;
bfs_binary_tree_info * end = (bfs_binary_tree_info * )malloc (sizeof (
bfs_binary_tree_info ));
end->parent = NULL;
end->left_flag = true;///we dont care since parent is NULL, this is root
end->m = m;
end->inorder = NULL;
end->BFS_index =BFS_index;
tree_queue.push (info);
tree_queue.push (end);
while (!tree_queue.empty ())
{
tmp_info = tree_queue.front ();
tree_queue.pop ();
if (tmp_info == end)
{
if (!tree_queue.empty ())
{
tree_queue.push (end);
prev_lvl_count += cur_lvl_count;
cur_lvl_count = 0;
child_count = 0;
}
else
{
//eend of it
break;
}
}
else
{
binary_tree * node = (binary_tree *) malloc (sizeof (binary_tree
));
cur_lvl_count++;
node->data = BFS[tmp_info->BFS_index + prev_lvl_count];
node->left = NULL;
node->right = NULL;
if (tmp_info->parent == NULL)
{
return_tree = node;
}
else
{
if (tmp_info->left_flag)
tmp_info->parent->left = node;
else
tmp_info->parent->right = node;
}
//now find the root from inorder
for (int i = 0; i < tmp_info->m; i++)
{
if (tmp_info->inorder[i]==node->data)
root_in_index = i;
}
if (root_in_index != 0 )
{
bfs_binary_tree_info * new_info = (bfs_binary_tree_info * )
malloc (sizeof (bfs_binary_tree_info ));
new_info->parent = node;
new_info->left_flag = true;///we dont care since parent is
NULL, this is root
new_info->m = root_in_index;
new_info->inorder = tmp_info->inorder;
new_info->BFS_index = child_count;
tree_queue.push (new_info);
child_count++;
//do have left child
//node->left = build_binary_tree_from_inorder_BFS (inorder,
root_in_index, BFS, ++BFS_index);
}
if (root_in_index != tmp_info->m -1 )
{
//do have right child
bfs_binary_tree_info * new_info = (bfs_binary_tree_info * )
malloc (sizeof (bfs_binary_tree_info ));
new_info->parent = node;
new_info->left_flag = false;///we dont care since parent is
NULL, this is root
new_info->inorder = tmp_info->inorder + root_in_index + 1;
new_info->m = tmp_info->m - root_in_index - 1;
new_info->BFS_index =child_count;
child_count++;
tree_queue.push (new_info);
}
}
}
//now from 0 to root_in_index is left side
//from root_in_index to m is right side
return return_tree;
}
int inorder[]= {8,5,7,4,9,6};
int BFS[]= {7,8,9,5,4,6};
binary_tree * tree = build_binary_tree_from_inorder_BFS2 (inorder, 6, BFS, 0
);
随便乱写了点，运行没有问题：
typedef struct bfs_binary_tree_info
{
binary_tree * parent;
//true for left child, false for right child
bool left_flag;
int * inorder;
int m;
int BFS_index;
}bfs_binary_tree_info;
binary_tree * build_binary_tree_from_inorder_BFS2 ( int inorder[], int m,
int BFS[], int BFS_index )
{
//verify input, make sure they are all valid
int root = BFS[BFS_index];
int root_in_index = -1;
queue
int prev_lvl_count = 0;
int cur_lvl_count = 0;
int child_count = 0;
binary_tree * return_tree = NULL;
bfs_binary_tree_info * tmp_info;
bfs_binary_tree_info * info = (bfs_binary_tree_info * )malloc (sizeof (
bfs_binary_tree_info ));
info->parent = NULL;
info->left_flag = true;///we dont care since parent is NULL, this is
root
info->m = m;
info->inorder = inorder;
info->BFS_index =BFS_index;
bfs_binary_tree_info * end = (bfs_binary_tree_info * )malloc (sizeof (
bfs_binary_tree_info ));
end->parent = NULL;
end->left_flag = true;///we dont care since parent is NULL, this is root
end->m = m;
end->inorder = NULL;
end->BFS_index =BFS_index;
tree_queue.push (info);
tree_queue.push (end);
while (!tree_queue.empty ())
{
tmp_info = tree_queue.front ();
tree_queue.pop ();
if (tmp_info == end)
{
if (!tree_queue.empty ())
{
tree_queue.push (end);
prev_lvl_count += cur_lvl_count;
cur_lvl_count = 0;
child_count = 0;
}
else
{
//eend of it
break;
}
}
else
{
binary_tree * node = (binary_tree *) malloc (sizeof (binary_tree
));
cur_lvl_count++;
node->data = BFS[tmp_info->BFS_index + prev_lvl_count];
node->left = NULL;
node->right = NULL;
if (tmp_info->parent == NULL)
{
return_tree = node;
}
else
{
if (tmp_info->left_flag)
tmp_info->parent->left = node;
else
tmp_info->parent->right = node;
}
//now find the root from inorder
for (int i = 0; i < tmp_info->m; i++)
{
if (tmp_info->inorder[i]==node->data)
root_in_index = i;
}
if (root_in_index != 0 )
{
bfs_binary_tree_info * new_info = (bfs_binary_tree_info * )
malloc (sizeof (bfs_binary_tree_info ));
new_info->parent = node;
new_info->left_flag = true;///we dont care since parent is
NULL, this is root
new_info->m = root_in_index;
new_info->inorder = tmp_info->inorder;
new_info->BFS_index = child_count;
tree_queue.push (new_info);
child_count++;
//do have left child
//node->left = build_binary_tree_from_inorder_BFS (inorder,
root_in_index, BFS, ++BFS_index);
}
if (root_in_index != tmp_info->m -1 )
{
//do have right child
bfs_binary_tree_info * new_info = (bfs_binary_tree_info * )
malloc (sizeof (bfs_binary_tree_info ));
new_info->parent = node;
new_info->left_flag = false;///we dont care since parent is
NULL, this is root
new_info->inorder = tmp_info->inorder + root_in_index + 1;
new_info->m = tmp_info->m - root_in_index - 1;
new_info->BFS_index =child_count;
child_count++;
tree_queue.push (new_info);
}
}
}
//now from 0 to root_in_index is left side
//from root_in_index to m is right side
return return_tree;
}
int inorder[]= {8,5,7,4,9,6};
int BFS[]= {7,8,9,5,4,6};
binary_tree * tree = build_binary_tree_from_inorder_BFS2 (inorder, 6, BFS, 0
);
n*n
10 楼
co-ask
k*r
11 楼
虽然一个子树在BFS 序列中会不连续，但我觉得这道题还是可以模拟preorder+inorder
用递归做，唯一要额外注意的就是要把不连续的BFS串抽出来拼成连续串（以便这个连
续串对应一个子树）
code写起来也不麻烦，十几行吧，请高手指正
struct node{node * l,r; int id;}
node * f(int b[], int i[], int len){
if (len==0){return NULL}
node * h=new node; h->id=b[0]; h->l=NULL; h->r=NULL;
if (len==1){ return h;}
int k=findhead(b[0], i); map m;
int *newi=new int[k]; for (int j=0; j
int *newi2=new int[len-k-1]; for (int j=k+1; j
return h;
}
用递归做，唯一要额外注意的就是要把不连续的BFS串抽出来拼成连续串（以便这个连
续串对应一个子树）
code写起来也不麻烦，十几行吧，请高手指正
struct node{node * l,r; int id;}
node * f(int b[], int i[], int len){
if (len==0){return NULL}
node * h=new node; h->id=b[0]; h->l=NULL; h->r=NULL;
if (len==1){ return h;}
int k=findhead(b[0], i); map
int *newi=new int[k]; for (int j=0; j
int *newi2=new int[len-k-1]; for (int j=k+1; j
return h;
}
p*2
12 楼
看了看，感觉应该可以分两段。
BFS 可以看出7是root
indorder可以看出85是左树，496是右树
BFS又可以看出，8是左树的根，9是右树的根
7
/ \
8 9
\ / \
5 4 6
inorder: 857496
BFS: 789546
BFS 可以看出7是root
indorder可以看出85是左树，496是右树
BFS又可以看出，8是左树的根，9是右树的根
7
/ \
8 9
\ / \
5 4 6
inorder: 857496
BFS: 789546
p*n
13 楼
有虫吧
有输入错
＋1＋2也不对巴
要不要在楼主的例子上跑一跑？
int
【在 l**********1 的大作中提到】
: 写了个练手，求牛人指正
: public static TreeNode rebuild(int[] inorder,int[] bfs,int bfsl,int bfsh,int
: inorderl, inorderh){
: //base case
: if(bsfl>=bfsh||inorderl>inorderh) return null;
: TreeNode root=new TreeNode();
: root.value=bfs[bfsl];
: //find the index of root value in inorder array
: int cutoff=findCut(inorder,inorderl,inorderh,bfs[bfsl]);
: //build the tree recursively
有输入错
＋1＋2也不对巴
要不要在楼主的例子上跑一跑？
int
【在 l**********1 的大作中提到】
: 写了个练手，求牛人指正
: public static TreeNode rebuild(int[] inorder,int[] bfs,int bfsl,int bfsh,int
: inorderl, inorderh){
: //base case
: if(bsfl>=bfsh||inorderl>inorderh) return null;
: TreeNode root=new TreeNode();
: root.value=bfs[bfsl];
: //find the index of root value in inorder array
: int cutoff=findCut(inorder,inorderl,inorderh,bfs[bfsl]);
: //build the tree recursively
相关阅读
有CRO版吗华裔女博士状告纽约州立大学歧视违约 索偿750万 (转载)大家看看这个是什么结构(histology)AHA fellowship的推荐信也求review机会 (转载)有没有> 1,000,000 蛋白MARKER？paper help，包子答谢。推荐一个好用的Nanog抗体从抗原柱洗脱的抗体沉淀？谁要低吸附Ultra-low attachment 96 plate(ZT) 记2010国家最高科技奖获得者王振义：教癌细胞改邪归正各位工业界大牛给我指点迷津 (关于找工)请问yeast two hybrid 的一个问题国内医学本科毕业，到美国也可以做postdoc吗？求教: 细菌genome分析paper help!!!今天看到一个杂志JoVE，非常有意思急求2篇paper!!! thanks!Scientific Reports ------ a new Plos One?饶子和不当南开校长了