算法：二叉排序树的添加、查找和删除

定义节点和二叉排序树

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
}