前言 树的深度优先遍历(Depth-First Search, DFS)是一种用于遍历或搜索树数据结构的算法。 在深度优先遍历中,从根节点开始,先访问当前节点,然后递归地访问其子节点,直到到达叶子节点。 然后回溯到上一级节点,继续访问其未被访问的子节点。
js代码实现 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 const tree = { val : 'a' , children : [ { val : 'b' , children : [ { val : 'd' }, { val : 'e' } ] }, { val : 'c' , children : [ { val : 'f' }, { val : 'g' } ] } ] } function dfs (root ) { console .log (root.val ); if (root.children ) { root.children .forEach (child => { dfs (child); }) } } function dfsStack (root ) { let stack = [root]; while (stack.length > 0 ) { let node = stack.pop (); console .log (node.val ); if (node.children ) { const children = node.children ; for (let i = children.length - 1 ; i >= 0 ; i--) { stack.push (children[i]); } } } }
go代码实现 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 package mainimport "fmt" type Node struct { Val string Child []*Node } func newNode (val string ) *Node { return &Node{ Val: val, Child: make ([]*Node, 0 ), } } func (n *Node) AddChild(children ...*Node) { n.Child = append (n.Child, children...) } func Dfs (root *Node) { fmt.Println(root.Val) if len (root.Child) > 0 { for _, child := range root.Child { Dfs(child) } } } func DfsStack (root *Node) { stack := make ([]*Node, 0 ) stack = append (stack, root) for len (stack) > 0 { node := stack[len (stack)-1 ] stack = stack[:len (stack)-1 ] fmt.Println(node.Val) if len (node.Child) > 0 { for i := len (node.Child) - 1 ; i >= 0 ; i-- { stack = append (stack, node.Child[i]) } } } } func main () { a := newNode("a" ) b := newNode("b" ) c := newNode("c" ) d := newNode("d" ) e := newNode("e" ) f := newNode("f" ) g := newNode("g" ) a.AddChild(b, c) b.AddChild(d, e) c.AddChild(f, g) Dfs(a) fmt.Println("--------------" ) DfsStack(a) }