Golang实现一个可存放重复元素的二叉搜索树，结合Morris算法

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
}

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)
	}
}