blog/数据结构/用go实现二叉树.md

---
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断点调试查看插入结果![](https://s2.loli.net/2022/05/08/byvcQHTRGjgAEJ5.png)

## 二叉树节点查询

二叉树查询只需要依次比较大小进行判断就能找到需要的值
```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
}
```

## 节点遍历
节点遍历分为三种方式，分别为前序遍历，中序遍历，后续遍历

+ ### 前序遍历
    前序遍历访问顺序为当前节点，左节点，右节点
    我们通过递归的方式进行遍历
  ![](https://s2.loli.net/2022/05/08/F3Sds8P9KWaRoIp.png)
  该二叉树我们通过前序遍历的顺序为**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即可
  ![](https://s2.loli.net/2022/05/08/YrqLx5f6Gk2KeRH.png)


+ 节点的左右子节点都存在

    该情况需要进行节点交换，需要先获取到当前节点的右子节点的中序遍历的第一个节点，然后交换两个节点的值，如果该右子节点的前序遍历
    首节点存在右子节点，则继续获取并交换，知道将该节点交换到叶子节点。

  ![](https://s2.loli.net/2022/05/08/25dGitWVH7Zh38x.png)

    若将该二叉树的节点7删除，先需要获取右子节点的中序遍历守节点，因为节点9不存在左子节点，所以该节点就为9，我们就将节点9与节点7
    进行交换，因为仍不为叶子节点，所以继续获取，将节点11与节点7交换，最终交换结果为：
  ![](https://s2.loli.net/2022/05/08/m72bcweH8vX4z5h.png)
    我们直接将该叶子节点删除即可

```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