Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
101 lines (82 sloc) 2.4 KB

Go 语言实现二叉树

本节介绍了如何使用 Go 语言实现一个二叉树,示例代码在 binTree.go 中。 下面将binTree.go 的内容分成五个部分来介绍。第一部分如下:

package main

import (
	"fmt"
	"math/rand"
	"time"
)

type Tree struct {
	Left  *Tree
	Value int
	Right *Tree
}

这里是使用 Go 语言中的结构体定义的树的节点。由于我们没有真实的数据,所以将使用math/rand 包向树中填充随机的数值。

binTree.go 中代码的第二部分如下:

func traverse(t *Tree) {
	if t == nil {
		return
	}
	traverse(t.Left)
	fmt.Println(t.Value, " ")
	traverse(t.Right)
}

traverse() 函数展示了如何使用递归访问二叉树上的所有节点。

binTree.go 中的第三个代码段如下:

func create(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() 函数仅用于向树中填充随机的数值。

该程序的第四部分如下:

func insert(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 代码:

func main() {
	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
You can’t perform that action at this time.