登录
首页 >  Golang >  Go教程

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

来源:脚本之家

时间:2023-01-07 12:06:01 210浏览 收藏

IT行业相对于一般传统行业,发展更新速度更快,一旦停止了学习,很快就会被行业所淘汰。所以我们需要踏踏实实的不断学习,精进自己的技术,尤其是初学者。今天golang学习网给大家整理了《golang通过递归遍历生成树状结构的操作》,聊聊遍历、递归、树状结构,我们一起来看看吧!

业务场景:

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

解决办法:

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

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

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的树结构三种遍历方式

看代码吧~

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()
}

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

终于介绍完啦!小伙伴们,这篇关于《golang通过递归遍历生成树状结构的操作》的介绍应该让你收获多多了吧!欢迎大家收藏或分享给更多需要学习的朋友吧~golang学习网公众号也会发布Golang相关知识,快来关注吧!

声明:本文转载于:脚本之家 如有侵犯,请联系study_golang@163.com删除
相关阅读
更多>
最新阅读
更多>
课程推荐
更多>
评论列表