二叉树的三种遍历方式:
package main
import "fmt"
type Hero struct {
No int
Name string
Left *Hero
Right *Hero
}
//前序遍历 根左右
// 前序遍历 先输入root 然后在输出左子树,然后再输出右子树
func PreOrder(node *Hero) {
if node != nil {
fmt.Printf("no=%d name=%s\n", node.No, node.Name)
PreOrder(node.Left)
PreOrder(node.Right)
}
}
//中序遍历 先输出root的左子树,再输出root节点,最后输出root的右子树
func InfixOrder(node *Hero) {
if node != nil {
InfixOrder(node.Left)
fmt.Printf("no=%d name=%s\n", node.No, node.Name)
InfixOrder(node.Right)
}
}
//后序遍历 先输出左子树,再输出右子树,最后输出当前node节点
func PostOrder(node *Hero) {
if node != nil {
PostOrder(node.Left)
PostOrder(node.Right)
fmt.Printf("no=%d name=%s\n", node.No, node.Name)
}
}
func main() {
root := &Hero{
No: 1,
Name: "宋江",
}
left1 := &Hero{
No: 2,
Name: "吴用",
}
node10 := &Hero{
No: 10,
Name: "李逵",
}
node12 := &Hero{
No: 12,
Name: "拼命三郎阮小二",
}
left1.Left = node10
left1.Right = node12
right1 := &Hero{
No: 3,
Name: "卢俊义",
}
root.Left = left1
root.Right = right1
right2 := &Hero{
No: 4,
Name: "林冲",
}
right1.Right = right2
}
感觉下边的这边转载的更复杂了, 比不上上边的清晰易理解
转载自https://studygolang.com/articles/16314
go语言在区块链编程中有巨大的优势,其中fabric和ethereum都是基于go语言编写的。为了能更好的学习区块链的底层技术,先将go的基础打好。
本篇文章使用golang来实现树的遍历
树的定义
package main
type Node struct {
Val int
Left *Node
Right *Node
}
深度优先遍历
深度优先遍历需要优先使用栈
栈的定义
package main
import "container/list"
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结构体添加前序遍历的方法,前序遍历的思路是通过栈,将右子树先行压入栈,然后左子树压栈
package main
func (root *Node) PreTravesal() {
if root == nil {
return
}
s := 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)
}
}
}
中序遍历
package main
func (root *Node) Intravesal() {
if root == nil {
return
}
s := 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
}
}
后序遍历
package main
func (root *Node) PostTravesal() {
if root == nil {
return
}
s := NewStack()
out := 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 !s.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)
}
}
}