二叉搜索树的结构如下:
// Binary Search Tree
type BST struct {
// Data interface{} 替换为interface可以支持多种数据类型
Val int
Left *BST
Right *BST
}
实现如下操作:
查找(递归/非递归)
删除
插入
最大值
最小值
代码:
package main
// Binary Search Tree
type BST struct {
// Data interface{}
Val int
Left *BST
Right *BST
}
// BST插入操作递归操作
func (node *BST) Insert(val int) {
if val node.Val { // 查找的值大于当前节点在右子树找
return node.Right.SearchRecursion(key)
}else if key key{
tree = tree.Left
}else {
tree = tree.Right
}
}
}
// BST最小值
func (node *BST) Min() int {
tree := node
for {
if tree.Left != nil {
tree = tree.Left
}else {
return tree.Val
}
}
}
// BST最大值
func (node *BST) Max() int {
tree := node
for {
if tree.Right != nil {
tree = tree.Right
}else {
return tree.Val
}
}
}
// BST删除操作
func (node *BST) Remove(key int) *BST {
if node == nil {
return nil
}
// 向左找
if key node.Val {
return node.Right.Remove(key)
}
// 如果该节点没左右子树直接删除
if node.Left == nil && node.Right == nil {
node = nil
return node
}
// 有右子树直接用右子树覆盖该节点
if node.Left == nil {
node = node.Right
return node
}
// 有左子树直接用左子树覆盖该节点
if node.Right != nil {
node = node.Left
return node
}
// 左右子树均存在， 找到右子树的最左节点替换当前节点
mostLeftMode := node.Right
for {
if mostLeftMode != nil && mostLeftMode.Left != nil {
mostLeftMode = mostLeftMode.Left
}else {
break
}
}
node.Val = mostLeftMode.Val
// 删除右子树的最左节点
node.Right = node.Right.Remove(node.Val)
return node
}
func main() {
}
作者：ClassmateLin