AI 助理
文档备案控制台
开发者社区 人工智能 文章 正文

Golang 数据结构实现之 二叉树

2017-11-16 2046
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：

   二叉树的理论知识，应该都比较了解了，下文不再详细介绍二叉树的基本知识。

   在二叉树中具有以下重要性质：

   1.在二叉树的第i层上最多有(2的i次方)个结点。

   2.高度为h的二叉树至多有(2的h+1次方-1)个结点。

   3.对任何一棵二叉树，如果其终端结点(叶子结点)数为n0，度为2的结点数为n2，则n0 = n2 + 1。

   下面就直接贴出golang的二叉树代码，由binaryTreeNode.go和binaryTree.go两个文件组合：

   binaryTreeNode.go：

   （

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
package  tree
                                                                                                                                      
import  (
     "math"
)
                                                                                                                                      
//二叉树节点
type BinTreeNode struct {
     data    interface {}   //数据域
     parent *BinTreeNode  //父节点
     lChild *BinTreeNode  //左孩子
     rChild *BinTreeNode  //右孩子
     height  int           //以该结点为根的子树的高度
     size    int           //该结点子孙数(包括结点本身)
}
                                                                                                                                       
func NewBinTreeNode(e  interface {}) *BinTreeNode {
     return  &BinTreeNode{data: e, size:  1 }
}
                                                                                                                                      
//获得节点数据
func ( this  *BinTreeNode) GetData()  interface {} {
     if  this  == nil {
         return  nil
     }
     return  this .data
}
                                                                                                                                      
//设置节点数据
func ( this  *BinTreeNode) SetData(e  interface {}) {
     this .data = e
}
                                                                                                                                      
//判断是否有父亲
func ( this  *BinTreeNode) HasParent() bool {
     return  this .parent != nil
}
                                                                                                                                       
//获得父亲节点
func ( this  *BinTreeNode) GetParent() *BinTreeNode {
     if  ! this .HasParent() {
         return  nil
     }
     return  this .parent
}
                                                                                                                                      
//设置父亲节点
func ( this  *BinTreeNode) setParent(p *BinTreeNode) {
     this .parent = p
     // this.parent.SetHeight() //更新父结点及其祖先高度
     // this.parent.SetSize()   //更新父结点及其祖先规模
}
                                                                                                                                      
//断开与父亲的关系
func ( this  *BinTreeNode) CutOffParent() {
     if  ! this .HasParent() {
         return
     }
     if  this .IsLChild() {
         this .parent.lChild = nil  //断开该节点与父节点的连接
     }  else  {
         this .parent.rChild = nil  //断开该节点与父节点的连接
     }
                                                                                                                                      
     this .parent = nil        //断开该节点与父节点的连接
     this .parent.SetHeight()  //更新父结点及其祖先高度
     this .parent.SetSize()    //更新父结点及其祖先规模
}
                                                                                                                                      
//判断是否有左孩子
func ( this  *BinTreeNode) HasLChild() bool {
     return  this .lChild != nil
}
                                                                                                                                      
//获得左孩子节点
func ( this  *BinTreeNode) GetLChild() *BinTreeNode {
     if  ! this .HasLChild() {
         return  nil
     }
     return  this .lChild
}
                                                                                                                                      
//设置当前结点的左孩子,返回原左孩子
func ( this  *BinTreeNode) SetLChild(lc *BinTreeNode) *BinTreeNode {
     oldLC :=  this .lChild
     if  this .HasLChild() {
        this .lChild.CutOffParent()  //断开当前左孩子与结点的关系
     }
     if  lc != nil {
         lc.CutOffParent()  //断开lc与其父结点的关系
         this .lChild = lc   //确定父子关系
         lc.setParent( this )
         this .SetHeight()  //更新当前结点及其祖先高度
         this .SetSize()    //更新当前结点及其祖先规模
     }
     return  oldLC
}
                                                                                                                                      
//判断是否有右孩子
func ( this  *BinTreeNode) HasRChild() bool {
     return  this .rChild != nil
}
                                                                                                                                      
//获得右孩子节点
func ( this  *BinTreeNode) GetRChild() *BinTreeNode {
     if  ! this .HasRChild() {
         return  nil
     }
     return  this .rChild
}
                                                                                                                                      
//设置当前结点的右孩子,返回原右孩子
func ( this  *BinTreeNode) SetRChild(rc *BinTreeNode) *BinTreeNode {
     oldRC :=  this .rChild
     if  this .HasRChild() {
       this .rChild.CutOffParent()  //断开当前左孩子与结点的关系
     }
     if  rc != nil {
         rc.CutOffParent()  //断开rc与其父结点的关系
         this .rChild = rc   //确定父子关系
         rc.setParent( this )
         this .SetHeight()  //更新当前结点及其祖先高度
         this .SetSize()    //更新当前结点及其祖先规模
     }
     return  oldRC
}
                                                                                                                                      
//判断是否为叶子结点
func ( this  *BinTreeNode) IsLeaf() bool {
     return  ! this .HasLChild() && ! this .HasRChild()
}
                                                                                                                                      
//判断是否为某结点的左孩子
func ( this  *BinTreeNode) IsLChild() bool {
     return  this .HasParent() &&  this  ==  this .parent.lChild
}
                                                                                                                                      
//判断是否为某结点的右孩子
func ( this  *BinTreeNode) IsRChild() bool {
     return  this .HasParent() &&  this  ==  this .parent.rChild
}
                                                                                                                                      
//取结点的高度,即以该结点为根的树的高度
func ( this  *BinTreeNode) GetHeight()  int  {
     return  this .height
}
                                                                                                                                      
//更新当前结点及其祖先的高度
func ( this  *BinTreeNode) SetHeight() {
     newH :=  0  //新高度初始化为0,高度等于左右子树高度加1中的大者
     if  this .HasLChild() {
         newH =  int (math.Max(float64(newH), float64( 1 + this .GetLChild().GetHeight())))
     }
     if  this .HasRChild() {
         newH =  int (math.Max(float64(newH), float64( 1 + this .GetRChild().GetHeight())))
     }
     if  newH ==  this .height {
         //高度没有发生变化则直接返回
         return
     }
                                                                                                                                      
     this .height = newH  //否则更新高度
     if  this .HasParent() {
         this .GetParent().SetHeight()  //递归更新祖先的高度
     }
}
                                                                                                                                      
//取以该结点为根的树的结点数
func ( this  *BinTreeNode) GetSize()  int  {
     return  this .size
}
                                                                                                                                      
//更新当前结点及其祖先的子孙数
func ( this  *BinTreeNode) SetSize() {
     this .size =  1  //初始化为1,结点本身
     if  this .HasLChild() {
         this .size +=  this .GetLChild().GetSize()  //加上左子树规模
     }
     if  this .HasRChild() {
         this .size +=  this .GetRChild().GetSize()  //加上右子树规模
     }
                                                                                                                                      
     if  this .HasParent() {
         this .parent.SetSize()  //递归更新祖先的规模
     }
                                                                                                                                      
}

 

    binaryTree.go：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
package  tree
                                                                                                                                                       
import  (
     "container/list"
)
                                                                                                                                                       
//二叉树
type binaryTree struct {
     root   *BinTreeNode  //根节点
     height  int
     size    int
}
                                                                                                                                                       
func NewBinaryTree(root *BinTreeNode) *binaryTree {
     return  &binaryTree{root: root}
}
                                                                                                                                                       
//获得二叉树总结点数
func ( this  *binaryTree) GetSize()  int  {
     return  this .root.size
}
                                                                                                                                                       
//判断二叉树是否为空
func ( this  *binaryTree) IsEmpty() bool {
     return  this .root != nil
}
                                                                                                                                                       
//获得二叉树根节点
func ( this  *binaryTree) GetRoot() *BinTreeNode {
     return  this .root
}
                                                                                                                                                       
//获得二叉树高度，根节点层为0
func ( this  *binaryTree) GetHeight()  int  {
     return  this .root.height
}
                                                                                                                                                        
//获得第一个与数据e相等的节点
func ( this  *binaryTree) Find(e  interface {}) *BinTreeNode {
     if  this .root == nil {
         return  nil
     }
     p :=  this .root
     return  isEqual(e, p)
}
                                                                                                                                                       
func isEqual(e  interface {}, node *BinTreeNode) *BinTreeNode {
     if  e == node.GetData() {
         return  node
     }
                                                                                                                                                       
     if  node.HasLChild() {
         lp := isEqual(e, node.GetLChild())
         if  lp != nil {
             return  lp
         }
     }
                                                                                                                                                       
     if  node.HasRChild() {
         rp := isEqual(e, node.GetRChild())
         if  rp != nil {
             return  rp
         }
                                                                                                                                                       
     }
                                                                                                                                                       
     return  nil
}
                                                                                                                                                       
//先序遍历，并保存在链表里
func ( this  *binaryTree) PreOrder() *list.List {
     traversal := list.New()
     preOrder( this .root, traversal)
     return  traversal
}
                                                                                                                                                       
func preOrder(rt *BinTreeNode, l *list.List) {
     if  rt == nil {
         return
     }
     l.PushBack(rt)
     preOrder(rt.GetLChild(), l)
     preOrder(rt.GetRChild(), l)
}
                                                                                                                                                       
//中序遍历，并保存在链表里
func ( this  *binaryTree) InOrder() *list.List {
     traversal := list.New()
     inOrder( this .root, traversal)
     return  traversal
}
                                                                                                                                                       
func inOrder(rt *BinTreeNode, l *list.List) {
     if  rt == nil {
         return
     }
     inOrder(rt.GetLChild(), l)
     l.PushBack(rt)
     inOrder(rt.GetRChild(), l)
}
                                                                                                                                                       
//后序遍历，并保存在链表里
func ( this  *binaryTree) PostOrder() *list.List {
     traversal := list.New()
     postOrder( this .root, traversal)
     return  traversal
}
                                                                                                                                                        
func postOrder(rt *BinTreeNode, l *list.List) {
     if  rt == nil {
         return
     }
     postOrder(rt.GetLChild(), l)
     postOrder(rt.GetRChild(), l)
     l.PushBack(rt)
}


   上述遍历的过程显然是一个递归的过程，算法中是将结点加入链接表list的尾部作为对结点的访问，该操作只需要常数时间即可完成。在算法的递归执行过程中，每个结点访问且仅被访问一次，因此算法的时间复杂度T(n) = Ο(n)。对于中序和后序遍历的递归算法也是如此，即中序和后序递归算法的时间复杂度也是Ο(n)。

   

   下面做下测试，创建这么一棵二叉树：

wKioL1MoAnDBhw84AADvpshZg_k542.jpg

   测试代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
package  main
                                                                            
import  (
     "dataStructures/tree"
     "fmt"
)
                                                                            
func main() {
     a := tree.NewBinTreeNode( 1 )
     tree1 := tree.NewBinaryTree(a)
     a.SetLChild(tree.NewBinTreeNode( 2 ))
     a.SetRChild(tree.NewBinTreeNode( 5 ))
     a.GetLChild().SetRChild(tree.NewBinTreeNode( 3 ))
     a.GetLChild().GetRChild().SetLChild(tree.NewBinTreeNode( 4 ))
     a.GetRChild().SetLChild(tree.NewBinTreeNode( 6 ))
     a.GetRChild().SetRChild(tree.NewBinTreeNode( 7 ))
     a.GetRChild().GetLChild().SetRChild(tree.NewBinTreeNode( 9 ))
     a.GetRChild().GetRChild().SetRChild(tree.NewBinTreeNode( 8 ))
                                                                            
     node2 := a.GetLChild()
     node9 := a.GetRChild().GetLChild().GetRChild()
                                                                            
     fmt.Println( "结点2是叶子结点吗? " , node2.IsLeaf())
     fmt.Println( "结点9是叶子结点吗? " , node9.IsLeaf())
                                                                            
     fmt.Println( "这棵树的结点总数：" , tree1.GetSize())
                                                                            
     l := tree1.InOrder() //中序遍历
     for  e := l.Front(); e != nil; e = e.Next() {
         obj, _ := e.Value.(*tree.BinTreeNode)
         fmt.Printf( "data:%v\n" , *obj)
     }
     result := tree1.Find( 6 )
     fmt.Printf( "结点6的父节点数据：%v\t结点6的右孩子节点数据: %v\n" , result.GetParent().GetData(), result.GetRChild().GetData())
}


   结果：

wKiom1MoBAnDlJYJAAGF_ZD0tb8698.jpg

   看下中序遍历后，list内存储节点的顺序：2,4,3,1,6,9,5,7,8.符合这棵树中序遍历的结果。










本文转自 ponpon_ 51CTO博客，原文链接：http://blog.51cto.com/liuxp0827/1378672，如需转载请自行联系原作者
文章标签：
算法
Go
关键词：
数据结构二叉树
Go数据结构
Golang数据结构
数据结构golang
Golang二叉树
余二五
目录
相关文章
修己xj
|
12月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构，广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型（如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等）及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历，并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力，优化算法设计。
修己xj
372 10
算法系列之数据结构-二叉树
RossyYan
|
Java C++
【C++数据结构——树】二叉树的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数（简单示例，手动构建） TreeNode*create
RossyYan
430 12
2G冲浪词条
|
存储 安全 Go
Go语言中的map数据结构是如何实现的？
Go 语言中的 `map` 是基于哈希表实现的键值对数据结构，支持快速查找、插入和删除操作。其原理涉及哈希函数、桶（Bucket）、动态扩容和哈希冲突处理等关键机制，平均时间复杂度为 O(1)。为了确保线程安全，Go 提供了 `sync.Map` 类型，通过分段锁实现并发访问的安全性。示例代码展示了如何使用自定义结构体和切片模拟 `map` 功能，以及如何使用 `sync.Map` 进行线程安全的操作。
2G冲浪词条
425 9
RossyYan
|
C++
【C++数据结构——树】二叉树的性质（头歌实践教学平台习题）【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树，并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括： 1. **定义二叉树节点结构体**：定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**：通过解析括号表示串，递归地构建二叉树的各个节点及其子树。 3. **使用示例**：展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**： - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后，提供了测试说明及通关代
RossyYan
232 10
RossyYan
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法（头歌教学实验平台习题） 【合集】
本任务旨在实现二叉树的遍历，包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义，并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑，以及层次遍历中队列的应用。最后提供了测试用例和预期输出，确保代码正确性。通过这些内容，帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
RossyYan
602 3
三三是该溜子
|
数据库
数据结构中二叉树，哈希表，顺序表，链表的比较补充
二叉搜索树，哈希表，顺序表，链表的特点的比较
三三是该溜子
358 0
数据结构中二叉树，哈希表，顺序表，链表的比较补充
LucianaiB
|
机器学习/深度学习 存储 算法
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法，包括先序、中序、后序的递归与非递归遍历方法。通过编程实践，加深对二叉树结构的理解，学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
LucianaiB
398 4
ephemerals__
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
1414 9
java冯坚持
|
存储 算法 关系型数据库
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
这篇文章主要介绍了多路查找树的基本概念，包括二叉树的局限性、多叉树的优化、B树及其变体（如2-3树、B+树、B*树）的特点和应用，旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
java冯坚持
237 0
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
java冯坚持
|
存储 算法 搜索推荐
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
java冯坚持
367 0
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树

热门文章

最新文章

  • 1
    Golang发送邮件
  • 2
    golang实现版本号比较
  • 3
    使用Golang框架构建分布式系统
  • 4
    Golang函数
  • 5
    Golang各平台环境搭建实战
  • 6
    微服务注册中心注册表与hashcode实现golang版
  • 7
    golang操作文件
  • 8
    【微信公众号开发】基于golang的公众号开发——接入消息自动回复接口
  • 9
    03-Golang-常量与运算符
  • 10
    Golang深入浅出之-结构体标签（Tags）：JSON序列化与反射应用
  • 1
    基于 Go 语言跳表结构的局域网控制桌面软件进程管理算法研究
    227
  • 2
    go-dongle v1.1.7 发布，新增 SM4 国密分组对称加密算法支持
    302
  • 3
    go-dongle v1.1.7 发布，新增 SM4 国密分组对称加密算法支持
    304
  • 4
    防止员工泄密软件中文件访问日志管理的 Go 语言 B + 树算法
    165
  • 5
    如何管理员工上网：基于 Go 语言实现的布隆过滤器访问拦截算法应用
    239
  • 6
    【GoWails】Go做桌面应用开发？本篇文章带你上手Wails框架！一步步带你玩明白前后端双端的数据绑定！
    1030
  • 7
    【GoGin】（0）基于Go的WEB开发框架，GO Gin是什么？怎么启动？本文给你答案
    495
  • 8
    【GoGin】（1）上手Go Gin 基于Go语言开发的Web框架，本文介绍了各种路由的配置信息；包含各场景下请求参数的基本传入接收
    467
  • 9
    【Golang】（5）Go基础的进阶知识！带你认识迭代器与类型以及声明并使用接口与泛型！
    265
  • 10
    【Golang】（4）Go里面的指针如何？函数与方法怎么不一样？带你了解Go不同于其他高级语言的语法
    301

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • Go语言核心编程 - 基础语法、数组、切片、Map
  • Go语言核心编程 - 面向对象、文件、单元测试、反射、TCP编程
  • Go语言完全自学手册图文教程

    • 相关电子书

    更多
  • Go 构建日请求千亿级微服务的最佳实践
  • RocketMQ Client-GO 介绍
  • Apache Flink 流式应用中状态的数据结构定义升级

    • 推荐镜像

    更多
  • golang
    • 下一篇
    ECS账号安全防护最佳实践