goLang 二叉树遍历(递归 非递归 前序遍历 中序遍历 后序
2020-04-09 本文已影响0人
yulekwok
goLang 二叉树遍历(递归 非递归 前序遍历 中序遍历 后序遍历 层序遍历)
前序遍历
前序遍历的顺序是 根 -----> 左子树 -----> 右子树
中序遍历
中序遍历的顺序是 左子树 -----> 根 ------> 右子树
后序遍历
后序遍历的顺序是 左子树 -----> 右子树 -----> 根
代码
遍历代码
package BinarySearchTree
import (
"fmt"
"com.struct.study/struct/firstStudy/Queue"
"com.struct.study/struct/firstStudy/Stack"
)
type TreeNode struct {
Val interface{}
Left *TreeNode
Right *TreeNode
Parent *TreeNode
}
func NodeC(val interface{}, parent *TreeNode) *TreeNode {
return &TreeNode{
Val: val,
Left: nil,
Right: nil,
Parent: parent,
}
}
//前序遍历
// 根节点 左子树 右子树
func PreOrder(node *TreeNode) {
if node != nil {
fmt.Printf("%v ", node.Val)
PreOrder(node.Left)
PreOrder(node.Right)
}
}
//中序遍历
// 左子树 根节点 右子树
func InfixOrder(node *TreeNode) {
if node != nil {
InfixOrder(node.Left)
fmt.Printf("%v ", node.Val)
InfixOrder(node.Right)
}
}
//后序遍历
// 左子树 右子树 根节点
func PostOrder(node *TreeNode) {
if node != nil {
PostOrder(node.Left)
PostOrder(node.Right)
fmt.Printf("%v ", node.Val)
}
}
// 先序遍历
func PreOrderNew(node *TreeNode) {
if node == nil {
return
}
s := Stack.NewStack()
s.Push(node)
current, _ := s.Pop().(*TreeNode)
for current != nil {
fmt.Printf("%v ", current.Val)
if right := current.Right; right != nil {
s.Push(right)
}
if left := current.Left; left != nil {
s.Push(left)
}
current, _ = s.Pop().(*TreeNode)
}
fmt.Println()
}
// 中序遍历 非递归
func InOrderNew(node *TreeNode) {
if node == nil {
return
}
s := Stack.NewStack()
current := node
for s.Size() > 0 || current != nil {
if current != nil {
s.Push(current)
current = current.Left
} else {
current,_ = s.Pop().(*TreeNode)
fmt.Printf("%v ", current.Val)
current = current.Right
}
}
fmt.Println()
}
// 后序遍历 非递归
func PostOrderNew(node *TreeNode) {
if node == nil {
return
}
s := Stack.NewStack()
current := node
var pre (*TreeNode)
for current != nil || s.Size() > 0 {
for current != nil {
s.Push(current)
current = current.Left
}
current,_ = s.Top().(*TreeNode)
if current.Right == nil || pre == current.Right {
fmt.Printf("%v ", current.Val)
pre = current
s.Pop()
current = nil
} else {
current = current.Right
}
}
fmt.Println()
}
// 后序遍历2 非递归
func PostOrderNew2(node *TreeNode) {
s1, s2 := Stack.NewStack(), Stack.NewStack()
s1.Push(node)
for s1.Size() > 0 {
current,_ := s1.Pop().(*TreeNode)
s2.Push(current)
if current.Left != nil {
s1.Push(current.Left)
}
if current.Right != nil {
s1.Push(current.Right)
}
}
for s2.Size() > 0 {
current,_ := s2.Pop().(*TreeNode)
fmt.Printf("%v ", current.Val)
}
}
// 层序遍历
func LevelOrder(node *TreeNode) {
if node == nil {
return
}
listQueue := Queue.NewQueue()
listQueue.Push(node)
for listQueue.Len() > 0 {
current,_ := listQueue.Pop().(*TreeNode)
if current.Left != nil {
fmt.Printf(" %v --- (父%v) \n", current.Left.Val, current.Val)
listQueue.Push(current.Left)
}
if current.Right != nil {
listQueue.Push(current.Right)
fmt.Printf(" (父%v) --- %v \n", current.Val, current.Right.Val)
}
}
}
队列
package Queue
import (
"container/list"
"sync"
)
type Queue struct {
l *list.List
m sync.Mutex
}
func NewQueue() *Queue {
return &Queue{l: list.New()}
}
func (q *Queue) Push(v interface{}) {
if v == nil {
return
}
q.m.Lock()
defer q.m.Unlock()
q.l.PushBack(v)
}
func (q *Queue) Pop() interface{} {
q.m.Lock()
defer q.m.Unlock()
if elem := q.l.Front(); elem != nil {
q.l.Remove(elem)
return elem.Value
}
return nil
}
func (q *Queue) Len() int {
q.m.Lock()
defer q.m.Unlock()
return q.l.Len()
}
栈
package Stack
import (
"container/list"
"sync"
)
type Stack struct {
l *list.List
m sync.Mutex
}
func NewStack() *Stack {
return &Stack{l: list.New()}
}
func (s *Stack) Clear() {
s.m.Lock()
defer s.m.Unlock()
s.l = nil
}
func (s *Stack) Size() int {
s.m.Lock()
defer s.m.Unlock()
return s.l.Len()
}
func (s *Stack) isEmpty() bool {
s.m.Lock()
defer s.m.Unlock()
return s.l.Len() == 0
}
func (s *Stack) Push(v interface{}) {
if v == nil {
return
}
s.m.Lock()
defer s.m.Unlock()
s.l.PushFront(v)
}
func (s *Stack) Pop() interface{} {
s.m.Lock()
defer s.m.Unlock()
if elem := s.l.Front(); elem != nil {
s.l.Remove(elem)
return elem.Value
}
return nil
}
func (s *Stack) Top() interface{} {
s.m.Lock()
defer s.m.Unlock()
if elem := s.l.Front(); elem != nil {
return elem.Value
}
return nil
}
测试代码
tree := &BinarySearchTree.BinarySearchTree{}
intArray := [...]int{46, 35, 25, 16, 50, 49, 31, 27, 44, 21, 43, 24, 47}
for _, value := range intArray {
tree.Add(value)
}
fmt.Println("-------先序遍历-----------")
BinarySearchTree.PreOrder(tree.Root) // 46 35 25 16 21 24 31 27 44 43 50 49 47
fmt.Println()
fmt.Println("+++++++++++++++++++")
BinarySearchTree.PreOrderNew(tree.Root)//46 35 25 16 21 24 31 27 44 43 50 49 47
fmt.Println()
fmt.Println("---------中序遍历---------")
BinarySearchTree.InfixOrder(tree.Root)//16 21 24 25 27 31 35 43 44 46 47 49 50
fmt.Println()
fmt.Println("+++++++++++++++++++")
BinarySearchTree.InOrderNew(tree.Root)// 16 21 24 25 27 31 35 43 44 46 47 49 50
fmt.Println("--------后序遍历-------")
BinarySearchTree.PostOrder(tree.Root)//24 21 16 27 31 25 43 44 35 47 49 50 46
fmt.Println()
fmt.Println("+++++++++++++++++++")
BinarySearchTree.PostOrderNew(tree.Root)//24 21 16 27 31 25 43 44 35 47 49 50 46
BinarySearchTree.PostOrderNew2(tree.Root)//24 21 16 27 31 25 43 44 35 47 49 50 46
fmt.Println("--------层序遍历-------")
BinarySearchTree.LevelOrder(tree.Root)
//35 --- (父46)
//(父46) --- 50
//25 --- (父35)
//(父35) --- 44
//49 --- (父50)
//16 --- (父25)
//(父25) --- 31
//43 --- (父44)
//47 --- (父49)
//(父16) --- 21
//27 --- (父31)
//(父21) --- 24
