Go 数据结构之二叉树详情

目录
  • Go 语言实现二叉树
    • 定义二叉树的结构
    • 二叉树遍历
    • 创建二叉树
    • 插入值
  • 测试

前言：

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

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

树形结构的深度（也被称作高度）则被定义为根节点为根节点至某个节点间的最长路径，而节点的深度则表示当当前节点至树根节点间的边数。二叉树有许多不同的形状和大小。 形状取决于节点的数量和节点的链接方式。

下图说明了由九个节点组成的二叉树的三种不同形状：

Go 语言实现二叉树

定义二叉树的结构

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)
}

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

创建二叉树

利用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
}

插入值

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 18
0 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

到此这篇关于 Go 数据结构之二叉树详情的文章就介绍到这了,更多相关 Go 二叉树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • 详解Go语言如何实现二叉树遍历

    详解Go语言如何实现二叉树遍历

    目录 1. 二叉树的定义 2. 前序遍历 3. 中序遍历 4. 后序遍历 1. 二叉树的定义 二叉树需满足的条件 ① 本身是有序树 ② 树中包含的各个节点的长度不能超过2,即只能是0.1或者2 2. 前序遍历 前序遍历二叉树的顺序:根——>左——>右 package main import "fmt" //定义结构体 type Student struct { Name string Age int Score float32 left *Student //左子树指针 r

  • Django更新models数据库结构步骤

    有时候在我们使用Django设计了models中的数据库结构,并且已经同步了数据库之后,我们突然想在数据表中更新或者增加新的字段,也就是需要修改数据库的结构,会出现以下的问题: C:\Users\Administrator\Desktop\Web开发\Django_Demo\jkxy>python manage.py makemigrations You are trying to add a non-nullable field 'grade' to student without a def

  • 使用go实现常见的数据结构

    1 golang常见数据结构实现 1.1 链表 举单链表的例子,双向链表同理只是多了pre指针. 定义单链表结构: type LinkNode struct { Data int64 NextNode *LinkNode } 构造链表及打印链表: func main() { node := new(LinkNode) node.Data = 1 node1 := new(LinkNode) node1.Data = 2 node.NextNode = node1 // node1 链接到 nod

  • Go语言的数据结构转JSON

    目录 结构体转为 JSON 格式 接口转为 JSON 格式 Marshal() 函数的原型 总结 在日常工作中,除了需要从 JSON 转化为 Go 的数据结构.但往往相反的情况是:我们需要将数据以 JSON 字符串的形式发送到 Web 服务器.今天我们将学会如何从一个结构化数据编码为 JSON . Json(Javascript Object Nanotation)是一种数据交换格式,常用于前后端数据传输.任意一端将数据转换成json 字符串,另一端再将该字符串解析成相应的数据结构,如strin

  • Go 数据结构之二叉树详情

    Go 数据结构之二叉树详情

    目录 Go 语言实现二叉树 定义二叉树的结构 二叉树遍历 创建二叉树 插入值 测试 前言: 树可以有许多不同的形状,并且它们可以在每个节点允许的子节点数量或它们在节点内组织数据值的方式上有所不同. 而在其中最常用的树之一是二叉树. 二叉树是一棵树,其中每个节点最多可以有两个孩子. 一个孩子被识别为左孩子,另一个孩子被识别为右孩子. 二叉树是一种数据结构,在每个节点下面最多存在两个其他节点.即一个节点要么连接至一个.两个节点或不连接其他节点. 树形结构的深度(也被称作高度)则被定义为根节点为根节点

  • C语言数据结构之二叉树的非递归后序遍历算法

    C语言数据结构之二叉树的非递归后序遍历算法 前言: 前序.中序.后序的非递归遍历中,要数后序最为麻烦,如果只在栈中保留指向结点的指针,那是不够的,必须有一些额外的信息存放在栈中. 方法有很多,这里只举一种,先定义栈结点的数据结构 typedef struct{Node * p; int rvisited;}SNode //Node 是二叉树的结点结构,rvisited==1代表p所指向的结点的右结点已被访问过. lastOrderTraverse(BiTree bt){ //首先,从根节点开始,

  • JavaScript数据结构之二叉树的删除算法示例

    本文实例讲述了JavaScript数据结构之二叉树的删除算法.分享给大家供大家参考,具体如下: 从二叉查找树上删除节点的操作复杂程度取决于删除哪个节点.如果删除没有子节点的节点就非常简单,如果节点只有一个子节点,不管是左子节点还是右子节点,就变得稍微有点复杂,如果节点包含两个子节点就最复杂. 如果待删除节点是叶子节点,那么只需要将从父节点指向它的链接指向null. 如果待删除节点只包含一个子节点,那么原本指向它的节点就得使其指向它的子节点. 如果待删除节点包含两个子节点,那么我们可以采用两种方式

  • JavaScript数据结构之二叉树的遍历算法示例

    本文实例讲述了JavaScript数据结构之二叉树的遍历算法.分享给大家供大家参考,具体如下: 三种遍历的代码: function inOrder(node){//中序遍历 if(node!=null){ inOrder(node.left); document.write(node.show()+" "); inOrder(node.right); } } function preOrder(node){//先序遍历 if(node!=null){ document.write(no

  • JavaScript数据结构之二叉树的查找算法示例

    本文实例讲述了JavaScript数据结构之二叉树的查找算法.分享给大家供大家参考,具体如下: 前面文章介绍了二叉树的遍历,现在谈谈在二叉树中进行查找.对二叉查找树来说,一般有以下三类查找:最大值,最小值和给定值. 查找最小值就是遍历左子树,直到找到最后一个结点,这是因为在二叉查找树中较小的值总是在左子节点上的. 代码如下: function getMin(){//查找最小值 var current=this.root;//指向根节点 while(current.left!=null){ cur

  • JavaScript数据结构之二叉树的计数算法示例

    本文实例讲述了JavaScript数据结构之二叉树的计数算法.分享给大家供大家参考,具体如下: 二叉查找树的一个用途就是记录一组数据集中数据出现的次数.比如记录成绩的分布,给定一组考试成绩,如果未出现则加入树,如果已经出现则数量加一. 所以要修改Node对象,添加记录成绩出现次数加一,代码如下: function Node(data,left,right){ this.data=data; this.left=left; this.right=right; this.show=show; thi

  • C语言数据结构之二叉树详解

    C语言数据结构之二叉树详解

    目录 1. 树概念及结构 1.1树概念 1.2树的表示 2. 二叉树概念及结构 2.1概念 2.2数据结构中的二叉树 2.3特殊的二叉树 2.4二叉树的存储结构 2.5二叉树的性质 3. 二叉树顺序结构及概念 3.1二叉树的顺序结构 3.2堆的概念及结构 3.3堆的实现 4. 二叉树链式结构及实现 4.1二叉树链式结构的遍历 4.2二叉树的链式实现 1. 树概念及结构 1.1树概念 树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合.把它叫做树是因为它看起来像一棵

  • Java 数据结构进阶二叉树题集下

    目录 1.对称二叉树 2.创建并遍历二叉树 3.二叉树中两节点最近公共祖先 4.二叉搜索树与双向链表 5.根据前序和中序遍历结果创建二叉树 6.二叉树创建字符串 7.非递归实现二叉树前序遍历 8.非递归实现二叉树后序遍历 1.对称二叉树 [OJ链接] 分为以下几种情况: 二叉树为空,是对称二叉树 二叉树不为空,其左子树或者右子树为空,不是对称二叉树 二叉树不为空,左右子树都为空,是对称二叉树 二叉树不为空,左右子树不为空,左右子节点值不同,不是对称二叉树 二叉树不为空,左右子树不为空,左右子节点

  • Java 数据结构进阶二叉树题集上

    Java 数据结构进阶二叉树题集上

    目录 1.二叉树的遍历 (1)前.中.后序遍历 (2)层序遍历 2.获取树中子结点的个数 3.获取二叉树的高度 4.判断是不是完全二叉树 5.判断两个树是否相同 6.另一棵树的子树 7.判断平衡二叉树 二叉树操作的代码大多数使用递归来实现,代码会比较简洁,如果使用非递归,代码会比较的繁荣,而且不易理解.(上)中的题偏向于基础,后面(下)中的题机会比较难. 1.二叉树的遍历 (1)前.中.后序遍历 这里写到的遍历是递归遍历,代码比较简单,后续会写非递归的代码.以前序遍历为例: 如果根节点root为

  • Go语言数据结构之二叉树可视化详解

    Go语言数据结构之二叉树可视化详解

    目录 题目 源代码 做题思路 扩展 左右并列展示 上下并列展示 总结回顾 题目 以图形展示任意二叉树,如下图,一个中缀表达式表示的二叉树:3.14*r²*h/3 源代码 package main import ( "fmt" "io" "os" "os/exec" "strconv" "strings" ) type any = interface{} type btNode struc

随机推荐