内容简介:go语言在区块链编程中有巨大的优势,其中fabric和ethereum都是基于go语言编写的。为了能更好的学习区块链的底层技术,先将go的基础打好。本篇文章使用golang来实现树的遍历深度优先遍历需要优先使用栈
go语言在区块链编程中有巨大的优势,其中fabric和ethereum都是基于 go 语言编写的。为了能更好的学习区块链的底层技术,先将go的基础打好。
本篇文章使用golang来实现树的遍历
树的定义
package tree type Node struct { Val int Left *Node Right *Node }
深度优先遍历
深度优先遍历需要优先使用栈
栈的定义
type Stack struct { list *list.List } func NewStack() *Stack { list := list.New() return &Stack{list} } func (stack *Stack) Push(value interface{}) { stack.list.PushBack(value) } func (stack *Stack) Pop() interface{} { if e := stack.list.Back(); e!= nil { stack.list.Remove(e) return e.Value } return nil } func (stack *Stack) Len() int { return stack.list.Len() } func (stack *Stack) Empty() bool { return stack.Len() == 0 }
前序遍历
为Stack结构体添加前序遍历的方法,前序遍历的思路是通过栈,将右子树先行压栈,然后左子树压栈
func (root *Node) PreTravesal() { if root == nil { return } s := stack.NewStack() s.push(root) for !s.Empty() { cur := s.Pop().(*Node) fmt.Println(cur.Val) if cur.Right != nil { s.Push(cur.Right) } if cur.Left != nil { s.Push(cur.Left) } } }
中序遍历
func (root *Node) InTravesal() { if root == nil { return } s := stack.NewStack() cur := root for { for cur != nil { s.Push(cur) cur = cur.Left } if s.Empty() { break } cur = s.Pop().(*Node) fmt.Println(cur.Val) cur = cur.right } }
后序遍历
func (root *Node) PostTravesal() { if root == nil { return } s := stack.NewStack() out := stack.NewStack() s.Push(root) for !s.Empty() { cur := s.Pop().(*Node) out.Push(cur) if cur.Left != nil { s.Push(cur.Left) } if cur.Right != nil { s.Push(cur.Right) } } for !out.Empty() { cur := out.Pop().(*Node) fmt.Println(cur.Val) } }
广度优先遍历
广度优先遍历需要使用到队列
实现队列
使用切片实现队列
package queue import ( "fmt" ) type Queue interface { Offer(e interface{}) Poll() interface{} Clear() bool Size() int IsEmpty() bool } type LinkedList struct { elements []interface{} } func New() *LinkedList { return &LinkedList{} } func (queue *LinkedList) Offer(e interface{}) { queue.elements = append(queue.elements, e) } func (queue *LinkedList) Poll() interface{} { if queue.IsEmpty() { fmt.Println("Poll error : queue is Empty") return nil } firstElement := queue.elements[0] queue.elements = queue.elements[1:] return firstElement } func (queue *LinkedList) Size() int { return len(queue.elements) } func (queue *LinkedList) IsEmpty() bool { return len(queue.elements) == 0 } func (queue *LinkedList) Clear() bool { if queue.IsEmpty() { fmt.Println("queue is Empty!") return false } for i := 0; i < queue.Size(); i++ { queue.elements[i] = nil } queue.elements = nil return true }
层序遍历
func (root *Node) LevelTravesal() { if root == nil { return } linkedList := queue.New() linkedList.Offer(root) for !linkedList.IsEmpty() { cur := linkedList.Poll().(*Node) fmt.Println(cur.Val) if cur.Left != nil { linkedList.Offer(cur.Left) } if cur.Right != nil { linkedList.Offer(cur.Right) } } }
以上所述就是小编给大家介绍的《golang之树的遍历》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 数组常见的遍历循环方法、数组的循环遍历的效率对比
- C++拾趣——STL容器的插入、删除、遍历和查找操作性能对比(Windows VirtualStudio)——遍历和删除
- Js遍历数组总结
- 遍历
- 遍历 DOM 注意点
- MySQL 实现树形的遍历
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。