Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

make a tree from a table using golang?

Tags:

tree

go

treenode

I want to make a tree from a table. the table is as following:

OrgID   OrgName        parentID
A001    Dept           0 -----th top
A002    subDept1        A001
A003    sub_subDept    A002
A006    gran_subDept   A003
A004    subDept2        A001 

and i want the result is as following,how to do it using go:

Dept

--subDept1

----sub_subDept

------gran_subDept

--subDept2
like image 534
user3373877 Avatar asked Apr 09 '14 09:04

user3373877


2 Answers

With the information provided in your question and comment, what could solve your problem is an ordinary recursive loop.

package main

import "fmt"

type Org struct {
    OrgID    string
    OrgName  string
    parentID string
}

func printTree(tbl []Org, parent string, depth int) {
    for _, r := range tbl {
        if r.parentID == parent {
            for i := 0; i < depth; i++ {
                fmt.Print("--")
            }
            fmt.Print(r.OrgName, "\n\n")
            printTree(tbl, r.OrgID, depth+1)
        }
    }
}

func main() {
    data := []Org{
        {"A001", "Dept", "0 -----th top"},
        {"A002", "subDept1", "A001"},
        {"A003", "sub_subDept", "A002"},
        {"A006", "gran_subDept", "A003"},
        {"A004", "subDept2", "A001"},
    }

    printTree(data, "0 -----th top", 0)
}

Result:

Dept

--subDept1

----sub_subDept

------gran_subDept

--subDept2

Playground: http://play.golang.org/p/27CQAhI8gf

Be aware that this recursive function might get stuck in an loop incase there if a parent is the descendant of its own child.

like image 22
ANisus Avatar answered Sep 22 '22 12:09

ANisus


If you want to parse the lines into a tree structure, this is a way to do it:

package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strings"
)

type Node struct {
    name     string
    children []*Node
}

var (
    nodeTable = map[string]*Node{}
    root      *Node
)

func add(id, name, parentId string) {
    fmt.Printf("add: id=%v name=%v parentId=%v\n", id, name, parentId)

    node := &Node{name: name, children: []*Node{}}

    if parentId == "0" {
        root = node
    } else {

        parent, ok := nodeTable[parentId]
        if !ok {
            fmt.Printf("add: parentId=%v: not found\n", parentId)
            return
        }

        parent.children = append(parent.children, node)
    }

    nodeTable[id] = node
}

func scan() {
    input := os.Stdin
    reader := bufio.NewReader(input)
    lineCount := 0
    for {
        lineCount++
        line, err := reader.ReadString('\n')
        if err == io.EOF {
            break
        }
        if err != nil {
            fmt.Printf("error reading lines: %v\n", err)
            return
        }
        tokens := strings.Fields(line)
        if t := len(tokens); t != 3 {
            fmt.Printf("bad input line %v: tokens=%d [%v]\n", lineCount, t, line)
            continue
        }
        add(tokens[0], tokens[1], tokens[2])
    }
}

func showNode(node *Node, prefix string) {
    if prefix == "" {
        fmt.Printf("%v\n\n", node.name)
    } else {
        fmt.Printf("%v %v\n\n", prefix, node.name)
    }
    for _, n := range node.children {
        showNode(n, prefix+"--")
    }
}

func show() {
    if root == nil {
        fmt.Printf("show: root node not found\n")
        return
    }
    fmt.Printf("RESULT:\n")
    showNode(root, "")
}

func main() {
    fmt.Printf("main: reading input from stdin\n")
    scan()
    fmt.Printf("main: reading input from stdin -- done\n")
    show()
    fmt.Printf("main: end\n")
}
like image 57
Everton Avatar answered Sep 20 '22 12:09

Everton