預序樹遍歷的解析序列化

我想解析一個字符串（預序樹遍歷的序列化）到JSON對象（樹的節點和邊）。預序樹遍歷的解析序列化

問題

你會如何提取節點之間的邊緣？

字符串表示

字符串中包含的節點和節點（邊緣）之間的依賴關係。

正向符號將是一個簡單的'>'，空（或反向一級）符號將是一個簡單的'<'字符。

實施例：

'1>2>5<6<<3>4>7(<<<<)'

提取元素

爲了提取的元素（節點，邊），我通過使用正則表達式預處理字符串。

var network_info = '1>2>5<6<<3>4>7(<<<<)'; 
var network_elements = network_info.replace(/(\(<*\))/,'').match(/<|>|[0-9]/g);

結果是

Array [ "1", ">", "2", ">", "5", "<", "6", "<", "<", "3", ">", "4", ">", "7"]

提取節點

爲了提取的節點，我所定義的函數「getNodes」。

function getNodes(network_elements) { 
    var nodes = []; 
    var node_id = 1; 

    for (var i = 0; i < network_elements.length; i++) { 
     if(network_elements[i] != '<' && network_elements[i] != '>') { 
      var node = {}; 
      node.id = node_id++; 
      node.label = network_elements[i]; 
      nodes.push(node); 
     } 
    } 
    return nodes; 
}

結果是一個包含的節點的ID和標籤

[ 
{id: 1, label: '1'}, 
{id: 2, label: '2'}, 
{id: 3, label: '5'}, 
{id: 4, label: '6'}, 
...]

問題JSON對象的List：邊

邊緣的結果應如下所示（從並表示相應節點的ID。

[ 
{id: 1, from: 1, to: 2}, 
{id: 2, from: 2, to: 3}, 
{id: 3, from: 2, to: 4}, 
{id: 4, from: 1, to: 5}, 
{id: 5, from: 5, to: 6}, 
{id: 6, from: 6, to: 7} 
]

實施例的僞碼

var edges = []; 
var edge_id = 1; 
var from_node_id = 1; 
var to_node_id = 2; 

LOOP: 

    GET from_node_id 

    var edge = {}; 
    edge.id = edge_id++; 
    edge.from = from_node_id; 
    edge.to = to_node_id++; 
    edges.push(edge);

樹結果

的字符串 '1> 2> 5 < 3> 4> 7（< < < <）' 樹看起來像這樣

Example Tree

任何幫助很大appre ciated。

非常感謝您-tao

來源

2017-07-02 tao

您可以使用節點的堆棧跟蹤當前路徑根。推入堆棧中的初始節點。然後，當看到>X時，將當前堆棧頂端的左邊緣添加到節點X，並在堆棧上按X。當您看到<...< Y時，爲每個<從堆棧中彈出一個節點，然後從堆棧頂部添加一個新的右邊緣到Y。

你似乎沒有問題的JSON細節。我會讓這些給你解決。

來源

2017-07-02 17:10:15 Gene

非常感謝您的幫助。建議的解決方案能夠解決問題！ – tao

預序樹遍歷的解析序列化

回答

相關問題