go语言浅析二叉树

Hello,各位小伙伴大家好,我是小栈君,今天给大家带来的分享是关于关于二叉树相关的知识点,并用go语言实现一个二叉树和对二叉树进行遍历。

我们主要针对二叉树的概念,go实战实现二叉树的前序遍历、中序遍历、后序遍历。

二叉树概念

在计算机科学领域内,二叉树代表的是具有两个节点的树形结构,通常子树被称作为“左子树”,右边的被称作为“右子树”。二叉树通常的应用于实现二叉查找树和二叉堆。

例如上述图片中,我们就制定了一个二叉树,其中d、e、f称作a树的叶子节点。

[叶子结点是离散数学中的概念。一棵树当中没有子结点(即度为0)的结点称为叶子结点,简称“叶子”。 叶子是指出度为0的结点,又称为终端结点]

b和c 作为树a的孩子结点,b和a因为作为一个根a的孩子,所以他们的称呼为兄弟结点。其实总结一点就是关于二叉树各个结点的称呼其实和我们在家庭中,对于各个亲戚长辈的称呼类似。

在百度百科中也归纳除了关于二叉树的分类

一棵深度为k,且有2^k-1个结点的二叉树,称为满二叉树。这种树的特点是每一层上的结点数都是最大结点数。而在一棵二叉树中,除最后一层外,若其余层都是满的,并且或者最后一层是满的,或者是在右边缺少连续若干结点,则此二叉树为完全二叉树。

具有n个结点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树,至少有2k-1个叶子结点,至多有2k-1个结点。

所以通过我们上面的理论基础,我们结合代码来实现一下我们的二叉树结构。


如图所示 ,我们定义了一个树treeNode的结构体,关于结构体的分享,小栈君会在下一期对大家进行分享。对于go语言专题分享已经过了差不多三分之一,接下来我们会开启新的分享之旅,还请各位持续关注“IT干货栈”。

闲话不多说,我们在结构体中定义了三个参数,一个是树的名称,一个是树的左节点和右节点。请各位小伙伴注意哦,这里的用的是指针,因为在go语言中如果说不用引用传递,在后续添加节点后是没有任何效果的,下面我会给大家进行演示一下。



当我们将节点定义为不是引用类型的时候,直接编译器都通不过,报了一个无效的递归类型的错误。


所以我们先初始化一个根节点名称为“It干货栈”的节点,然后左节点名称为It ,右节点为干货。两个子节点就都没有左右节点。为了后续二叉树的遍历提供更多的数据,我们将增加方法进行追加树的节点。

// 定义一个树的节点 [IT干货栈]
type treeNode struct {
    name  string    // 定义树的名称
    left  *treeNode // 左节点
    right *treeNode // 右节点
}

// It干货栈
func main() {
    var node = treeNode{name: "It干货栈", left: &treeNode{name: "It", left: nil}, right: &treeNode{name: "干货"}}
    addLeftNode(&node, 2)
    addLeftNode(node.left, 3)
    addLeftNode(node.left.left, 4)
    addLeftNode(node.left.left.left, 5)
    node.addRightNode(2)
    node.right.addRightNode(3)
    node.right.right.addRightNode(4)
    node.right.right.right.addRightNode(5)
    fmt.Println(node)
}

// 增加二叉树左节点
func addLeftNode(node *treeNode, value int) {
    children := treeNode{name: fmt.Sprintf("子节点%s%d", "It干货栈", value)}
    node.left = &children
}

// 增加二叉树右节点
func (node *treeNode) addRightNode(value int) {
    children := treeNode{
        name:  fmt.Sprint("关注公众号", value),
        left:  nil,
        right: nil,
    }
    node.right = &children
}

以上代码我们我们定义了一个树节点,并且增加了相关的增加的节点的方法,细心的小伙伴可能已经看出来了,我们增加左节点和增加右节点的方法并不相同,那是因为在go语言中我们不仅可以写通用方法,比如增加二叉树左节点addLeftNode 方法。

我们还可以指定仅为treeNode专属方法addRightNode。

我们在添加了很多节点后,如果是采用传统的print打印出来的结果,如下图所示



所以接下来小栈君将为大家分享关于二叉树的前序、中序、后序遍历。

二叉树遍历

遍历是对树的一种最基本的运算,所谓遍历二叉树,就是按一定的规则和顺序走遍二叉树的所有结点,使每一个结点都被访问一次,而且只被访问一次。由于二叉树是非线性结构,因此,树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。

前序遍历

二叉树的前序遍历,又称为先序遍历。在二叉树的前序的顺序,首先访问根,再先序遍历左(右)子树,最后先序遍历右(左)子树。



是不是很简单的代码就完成了我们关于二叉树的前序遍历。先访问根节点,然后依次遍历右节点和左节点,当然我们也可以交换顺序进行先遍历左节点在继续遍历右节点。

中序遍历

关于go语言中序遍历的顺序,首先中序遍历左(右)子树,再访问根,最后中序遍历右(左)子树。


后序遍历

go语言的后序遍历顺序是首先后序遍历左(右)子树,再后序遍历右(左)子树,最后访问根。那么他的顺序就应该如图所示:



以上就是关于二叉树的遍历的分享,关于二叉树的讲解我们就到这里,对于先序遍历,中序遍历,后续遍历,其实其实也就是遍历的顺序不同而已,接下来就附上当前测试用例的代码。

// 定义一个树的节点 [IT干货栈]
type treeNode struct {
    name  string    // 定义树的名称
    left  *treeNode // 左节点
    right *treeNode // 右节点l
}

// It干货栈
func main() {
    var node = treeNode{name: "It干货栈", left: &treeNode{name: "It", left: nil}, right: &treeNode{name: "干货"}}
    addLeftNode(&node, 2)
    addLeftNode(node.left, 3)
    addLeftNode(node.left.left, 4)
    addLeftNode(node.left.left.left, 5)
    node.addRightNode(2)
    node.right.addRightNode(3)
    node.right.right.addRightNode(4)
    node.right.right.right.addRightNode(5)
    traversal(&node)
}

// 遍历
func traversal(node *treeNode) {
    if node == nil {
        return
    }
    traversal(node.left)
    traversal(node.right)
    fmt.Println("名称", node.name)
}

// 增加二叉树左节点
func addLeftNode(node *treeNode, value int) {
    children := treeNode{name: fmt.Sprintf("子左节点->%s%d", "It干货栈", value)}
    node.left = &children
}

// 增加二叉树右节点
func (node *treeNode) addRightNode(value int) {
    children := treeNode{
        name:  fmt.Sprint("子右节点->关注公众号", value),
        left:  nil,
        right: nil,
    }
    node.right = &children
}

以上就是今天的分享了,如果你喜欢我的分享麻烦分享、转发或点击好看,我们下期再见,我是小栈君,拜了个拜~

本文由博客一文多发平台 OpenWrite 发布!

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 214,029评论 6 493
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,238评论 3 388
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 159,576评论 0 349
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,214评论 1 287
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,324评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,392评论 1 292
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,416评论 3 412
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,196评论 0 269
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,631评论 1 306
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,919评论 2 328
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,090评论 1 342
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,767评论 4 337
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,410评论 3 322
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,090评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,328评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,952评论 2 365
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,979评论 2 351

推荐阅读更多精彩内容