算法:二叉排序树的添加、查找和删除
算法 大约 3820 字定义节点和二叉排序树
type BinarySortTree struct {
root *Node
}
type Node struct {
id int
left *Node
right *Node
}
添加
func (bt *BinarySortTree) Add(id int) {
if bt.root == nil {
bt.root = &Node{id: id}
} else {
bt.root.Add(id)
}
}
func (node *Node) Add(id int) {
n := &Node{id: id}
if id < node.id {
if node.left == nil {
node.left = n
} else {
node.left.Add(id)
}
} else {
if node.right == nil {
node.right = n
} else {
node.right.Add(id)
}
}
}
查找
查找指定节点。
func (bt *BinarySortTree) search(id int) *Node {
if bt.root == nil {
return nil
} else {
return bt.root.search(id)
}
}
func (node *Node) search(id int) *Node {
if node.id == id {
return node
}
if id < node.id { // 往左子树找
if node.left == nil {
return nil
}
return node.left.search(id)
} else {
if node.right == nil {
return nil
}
return node.right.search(id)
}
}
查找指定节点的父节点。
func (bt *BinarySortTree) searchParent(id int) *Node {
if bt.root == nil {
return nil
} else {
return bt.root.searchParent(id)
}
}
func (node *Node) searchParent(id int) *Node {
if node.left != nil && node.left.id == id || node.right != nil && node.right.id == id {
return node
} else {
if id < node.id && node.left != nil {
return node.left.searchParent(id)
} else if id > node.id && node.right != nil {
return node.right.searchParent(id)
} else {
return nil
}
}
}
删除
func (bt *BinarySortTree) delete(id int) {
if bt.root == nil {
return
}
targetNode := bt.search(id)
if targetNode == nil {
return
}
// 就只有一个root节点
if bt.root.left == nil && bt.root.right == nil {
bt.root = nil
return
}
parentNode := bt.searchParent(id)
// target 是叶子节点
if targetNode.left == nil && targetNode.right == nil {
if parentNode.left != nil && parentNode.left.id == targetNode.id { // 如果是parentNode的左节点
parentNode.left = nil
} else if parentNode.right != nil && parentNode.right.id == targetNode.id { // 如果是parentNode的右节点
parentNode.right = nil
}
} else if targetNode.left != nil && targetNode.right != nil { // 删除有两颗子树的节点
min := bt.delRightTreeMin(targetNode.right)
targetNode.id = min
} else { // 删除只有一颗子树的节点
// 如果要删除的节点有左子节点
if targetNode.left != nil {
if parentNode.left != nil {
// targetNode是parent的左子节点
if parentNode.left.id == id {
parentNode.left = targetNode.left
} else { // targetNode是parent的右子节点
parentNode.right = targetNode.left
}
} else {
bt.root = targetNode.left
}
} else { // 要删除的节点有右子节点
if parentNode.right != nil {
// targetNode是parent的左子节点
if parentNode.left != nil && parentNode.left.id == id {
parentNode.left = targetNode.right
} else { // targetNode是parent的右子节点
parentNode.right = targetNode.right
}
} else {
bt.root = targetNode.right
}
}
}
}
func (bt *BinarySortTree) delRightTreeMin(node *Node) int {
targetNode := node
// 循环查找左子节点,就会找到最小值
for targetNode.left != nil {
targetNode = targetNode.left
}
bt.delete(targetNode.id)
return targetNode.id
}
阅读 490 · 发布于 2021-02-15
————        END        ————
Give me a Star, Thanks:)
https://github.com/fendoudebb扫描下方二维码关注公众号和小程序↓↓↓

昵称:
随便看看
换一批
-
Java 中 sleep 和 wait 的区别阅读 624
-
PHP编译安装redis扩展阅读 1310
-
Ubuntu 系统升级 MySQL 版本阅读 1606
-
软考-系统架构设计师:微内核操作系统阅读 1580
-
使用 awk 提取 JSON 字符串中的字段阅读 6561
-
Chrome 打开开发者工具的几种方法阅读 1366
-
OpenJDK 配置使用 VisualVM阅读 1849
-
Prometheus+Grafana+redis_exporter 监控 Redis 服务阅读 308
-
软考-系统架构设计师:范围管理和时间管理阅读 972
-
JavaScript 判断 Android 还是 iOS阅读 332