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

Golang 数据结构实现之 二叉树

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

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

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

   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二叉树
余二五
目录
相关文章
ephemerals__
|
24天前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
78 8
java冯坚持
|
2月前
|
存储 算法 关系型数据库
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
这篇文章主要介绍了多路查找树的基本概念，包括二叉树的局限性、多叉树的优化、B树及其变体（如2-3树、B+树、B*树）的特点和应用，旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
java冯坚持
24 0
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
java冯坚持
|
2月前
|
存储 算法 搜索推荐
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
java冯坚持
26 0
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
GuGuStudy
|
2月前
|
Java
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（二）
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（二）
GuGuStudy
28 1
GuGuStudy
|
2月前
|
算法 Java C语言
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（一）
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（一）
GuGuStudy
25 1
努力学习的小廉
|
2月前
|
存储
【数据结构】二叉树链式结构——感受递归的暴力美学
【数据结构】二叉树链式结构——感受递归的暴力美学
努力学习的小廉
17 1
阿客不是客
|
2月前
|
存储 算法
探索数据结构：分支的世界之二叉树与堆
探索数据结构：分支的世界之二叉树与堆
阿客不是客
24 0
java冯坚持
|
2月前
|
存储 算法
数据结构与算法学习十六：树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识，包括树的存储方式、二叉树的定义、遍历方法（前序、中序、后序、层次遍历），以及二叉树的查找和删除操作。
java冯坚持
28 0
努力学习的小廉
|
2月前
|
存储 算法
【数据结构】二叉树——顺序结构——堆及其实现
【数据结构】二叉树——顺序结构——堆及其实现
努力学习的小廉
23 0
椰椰椰耶
|
2月前
|
存储
【数据结构】二叉树零基础无压力上手，超详解
【数据结构】二叉树零基础无压力上手，超详解
椰椰椰耶
28 0