二叉搜索树基本操作

我们先来重复下二叉搜索树的性质： 树是一个空树，或其满足以下条件：

• 对于任意一个节点，若左子树不为空，则左子树上所有节点的值均小于它的值
• 对于任意一个节点，若右子树不为空，则右子树上所有节点的值均大于它的值

先预定义节点类型：

type BTNode struct {
	Data  int
	Left  *BTNode
	Right *BTNode
}

话不多说，直接上增删改查的代码。

查找

可以直接利用二叉搜索树有序的特点进行二分搜索

func findNode(root *BTNode, val int) *BTNode {
	if root == nil {
		return nil
	}
	if root.Data > val {
		return findNode(root.Left, val)
	}
	if root.Data < val {
		return findNode(root.Right, val)
	}
	return root
}

插入

插入操作和查找操作类似，如果要插入的值存在的话什么都不用做，如果不存在的话，二分查找到大小最近的叶子节点，将自己挂到叶子节点下即可

func insertNode(root *BTNode, val int) *BTNode {
	if root == nil {
		return &BTNode{Data: val}
	}
	if root.Data > val {
		// 在右侧插入
		root.Right = insertNode(root.Right, val)
	} else if root.Data < val {
		// 在左侧插入
		root.Left = insertNode(root.Left, val)
	}
	return root
}

删除

删除操作稍复杂些，分一下可能遇到的情况：

1. 如果要删除的节点是叶子节点，切断父节点指向自己的指针即可
2. 如果要删除的节点是中间节点，需要将左子树中最大的节点放到当前位置，或者将右子树中最小的节点放到当前位置

// 查找最小节点
func findMinNode(root *BTNode) *BTNode {
	if root == nil {
		return nil
	}
	min := root
	leftMin := findMinNode(root.Left)
	if leftMin != nil && leftMin.Data < min.Data {
		return leftMin
	}
	return min
}

// 查找最大节点
func findMaxNode(root *BTNode) *BTNode {
	if root == nil {
		return nil
	}
	max := root
	rightMax := findMaxNode(root.Left)
	if rightMax != nil && rightMax.Data > max.Data {
		return rightMax
	}
	return max
}

// 删除节点，返回删除后的当前节点
func deleteNode(root *BTNode, val int) *BTNode {
	if root == nil {
		return nil
	}
	if root.Data < val {
		// 在右子树中删
		root.Right = deleteNode(root.Right, val)
	} else if root.Data > val {
		// 在左子树中删
		root.Left = deleteNode(root.Left, val)
	} else {
		// 删除当前节点
		if root.Left == nil && root.Right == nil {
			// 当前节点是叶子节点
			return nil
		}
		// 当前节点是中间节点，取左子树最大节点，如果取不到则取右子树最小节点，来代替当前节点

		// 查找右侧最小
		min := findMinNode(root.Right)
		if min == nil {
			// 右侧最小不存在，查找左侧最大
			max := findMaxNode(root.Left)
			if max != nil {
				root.Left = deleteNode(root.Left, max.Data)
				root.Data = max.Data
			}
		} else {
			// 移动 min 到当前位置，即删除min，将min 的值复制到当前节点
			root.Right = deleteNode(root.Right, min.Data)
			root.Data = min.Data
		}
	}
	return root
}

更新

更新操作不能直接修改节点的值，否则可能会不满足二叉搜索树的性质，因此要实现更新需要先删除后插入

func updateNode(root *BTNode, oldVal, newVal int) *BTNode {
	node := findNode(root, oldVal)
	if node == nil {
		// 要修改的不存在，什么都不做
		return root
	}
	root = deleteNode(root, oldVal)
	root = insertNode(root, newVal)
	return root
}