借鑒了前人的代碼,但是最后遞歸的指針調(diào)用自己也是調(diào)試了半天才出來,這里獻上完整的示例代碼.
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來確定科室之間的關(guān)系的, (a.frame_dept_str= a's parent's frame_dept_str + a's parent's dept_id).
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()
}
