406 lines
9.3 KiB
Markdown
406 lines
9.3 KiB
Markdown
---
|
||
title: 用go实现二叉树
|
||
tags: 数据结构
|
||
categories: 数据结构, 二叉树
|
||
date: 2022-05-08 20:01:00
|
||
---
|
||
|
||
# 用go实现二叉树
|
||
|
||
> 二叉查找树（Binary Search Tree，简称BST）是一棵二叉树，它的左子节点的值比父节点的值要小，
|
||
右节点的值要比父节点的值大。它的高度决定了它的查找效率。在理想的情况下，二叉查找树增删查改的时间复杂度为O(logN)
|
||
(其中N为节点数），最坏的情况下为O(N)。当它的高度为logN+1时，我们就说二叉查找树是平衡的。
|
||
|
||
## 二叉树的构成
|
||
|
||
因为二叉树的节点需要可比较，所以定义了一个接口，包含了比较大小的方法和是否相等的方法
|
||
|
||
```go
|
||
|
||
// 实现该接口则代表可比较
|
||
type compare interface {
|
||
// 如果大于返回true,否则返回false
|
||
compare(data interface{}) bool
|
||
// 判断是否相等
|
||
equals(data interface{}) bool
|
||
}
|
||
|
||
// 二叉树节点
|
||
type BST struct {
|
||
// 节点值
|
||
data compare
|
||
// 左节点
|
||
LeftNode *BST
|
||
// 右节点
|
||
RightNode *BST
|
||
}
|
||
|
||
// 节点值得结构体，实现了compare接口
|
||
type data struct {
|
||
key int
|
||
value interface{}
|
||
}
|
||
|
||
func (d *data) equals(d1 interface{}) bool {
|
||
if d.key == d1.(*data).key {
|
||
return true
|
||
}
|
||
return false
|
||
}
|
||
|
||
func (d *data) compare(d1 interface{}) bool {
|
||
if d.key > d1.(*data).key {
|
||
return true
|
||
}
|
||
return false
|
||
}
|
||
```
|
||
|
||
## 二叉树的插入
|
||
|
||
二叉树的插入非常简单，先判断根节点是否为空，为空则直接作为根节点，
|
||
若不为空则找到需要插入位置的父节点，从根节点开始比较，小于则向左子节点靠近，
|
||
大于则靠近右子节点，找到插入位置的父节点后，再进行比较插入就行。
|
||
|
||
```go
|
||
// insert 插入
|
||
func (b *BST) insert(content compare) {
|
||
var parent *BST
|
||
temp := b
|
||
// 先判断根节点是否为空
|
||
if temp.data == nil {
|
||
temp.data = content
|
||
return
|
||
}
|
||
// 循环遍历找到父节点
|
||
for true {
|
||
// 当节点为null时，
|
||
if temp == nil {
|
||
break
|
||
}
|
||
parent = temp
|
||
// 如果当前节点值小于插入的值，则跳向左子节点
|
||
if temp.data.compare(content) {
|
||
temp = temp.LeftNode
|
||
} else {
|
||
temp = temp.RightNode
|
||
}
|
||
}
|
||
// 比较值，进行插入赋值
|
||
if parent.data.compare(content) {
|
||
parent.LeftNode = &BST{
|
||
data: content,
|
||
LeftNode: nil,
|
||
RightNode: nil,
|
||
}
|
||
} else {
|
||
parent.RightNode = &BST{
|
||
data: content,
|
||
LeftNode: nil,
|
||
RightNode: nil,
|
||
}
|
||
}
|
||
}
|
||
|
||
func main() {
|
||
bst := NewBST()
|
||
bst.insert(&data{
|
||
key: 3,
|
||
value: "123",
|
||
})
|
||
|
||
bst.insert(&data{
|
||
key: 2,
|
||
value: "234",
|
||
})
|
||
bst.insert(&data{
|
||
key: 1,
|
||
value: "345",
|
||
})
|
||
bst.insert(&data{
|
||
key: 4,
|
||
value: "456",
|
||
})
|
||
fmt.Println(bst)
|
||
}
|
||
```
|
||
通过goland断点调试查看插入结果
|
||
|
||
## 二叉树节点查询
|
||
|
||
二叉树查询只需要依次比较大小进行判断就能找到需要的值
|
||
```go
|
||
// 查询
|
||
func (b *BST) query(node compare) compare {
|
||
temp := b
|
||
for true {
|
||
// 判断节点是否为空
|
||
if temp == nil {
|
||
return nil
|
||
}
|
||
// 判断节点的值是否匹配
|
||
if temp.data.equals(node) {
|
||
return temp.data
|
||
}
|
||
// 根据节点值得大小移动当前位置
|
||
if temp.data.compare(node) {
|
||
temp = temp.LeftNode
|
||
} else {
|
||
temp = temp.RightNode
|
||
}
|
||
}
|
||
return nil
|
||
}
|
||
|
||
func main() {
|
||
bst := NewBST()
|
||
bst.insert(&data{
|
||
key: 3,
|
||
value: "123",
|
||
})
|
||
|
||
bst.insert(&data{
|
||
key: 2,
|
||
value: "234",
|
||
})
|
||
bst.insert(&data{
|
||
key: 1,
|
||
value: "345",
|
||
})
|
||
bst.insert(&data{
|
||
key: 4,
|
||
value: "456",
|
||
})
|
||
// &{4 456}
|
||
fmt.Println(bst.query(&data{key: 4}))
|
||
}
|
||
```
|
||
|
||
## 二叉树更新
|
||
更新二叉树节点得值和插入类似，依次遍历找到节点更新即可
|
||
|
||
```go
|
||
func (b *BST) update(node compare) error {
|
||
temp := b
|
||
for true {
|
||
if temp == nil {
|
||
return errors.New("not found")
|
||
}
|
||
if temp.data.equals(node) {
|
||
temp.data = node
|
||
return nil
|
||
}
|
||
|
||
if temp.data.compare(node) {
|
||
temp = temp.LeftNode
|
||
} else {
|
||
temp = temp.RightNode
|
||
}
|
||
}
|
||
return nil
|
||
}
|
||
```
|
||
|
||
## 节点遍历
|
||
节点遍历分为三种方式，分别为前序遍历，中序遍历，后续遍历
|
||
|
||
+ ### 前序遍历
|
||
前序遍历访问顺序为当前节点，左节点，右节点
|
||
我们通过递归的方式进行遍历
|
||
|
||
该二叉树我们通过前序遍历的顺序为**3 2 4 7 6 9**
|
||
|
||
```go
|
||
// 前序遍历
|
||
func (b *BST) frontItem(slice []compare) []compare {
|
||
if b.data == nil {
|
||
return nil
|
||
}
|
||
slice = append(slice, b.data)
|
||
if b.LeftNode != nil {
|
||
slice = b.LeftNode.frontItem(slice)
|
||
}
|
||
if b.RightNode != nil {
|
||
slice = b.RightNode.frontItem(slice)
|
||
}
|
||
return slice
|
||
}
|
||
```
|
||
|
||
+ ### 中序遍历
|
||
中序遍历访问顺序为当左子节点，当前节点，右子节点
|
||
前面的二叉树我们通过中序遍历的顺序为**2 3 4 7 6 9**
|
||
```go
|
||
// 中序遍历
|
||
func (b *BST) midItem(slice []compare) []compare {
|
||
if b.data == nil {
|
||
return nil
|
||
}
|
||
if b.LeftNode != nil {
|
||
slice = b.LeftNode.frontItem(slice)
|
||
}
|
||
slice = append(slice, b.data)
|
||
if b.RightNode != nil {
|
||
slice = b.RightNode.frontItem(slice)
|
||
}
|
||
return slice
|
||
}
|
||
```
|
||
|
||
+ ### 后序遍历
|
||
后序遍历访问顺序为左节点，右节点，当前节点
|
||
前面二叉树我们通过后续遍历访问顺序为**2 6 9 7 4 3**
|
||
|
||
```go
|
||
// 后序遍历
|
||
func (b *BST) rearItem(slice []compare) []compare {
|
||
if b.data == nil {
|
||
return nil
|
||
}
|
||
if b.LeftNode != nil {
|
||
slice = b.LeftNode.rearItem(slice)
|
||
}
|
||
if b.RightNode != nil {
|
||
slice = b.RightNode.rearItem(slice)
|
||
}
|
||
slice = append(slice, b.data)
|
||
return slice
|
||
}
|
||
```
|
||
|
||
## 二叉树删除
|
||
|
||
二叉树得删除分为三种情况
|
||
|
||
+ 节点左右子节点都为空
|
||
|
||
该情况只需要将该节点从父节点的指向删除即可
|
||
|
||
|
||
+ 节点的子节点有一个为空
|
||
|
||
该情况需要将该节点的唯一子节点根据大小连接向该节点的父节点
|
||
从该二叉树中删除节点6，只需要将节点7的左子节点指向5即可
|
||
|
||
|
||
|
||
+ 节点的左右子节点都存在
|
||
|
||
该情况需要进行节点交换，需要先获取到当前节点的右子节点的中序遍历的第一个节点，然后交换两个节点的值，如果该右子节点的前序遍历
|
||
首节点存在右子节点，则继续获取并交换，知道将该节点交换到叶子节点。
|
||
|
||
|
||
|
||
若将该二叉树的节点7删除，先需要获取右子节点的中序遍历守节点，因为节点9不存在左子节点，所以该节点就为9，我们就将节点9与节点7
|
||
进行交换，因为仍不为叶子节点，所以继续获取，将节点11与节点7交换，最终交换结果为：
|
||
|
||
我们直接将该叶子节点删除即可
|
||
|
||
```go
|
||
// 删除节点
|
||
func (b *BST) delete(node compare) error {
|
||
temp := b
|
||
if temp == nil {
|
||
return errors.New("root")
|
||
}
|
||
isRoot := false
|
||
var parent *BST
|
||
// 获取要删除节点的位置和父节点位置
|
||
for true {
|
||
// 判断节点是否为根节点
|
||
if b.data.equals(node) {
|
||
isRoot = true
|
||
break
|
||
}
|
||
// 判断节点的值的大小
|
||
if temp.data.compare(node) {
|
||
if temp.LeftNode == nil {
|
||
return errors.New("not found")
|
||
}
|
||
if temp.LeftNode.data.equals(node) {
|
||
parent = temp
|
||
temp = temp.LeftNode
|
||
break
|
||
} else {
|
||
temp = temp.LeftNode
|
||
}
|
||
} else {
|
||
if temp.RightNode == nil {
|
||
return errors.New("not found")
|
||
}
|
||
if temp.RightNode.data.equals(node) {
|
||
parent = temp
|
||
temp = temp.RightNode
|
||
break
|
||
} else {
|
||
temp = temp.RightNode
|
||
}
|
||
}
|
||
}
|
||
|
||
// case1: 删除节点即无左节点也无右节点
|
||
if temp.LeftNode == nil && temp.RightNode == nil {
|
||
if parent.data.compare(node) {
|
||
parent.LeftNode = nil
|
||
} else {
|
||
parent.RightNode = nil
|
||
}
|
||
return nil
|
||
|
||
// case2: 删除节点有左节点无右节点
|
||
} else if temp.LeftNode != nil && temp.RightNode == nil {
|
||
|
||
if isRoot {
|
||
b.data = temp.LeftNode.data
|
||
b.LeftNode = temp.LeftNode.LeftNode
|
||
b.RightNode = temp.LeftNode.RightNode
|
||
return nil
|
||
}
|
||
|
||
if parent.LeftNode == temp {
|
||
parent.LeftNode = temp.LeftNode
|
||
} else {
|
||
parent.RightNode = temp.LeftNode
|
||
}
|
||
return nil
|
||
|
||
// case3: 删除节点有右节点无左节点
|
||
} else if temp.LeftNode == nil && temp.RightNode != nil {
|
||
if isRoot {
|
||
b.data = temp.RightNode.data
|
||
b.LeftNode = temp.RightNode.LeftNode
|
||
b.RightNode = temp.RightNode.RightNode
|
||
return nil
|
||
}
|
||
if parent.LeftNode == temp {
|
||
parent.LeftNode = temp.RightNode
|
||
} else {
|
||
parent.RightNode = temp.RightNode
|
||
}
|
||
return nil
|
||
|
||
// case3: 删除节点有右节点有左节点
|
||
} else {
|
||
for temp.RightNode != nil {
|
||
firstMidNode := temp.RightNode.firstMidNode()
|
||
firstMidNode.data, temp.data = temp.data, firstMidNode.data
|
||
temp = firstMidNode
|
||
}
|
||
return b.delete(node)
|
||
}
|
||
}
|
||
|
||
// 获取中序遍历第一个节点
|
||
func (b *BST) firstMidNode() *BST {
|
||
temp := b
|
||
for true {
|
||
if temp.LeftNode == nil {
|
||
return temp
|
||
}
|
||
temp = temp.LeftNode
|
||
}
|
||
return nil
|
||
}
|
||
```
|
||
|
||
## 个人博客 https://shhy.xyz |