写点什么

跟着动画学 Go 数据结构之二叉树

作者:宇宙之一粟
  • 2022 年 5 月 06 日
  • 本文字数:1369 字

    阅读完需:约 4 分钟

跟着动画学 Go 数据结构之二叉树

树可以有许多不同的形状,并且它们可以在每个节点允许的子节点数量或它们在节点内组织数据值的方式上有所不同。 而在其中最常用的树之一是二叉树。 二叉树是一棵树,其中每个节点最多可以有两个孩子。 一个孩子被识别为左孩子,另一个孩子被识别为右孩子。


二叉树是一种数据结构,在每个节点下面最多存在两个其他节点。即一个节点要么连接至一个、两个节点或不连接其他节点。

树形结构的深度(也被称作高度)则被定义为根节点为根节点至某个节点间的最长路径,而节点的深度则表示当当前节点至树根节点间的边数。二叉树有许多不同的形状和大小。 形状取决于节点的数量和节点的链接方式。 下图说明了由九个节点组成的二叉树的三种不同形状:

Go 语言实现二叉树

  1. 定义二叉树的结构

package main
import ( "fmt" "math/rand" "time")
type Tree struct { Left *Tree Value int Right *Tree}
复制代码
  1. 二叉树遍历

func traverse(t *Tree) {  if t == nil {    return  }    traverse(t.Left)  fmt.Print(t.Value, " ")  traverse(t.Right)}
复制代码

traverse() 函数通过递归方式访问二叉树的全部节点。

  1. 创建二叉树

利用 create() 函数利用随机整数填写二叉树:

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}
复制代码
  1. 插入值

insert 函数:

  • 第一个 if 语句在插入时如果是空树,就把插入的节点设置为根节点,并创建为 &Tree{nil, v, nil}

  • 第二个 if 语句确定插入值是否已在二叉树中存在。若存在,函数将直接返回且不执行任何操作

  • 第三个 if 语句检查插入的值位于当前节点的左孩子节点还是右孩子节点,并插入到相应的位置。

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}
复制代码

测试

package main
import ( "fmt" "math/rand" "time")
type Tree struct { Left *Tree Value int Right *Tree}
func traverse(t *Tree) { if t == nil { return }
traverse(t.Left) fmt.Print(t.Value, " ") traverse(t.Right)}
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}
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}
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 boot of the the tree is", tree.Value)}
复制代码

运行结果:

The value of the root of the tree is 180 1 4 5 6 8 9 10 12 14 15 18 19 -10 -2 0 1 4 5 6 8 9 10 12 14 15 18 19 The value of the boot of the the tree is 18
复制代码


发布于: 2022 年 05 月 06 日阅读数: 14
用户头像

宇宙古今无有穷期,一生不过须臾,当思奋争 2020.05.07 加入

🏆InfoQ写作平台-第二季签约作者 🏆 混迹于江湖,江湖却没有我的影子 热爱技术,专注于后端全栈,轻易不换岗 拒绝内卷,工作于软件工程师,弹性不加班 热衷分享,执着于阅读写作,佛系不水文

评论

发布
暂无评论
跟着动画学 Go 数据结构之二叉树_数据结构_宇宙之一粟_InfoQ写作社区