算法:二叉排序树的添加、查找和删除
算法 About 3,820 words定义节点和二叉排序树
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
}
Views: 1,729 · Posted: 2021-02-15
————        END        ————
Give me a Star, Thanks:)
https://github.com/fendoudebb/LiteNote扫描下方二维码关注公众号和小程序↓↓↓
Loading...