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) } } }
相关推荐
baike 2020-05-09
sunjunior 2020-04-08
mieleizhi0 2019-12-31
郭岚 2019-11-04
hanyujianke 2019-11-01
Sophiego 2019-05-18
Cypress 2019-07-01
YUAN 2019-06-28
Lenskit 2019-06-26
WindChaser 2019-06-21
xingweiyong 2015-04-07
算法魔功 2018-07-24
王少雷的黑马 2017-02-17
Wcplus 2018-05-07
zhglinux 2018-07-27
举 2017-10-12
wangxiaohua 2015-08-11
明立 2017-06-30
大数据分析BDA 2015-01-12
pythonpycharm 2016-05-24
cassiePython 2016-04-27
大数据分析BDA 2014-08-02
tansuo 2014-07-30
Pythonandme 2019-03-06
pythoncream 2018-12-24
guyuanxiang 2014-04-29
PHP100 2019-03-28
PHP100 2019-03-28