生成二叉树
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
}
网友评论