Esiry.com
Focus on Machine Learning.

Reverse Building a Tree Based on Traversal Results

In the business, you may encounter a situation of reverse building trees, such as how to reverse-build a tree when acquiring text data such as dependencies, administrative divisions, and organizational structures from external tools. We simulate the reverse build process of such a tree by “getting the depth of the tree to traverse the result, then constructing the tree structure, and finally outputting it in JSON format”. This article uses Ruby as the description language.

1) Traversed result text of the acquired tree

company   
+- org-1   
+- org-2  
|  \- org-2.1   
+- org-3   
+- org-4  
+- org-5  
+- org-6   
+- org-7  
|  +- org-7.1   
|  |  \- org-7.1.1  
|  +- org-7.2  
|  \- org-7.3  
+- org-8  
|  +- org-8.1  
|  \- org-8.2  
+- org-9  
+- org-10  
|  +- org-10.1  
|  \- org-10.2  
+- org-11   
+- org-12  
|  \- org-12.1  
+- org-13   
+- org-14  
|  +- org-14.1   
|  \- org-14.2   
+- org-15   
+- org-16   
|  +- org-16.1  
|  |  +- org-16.1.1  
|  |  |  \- org-16.1.1.1   
|  |  +- org-16.1.2   
|  |  +- org-16.1.3  
|  |  \- org-16.1.4  
|  +- org-16.2  
|  |  \- org-16.2.1  
|  \- org-16.3  
+- org-17  
+- org-18  
|  \- org-18.1  
+- org-19   
+- org-20   
+- org-21   
|  +- org-21.1   
|  \- org-21.2  
+- org-22  
+- org-23  
+- org-24  
|  \- org-24.1  
+- org-25  
+- org-26  
+- org-27  
+- org-28  
|  \- org-28.1  
+- org-29   
|  +- org-29.1   
|  \- org-29.2  
\- org-30 

2)Ruby reverse build tree code

#!/usr/bin/ruby    
#-*- coding: UTF-8 -*-    
require 'json'    
  
class Node    
  def initialize(name, parent)    
    @name = name    
    @parent = parent    
    @children = []    
  end    
  def add_child(child)    
    @children.push(child)    
  end    
  def name(name)    
    @name = name    
  end    
  def parent()    
    return @parent    
  end    
  def to_json(*options)    
    if @children.length > 0    
      return {name: @name, children: @children}.to_json(*options)    
    end    
    return {name: @name}.to_json(*options)    
  end    
end    
    
def process(line, last_line)    
  m = $pattern.match(line)    
  if m    
    sign = m[3]    
    depth = m[2].gsub(/\s/, '').length + sign.sub(/[+\\]/, '').length    
    name = m[4].strip    
    if 0 == m[1].length    
      $root.name(name)    
      $depth_last += 1    
    else    
      if depth < $depth_last    
        ($depth_last - depth).times { $parent = $parent.parent(); $depth_last -= 1 }    
      end    
      node = Node.new(name, $parent)    
      $parent.add_child(node)    
      $parent = node    
      $depth_last += 1    
    end    
  end    
end    
  
$root = $parent = Node.new('', nil)    
$pattern = /(([\|\s]*)([+\\]?-?).*?)(\w.*)/    
$depth_last = 0    
    
last_line = ""    
IO.foreach('depart_tree.txt') do |line|    
  process(line, last_line)    
  last_line = line    
end    
puts JSON.pretty_generate($root)    

3) After the successful construction, the JSON output of the tree

{  
  "name": "company",  
  "children": [  
    {  
      "name": "org-1"  
    },  
    {  
      "name": "org-2",  
      "children": [  
        {  
          "name": "org-2.1"  
        }  
      ]  
    },  
    {  
      "name": "org-3"  
    },  
    {  
      "name": "org-4"  
    },  
    {  
      "name": "org-5"  
    },  
    {  
      "name": "org-6"  
    },  
    {  
      "name": "org-7",  
      "children": [  
        {  
          "name": "org-7.1",  
          "children": [  
            {  
              "name": "org-7.1.1"  
            }  
          ]  
        },  
        {  
          "name": "org-7.2"  
        },  
        {  
          "name": "org-7.3"  
        }  
      ]  
    },  
    {  
      "name": "org-8",  
      "children": [  
        {  
          "name": "org-8.1"  
        },  
        {  
          "name": "org-8.2"  
        }  
      ]  
    },  
    {  
      "name": "org-9"  
    },  
    {  
      "name": "org-10",  
      "children": [  
        {  
          "name": "org-10.1"  
        },  
        {  
          "name": "org-10.2"  
        }  
      ]  
    },  
    {  
      "name": "org-11"  
    },  
    {  
      "name": "org-12",  
      "children": [  
        {  
          "name": "org-12.1"  
        }  
      ]  
    },  
    {  
      "name": "org-13"  
    },  
    {  
      "name": "org-14",  
      "children": [  
        {  
          "name": "org-14.1"  
        },  
        {  
          "name": "org-14.2"  
        }  
      ]  
    },  
    {  
      "name": "org-15"  
    },  
    {  
      "name": "org-16",  
      "children": [  
        {  
          "name": "org-16.1",  
          "children": [  
            {  
              "name": "org-16.1.1",  
              "children": [  
                {  
                  "name": "org-16.1.1.1"  
                }  
              ]  
            },  
            {  
              "name": "org-16.1.2"  
            },  
            {  
              "name": "org-16.1.3"  
            },  
            {  
              "name": "org-16.1.4"  
            }  
          ]  
        },  
        {  
          "name": "org-16.2",  
          "children": [  
            {  
              "name": "org-16.2.1"  
            }  
          ]  
        },  
        {  
          "name": "org-16.3"  
        }  
      ]  
    },  
    {  
      "name": "org-17"  
    },  
    {  
      "name": "org-18",  
      "children": [  
        {  
          "name": "org-18.1"  
        }  
      ]  
    },  
    {  
      "name": "org-19"  
    },  
    {  
      "name": "org-20"  
    },  
    {  
      "name": "org-21",  
      "children": [  
        {  
          "name": "org-21.1"  
        },  
        {  
          "name": "org-21.2"  
        }  
      ]  
    },  
    {  
      "name": "org-22"  
    },  
    {  
      "name": "org-23"  
    },  
    {  
      "name": "org-24",  
      "children": [  
        {  
          "name": "org-24.1"  
        }  
      ]  
    },  
    {  
      "name": "org-25"  
    },  
    {  
      "name": "org-26"  
    },  
    {  
      "name": "org-27"  
    },  
    {  
      "name": "org-28",  
      "children": [  
        {  
          "name": "org-28.1"  
        }  
      ]  
    },  
    {  
      "name": "org-29",  
      "children": [  
        {  
          "name": "org-29.1"  
        },  
        {  
          "name": "org-29.2"  
        }  
      ]  
    },  
    {  
      "name": "org-30"  
    }  
  ]  
}  

Your support will encourage us to be creative continuously!

Use [WeChat] Scan QR code for Appreciation

Use [Alipay] Scan QR code for Appreciation

Jumping to PayPal...
赞(0)
Please indicate the source:Esiry » Reverse Building a Tree Based on Traversal Results

Comment 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址