本节介绍了如何使用 Go 语言实现一个二叉树,示例代码在 binTree.go 中。 下面将binTree.go 的内容分成五个部分来介绍。第一部分如下:
packagemainimport ("fmt""math/rand""time")typeTreestruct { Left *Tree Value int Right *Tree}
这里是使用 Go 语言中的结构体定义的树的节点。由于我们没有真实的数据,所以将使用math/rand 包向树中填充随机的数值。
binTree.go 中代码的第二部分如下:
functraverse(t *Tree) {if t ==nil {return }traverse(t.Left) fmt.Println(t.Value, " ")traverse(t.Right)}
traverse()函数展示了如何使用递归访问二叉树上的所有节点。
binTree.go 中的第三个代码段如下:
funccreate(n int) *Tree {var t *Tree rand.Seed(time.Now().Unix())for i :=0; i <2*n; i++ { temp := rand.Intn(n *2) t =insert(t, temp) }return t}
create() 函数仅用于向树中填充随机的数值。
该程序的第四部分如下:
funcinsert(t *Tree, v int) *Tree {if t ==nil {return&Tree{nil, v, nil} }if v == t.Value {return t }if v < t.Value { t.Left =insert(t.Left, v)return t } t.Right =insert(t.Right, v)return t}
insert() 函数使用 if 语句做了很多重要的事。第一个 if 语句检查要操作的树是否为空。如果是空树,那么通过 &Tree{nil, v, nil} 创建的新节点将成为该树的根节点。第二个 if 语句判断二叉树上是否已经存在将要插入的值。如果值已经存在,那么函数将什么也不做然后返回。第三个 if 语句判断对于当前节点,被插入的值是在节点的左侧还是右侧,然后执行相应的操作。
注意,这里展示的实现创建的是非平衡二叉树。
binTree.go 的最后一部分包含如下的 Go 代码:
funcmain() { tree :=create(10) fmt.Println("The value of the root of the tree is", tree.Value)traverse(tree) fmt.Println() tree =insert(tree, -10) tree =insert(tree, -2)traverse(tree) fmt.Println() fmt.Println("The value of the root of the tree is", tree.Value)}
执行 binTree.go 将生成类似如下的输出:
$ go run binTree.go
The value of the root of the tree is 18
0 3 4 5 7 8 9 10 11 14 16 17 18 19
-10 -2 0 3 4 5 7 8 9 10 11 14 16 17 18 19
The value of the root of the tree is 18