今天学习的时候看到一道题目是问在二叉搜索树如何存放重复值，借此机会顺便复习了一下二叉搜索树。二叉搜索树的中序遍历是有序的，它的左子树的所有节点的值都是小于它的，它的右子树的所有节点的值都是大于它的。在学习二叉树的遍历的时候，有一个大名鼎鼎的Morris算法，使用双指针就可以实现二叉树的前中后序遍历，并且时间复杂度是O(N)，空间复杂度是O(1)，于是我使用Golang实现一个可存放重复元素的二叉搜索树，并且结合Morris算法进行查找。
存放重复值的思路就是使用一个计数器计算值出现的次数，并在输出值的时候将重复元素同样的输出出来，但是二叉搜索树仍然是不重复的元素组成的。
一：二叉搜索树对象
代码语言：go复制package BinarySearchTree
// 实现一个可存放重复值的二叉搜索树，手写版, 20240306
// 思路：用计数器存放重复出现的次数，其他的跟二叉搜索树一样
type Bst_1 struct {
root *TreeNode
count map[int]int
}
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func NewBinarySearchTree20240306() *Bst_1 {
return &Bst_1{count: make(map[int]int)}
}
// 插入
func (this *Bst_1) Insert(val int) {
if this.root == nil {
this.root = &TreeNode{Val: val}
this.count[val]
return
}
if _,ok := this.count[val]; ok {
this.count[val]
return
}
this.insertNode(this.root, val)
this.count[val]
}
// 从某个节点出发插入一个节点
func (this *Bst_1) insertNode(node *TreeNode, val int) *TreeNode {
if node == nil {
return &TreeNode{Val: val}
}
if node.Val < val {
node.Right = this.insertNode(node.Right, val)
} else {
node.Left = this.insertNode(node.Left, val)
}
return node
}
// 查找值是否存在
func (this Bst_1) Search(val int) bool {
_,ok := this.count[val]
return ok
}
func (this *Bst_1) Delete(val int) bool {
cnt,ok := this.count[val]
if !ok {
return false
}
if cnt > 1 {
this.count[val]--
return true
}
// 开始删除
this.root = deleteFrom(this.root, val)
delete(this.count, val)
return true
}
// 从某个节点出发，删除某个值，提子树
func deleteFrom(node *TreeNode, val int) *TreeNode {
if node == nil {
return nil
}
if val < node.Val {
node.Left = deleteFrom(node.Left, val)
return node
} else if val > node.Val {
node.Right = deleteFrom(node.Right, val)
return node
}
// 相等就检查左右子树
if node.Left == nil && node.Right == nil {
return nil
}
if node.Left == nil {
return node.Right
}
if node.Right == nil {
return node.Left
}
// 左右子树都不为nil, 找到右子树的最小值(或者找到左子树的最大值)
res := node.Right
for res != nil && res.Left != nil {
res = res.Left
}
// 交换值, 然后删除这个节点
node.Val, res.Val = res.Val, node.Val
deleteFrom(node.Right, res.Val)
return node
}
// 获取中序遍历的结果, 就知道是否是有序的
func (this *Bst_1) GetSortedSequence() []int {
// Morris算法
res := []int{}
p1 := this.root
var p2 *TreeNode
for p1 != nil {
p2 = p1.Left
if p2 != nil {
for p2.Right != nil && p2.Right != p1 {
p2 = p2.Right
}
if p2.Right == nil {
p2.Right = p1
p1 = p1.Left
} else {
// 遍历完左子树了
cnt := this.count[p1.Val]
for cnt > 0 {
cnt--
res = append(res, p1.Val)
}
p2.Right = nil
p1 = p1.Right
}
} else {
cnt := this.count[p1.Val]
for cnt > 0 {
cnt--
res = append(res, p1.Val)
}
p1 = p1.Right
}
}
return res
}二：单元测试
思路:通过检查中序遍历是否有序来判断二叉搜索树是否实现正确
代码语言：go复制package BinarySearchTree
import (
"fmt"
"reflect"
"sort"
"testing"
)
func TestBst_1(t *testing.T) {
bst := NewBinarySearchTree20240306()
bst.Insert(2)
bst.Insert(1)
bst.Insert(4)
bst.Insert(4)
bst.Insert(3)
bst.Insert(3)
arr1 := bst.GetSortedSequence()
arr2 := make([]int, len(arr1))
copy(arr2, arr1)
sort.Ints(arr2)
if !reflect.DeepEqual(arr1, arr2) {
t.Errorf("错误, 因为不相同, arr1: %v, arr2: %v", arr1, arr2)
}
}
func TestBst_1Deleted(t *testing.T) {
bst := NewBinarySearchTree20240306()
bst.Insert(2)
bst.Insert(1)
bst.Insert(4)
bst.Insert(4)
bst.Insert(3)
bst.Insert(3)
bst.Delete(3)
bst.Delete(2)
arr1 := bst.GetSortedSequence()
arr2 := make([]int, len(arr1))
fmt.Println(bst.root)
fmt.Println(arr1)
copy(arr2, arr1)
sort.Ints(arr2)
if !reflect.DeepEqual(arr1, arr2) {
t.Errorf("错误, 因为不相同, arr1: %v, arr2: %v", arr1, arr2)
}
}三：结果
可以看到结果是正确的。
