如何将Newick树格式转换为类似于分层javascript对象的树 [英] How to convert newick tree format to tree like Hierarchical javascript object

问题描述

我目前正在研究newick格式. https://en.wikipedia.org/wiki/Newick_format 我有一棵树的纽克弦

I am currently studying newick format. https://en.wikipedia.org/wiki/Newick_format I have a newick string of a tree

(A,B,(C,D)E)F;

如何将此字符串转换为分层的javascript对象，例如

How to convert this string into a hierarchical javascript object like

tree = {
  name: 'F',
  children: [{
    name: 'A'
  }, {
    name: 'B'
  }, {
    name: 'E',
    children: [{
      name: 'C'
    }, {
      name: 'D'
    }]
  }]

}

推荐答案

下面的代码应该可以在与您的示例类似的任何输入下正常工作.

The code below should work correctly with any input similar to your example.

但是，它假定每个节点都用单个字符标识.您必须对其进行修改以支持更长的符号.

However, it assumes that each node is identified with a single character. You'd have to modify it to support longer symbols.

此外，此代码也不是防弹符号，将在无效输入字符串的情况下在没有任何警告的情况下中断.

Also, this code is not bullet-proof and will break without any warning on invalid input strings.

主要思想是以相反的顺序解析字符串，并使用 stack 数组跟踪节点层次结构.

The main idea is to parse the string in reverse order and keep track of node hierarchy using the stack array.

var newick = '(A,B,(C,D)E)F',
    stack = [],
    child,
    root = [],
    node = root;

newick.split('').reverse().forEach(function(n) {
  switch(n) {
    case ')':
      // ')' => begin child node
      stack.push(node);
      node = child.children = [];
      break;

    case '(':
      // '(' => end of child node
      node = stack.pop();
      break;

    case ',':
      // ',' => separator (ignored)
      break;

    default:
      // assume all other characters are node names
      node.push(child = { name: n });
      break;
  }
});

这是一个简单的函数，它将转储结果结构:

And here is a simple function that will dump the resulting structure:

var dmp;

(dmp = function(node, level) {
  node.forEach(function(n) {
    console.log(Array(level).join('-') + n.name);
    n.children && dmp(n.children, level + 1);
  });
})(root, 1);

输出:

F
-E
--D
--C
-B
-A

这篇关于如何将Newick树格式转换为类似于分层javascript对象的树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！