如何预测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
相关阅读
临床试验【转】知社圈：我为什么离开学术圈 (转载)Re: 张益堂确实有励志作用 (转载)Paper help是不是老板都招不到人了医学研究这个极其复杂的系统ChIP是尚永丰发明的？美国癌症疫苗研发成功，彻底根治率达97%生物解决了啥问题是什么人在喊“袁隆平养活了中国人”请问science to review结束后，under evaluation 需要多久呢？现在博后工资多少？研究长生不老也许根本没有意义cancer vaccine ， may be availablePaper help这不叫冷知识，这叫知识普及大家觉得Wang Jun和11g是一类人吗？ (转载)生物是中国离国际领先水平最接近的学科吧？有生物学背景的临床实验室技术员哈弗的肯尼迪学院好不好申请入读？