golang通过递归遍历生成树状结构的操作

时间:2022-10-19 13:05:18

业务场景:

一个机构查询科室信息的时候,希望返回树状结构的嵌套格式;

解决办法:

通过递归和指针,嵌套成对应的结构体;

借鉴了前人的代码,但是最后递归的指针调用自己也是调试了半天才出来,这里献上完整的示例代码.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
package main
import (
    "fmt"
    "encoding/json"
)
 
type dept struct {
    DeptId string `json:"deptId"`
    FrameDeptStr string `json:"frameDeptStr"`
    Child []*dept `json:"child"`
}
func main() {
    depts := make([]dept,0)
    var a dept
    a.DeptId = "1"
    a.FrameDeptStr = ""
    depts = append(depts,a)
    a.DeptId="3"
    a.FrameDeptStr = "1"
    depts = append(depts,a)
    a.DeptId="4"
    a.FrameDeptStr = "1"
    depts = append(depts,a)
    a.DeptId="5"
    a.FrameDeptStr = "13"
    depts = append(depts,a)
    a.DeptId="6"
    a.FrameDeptStr = "13"
    depts = append(depts,a)
    fmt.Println(depts)
 
    deptRoots := make([]dept,0)
    for _,v := range depts{
        if v.FrameDeptStr == ""{
            deptRoots= append(deptRoots,v)
        }
    }
 
    pdepts := make([]*dept,0)
    for i,_ := range depts{
        var a *dept
        a = &depts[i]
        pdepts = append(pdepts,a)
    }
    //获取了根上的科室
    fmt.Println("根上的科室有:",deptRoots)
 
 
    var node *dept
    node = &depts[0]
    makeTree(pdepts,node)
    fmt.Println("the result we got is",pdepts)
    data, _ := json.Marshal(node)
    fmt.Printf("%s", data)
 
}
 
func has(v1 dept,vs []*dept) bool  {
    var has bool
    has = false
    for _,v2 := range vs {
        v3 := *v2
        if v1.FrameDeptStr+v1.DeptId == v3.FrameDeptStr{
            has = true
            break
        }
    }
    return has
}
 
func makeTree(vs []*dept,node *dept) {
    fmt.Println("the node value in maketree is:",*node)
    childs := findChild(node,vs)
    fmt.Println(" the child we got is :",childs)
    for _,child := range childs{
        fmt.Println("in the childs's for loop, the child's address  here is:",&child)
        node.Child = append(node.Child,child)
        fmt.Println("in the child's for loop, after append the child is:",child)
        if has(*child,vs) {
            fmt.Println("i am in if has")
            fmt.Println("the child in if has is:",*child)
            fmt.Println("the child in if has 's address is:",child)
            makeTree(vs,child)
        }
    }
}
 
func findChild(v *dept,vs []*dept)(ret []*dept)  {
    for _,v2 := range vs{
        if v.FrameDeptStr+v.DeptId == v2.FrameDeptStr{
            ret= append(ret,v2)
        }
    }
    return
}

代码备注:

通过frame_dept_str来确定科室之间的关系的, (a.frame_dept_str= a's parent's frame_dept_str + a's parent's dept_id).

补充:golang的树结构三种遍历方式

看代码吧~

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
package main
import "log"
type node struct {
    Item  string
    Left  *node
    Right *node
}
type bst struct {
    root *node
}
/*
        m
     k     l
  h    i     j
a  b  c  d  e  f
//先序遍历(根左右):m k h a b i c d l j e f
//中序遍历(左根右):a h b k c i d m l e j f
//后序遍历(左右根):a b h c d i k e f j l m
*/
func (tree *bst) buildTree() {
    m := &node{Item: "m"}
    tree.root = m
    k := &node{Item: "k"}
    l := &node{Item: "l"}
    m.Left = k
    m.Right = l
    h := &node{Item: "h"}
    i := &node{Item: "i"}
    k.Left = h
    k.Right = i
    a := &node{Item: "a"}
    b := &node{Item: "b"}
    h.Left = a
    h.Right = b
    c := &node{Item: "c"}
    d := &node{Item: "d"}
    i.Left = c
    i.Right = d
    j := &node{Item: "j"}
    l.Right = j
    e := &node{Item: "e"}
    f := &node{Item: "f"}
    j.Left = e
    j.Right = f
}
//先序遍历
func (tree *bst) inOrder() {
    var inner func(n *node)
    inner = func(n *node) {
        if n == nil {
            return
        }
        log.Println(n.Item)
        inner(n.Left)
        inner(n.Right)
    }
    inner(tree.root)
}
//中序
func (tree *bst) midOrder() {
    var inner func(n *node)
    inner = func(n *node) {
        if n == nil {
            return
        }
        inner(n.Left)
        log.Println(n.Item)
        inner(n.Right)
    }
    inner(tree.root)
}
//后序
func (tree *bst) lastOrder() {
    var inner func(n *node)
    inner = func(n *node) {
        if n == nil {
            return
        }
        inner(n.Left)
        inner(n.Right)
        log.Println(n.Item)
    }
    inner(tree.root)
}
func main() {
    tree := &bst{}
    tree.buildTree()
    // tree.inOrder()
    tree.lastOrder()
}

以上为个人经验,希望能给大家一个参考,也希望大家多多支持服务器之家。如有错误或未考虑完全的地方,望不吝赐教。

原文链接:https://blog.csdn.net/weixin_38496860/article/details/83377875