Go语言实现二叉树遍历

生成二叉树

type Node struct {
data string
left *Node
right *Node
}

nodeG := Node{data: "g", left: nil, right: nil}
nodeF := Node{data: "f", left: &nodeG, right: nil}
nodeE := Node{data: "e", left: nil, right: nil}
nodeD := Node{data: "d", left: &nodeE, right: nil}
nodeC := Node{data: "c", left: nil, right: nil}
nodeB := Node{data: "b", left: &nodeD, right: &nodeF}
nodeA := Node{data: "a", left: &nodeB, right: &nodeC}

图例如下:

btree

结果应该是分别是:

广度优先: a -> b -> c -> d -> f -> e -> g

先序遍历: a -> b -> d -> e -> f -> g -> c

中序遍历: e -> d -> b -> g -> f -> a -> c

后序遍历: e -> d -> g -> f -> b -> c -> a

广度优先遍历

结果存在result里面,如果不存可以少一层变量

func breadthFirstSearch(node Node) []string {
var result []string
var nodes []Node = []Node{node}

for len(nodes) > 0 {
node := nodes[0]
nodes = nodes[1:]
result = append(result, node.data)
if (node.left != nil) {
nodes = append(nodes, *node.left)
}
if (node.right != nil) {
nodes = append(nodes, *node.right)
}
}
return result
}

递归版前中后序遍历

func preOrderRecursive(node Node) {
fmt.Println(node.data)
if node.left != nil {
preOrderRecursive(*node.left)
}
// 在这里输出就是中序
if node.right != nil {
preOrderRecursive(*node.right)
}
// 在这里输出是后序

非递归版遍历

这个地方强烈建议读一下下面的第一个链接,我遵照着那篇文章实现的,只是用Go改写了而已。

seqStack

首先定义一个数据结构,用来存储一些Node的信息。

type seqStack struct {
data [100]*Node
tag [100]int // 后续遍历准备
top int // 数组下标
}

preOrder

func preOrderLoop(node *Node) (result []string) {
var s seqStack
s.top = -1 // 空
if node == nil {
panic("no data here")
}else {
for node != nil || s.top != -1 {
for node != nil {
result = append(result, node.data)
s.top++
s.data[s.top] = node
node = node.left
}
s.top--
node = s.data[s.top + 1]
node = node.right
}
}
return
}

midOrder

func midOrderLoop(node *Node) (result []string) {
var s seqStack
s.top = -1
if node == nil {
panic("no data here")
}else {
for node != nil || s.top != -1 {
for node != nil {
s.top++
s.data[s.top] = node
node = node.left
}
s.top--
node = s.data[s.top + 1]
result = append(result, node.data)
node = node.right
}
}
return
}

postOrder

这里是可以运行的,但是总会抛出一个数组越界的错误,我看了半天也没看出来哪里有问题,Mac版的devel我这边又有bug,没用起来。至少思路对了,我后面再看一下哪里的问题。(感谢 @RiXu 指正)

func postOrderLoop(node *Node) (result []string)  {
var s seqStack
s.top = -1

if node == nil {
panic("no data here")
}else {
for node != nil || s.top != -1 {
for node != nil {
s.top++
s.data[s.top] = node
s.tag[s.top] = 0
node = node.left
}

if s.tag[s.top] == 0 {
node = s.data[s.top]
s.tag[s.top] = 1
node = node.right
}else {
for s.tag[s.top] == 1 {
s.top--
node = s.data[s.top + 1]
fmt.Println(node.data)
result = append(result, node.data)
if s.top < 0 {
break
}
}
node = nil
}
}
}
return
}

References