备案控制台
探索云世界
开发者社区 人工智能 文章 正文

Golang 数据结构实现之 二叉树

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

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

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

   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
关键词：
数据结构二叉树
Golang数据结构
数据结构golang
Go数据结构
Golang二叉树
余二五
目录
相关文章
憧憬blog
|
28天前
|
存储 算法 Go
Golang 数据结构：图
Golang 数据结构：图
憧憬blog
45 0
阿森要自信
|
16天前
|
算法
【算法与数据结构】二叉树（前中后）序遍历2
【算法与数据结构】二叉树（前中后）序遍历
阿森要自信
16 0
筱姌
|
1天前
二叉树和数据结构
二叉树和数据结构
筱姌
10 0
认真学习的小雅兰.
|
2天前
|
算法 DataX
二叉树（中）+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”
二叉树（中）+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”
认真学习的小雅兰.
5 0
阿森要自信
|
12天前
|
算法 索引
【算法与数据结构】深入二叉树实现超详解（全源码优化）
【算法与数据结构】深入二叉树实现超详解（全源码优化）
阿森要自信
26 1
阿森要自信
|
12天前
|
存储 算法
【算法与数据结构】深入解析二叉树（二）之堆结构实现
【算法与数据结构】深入解析二叉树（二）之堆结构实现
阿森要自信
22 1
快乐的流畅
|
23天前
|
存储 算法 程序员
【数据结构】【版本2.0】【树形深渊】——二叉树入侵
【数据结构】【版本2.0】【树形深渊】——二叉树入侵
快乐的流畅
69 2
泡沫o0
|
24天前
|
算法 C++ 开发者
【C/C++ 数据结构 】二叉树基本性质：具有n个结点的完全二叉树的深度为[log2n]+1或者[log2(n+1)]...
【C/C++ 数据结构 】二叉树基本性质：具有n个结点的完全二叉树的深度为[log2n]+1或者[log2(n+1)]...
泡沫o0
11 0
泡沫o0
|
24天前
|
存储 算法 C语言
【C/C++ 数据结构 树】探索C/C++中的二叉树：从理论到实践
【C/C++ 数据结构 树】探索C/C++中的二叉树：从理论到实践
泡沫o0
60 0
使者大牙
|
25天前
|
存储 算法 Python
数据结构与算法——二叉树介绍（附代码）
数据结构与算法——二叉树介绍（附代码）
使者大牙
21 3

热门文章

最新文章

  • 1
    深入Golang之Mutex
  • 2
    通过Golang获取公网IP地址
  • 3
    【C++ 数据结构与算法 一站式备考指南】一文掌握 数据结构与算法课程 知识点（二）
  • 4
    Java 学习路线：基础知识、数据类型、条件语句、函数、循环、异常处理、数据结构、面向对象编程、包、文件和 API
  • 5
    C++关联容器深度解析：提升数据结构操作的艺术
  • 6
    【数据结构】【版本2.0】【树形深渊】——二叉树入侵
  • 7
    【C/C++ 数据结构 】从零开始实现哈希表：C++实践指南
  • 8
    Java数据结构与算法-java数据结构与算法（二）
  • 9
    【C/C++ 数据结构 树】探索C/C++中的二叉树：从理论到实践
  • 10
    【软件设计师备考 专题 】数据结构深度解析：从数组到图
  • 1
    Go语言：多重返回值的神奇之处
    28
  • 2
    什么是协程（Goroutine）？探索Go语言并发的奇妙世界
    31
  • 3
    Go语言中如何判断map中是否包含某个key？
    46
  • 4
    Go语言中tag的用处及详细介绍
    33
  • 5
    Go语言中的int和int32：同一个概念吗？
    55
  • 6
    Go语言的接口比较：两个interface能否比较？
    74
  • 7
    Go语言GC(垃圾回收)的工作原理
    22
  • 8
    Go语言协程泄漏(Goroutine Leak)：原因和解决方案
    37
  • 9
    Go面向对象是如何实现的？
    27
  • 10
    Go中的GMP状态详解
    30

    • 相关课程

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

    • 相关电子书

    更多
  • Apache Flink 流式应用中状态的数据结构定义升级
  • gohbase ：HBase go客户端
  • Go构建日请求千亿级微服务实践

    • 推荐镜像

    更多
  • golang
  • nodejs-release
  • pypi
    • 下一篇
    阿里云oss简介和使用流程