二叉查找树

1）二叉查找树是什么？
2）二叉查找树的插入、删除、查找？
3）Go代码实现

一、二叉查找树是什么？
二叉查找树（BST）又被称为搜索二叉树，有序二叉树，排序二叉树。它的特点就是，如果一个节点的左子不为空，则它的左子树都是小于这个节点值，如果这个节点的右子树不为空，则它的右子树都是不小于这个节点值，它的左右子树又是二叉排序树。

二、二叉查找树的插入、删除、查找？
关于插入和查找都是比较简单的
比较复杂的是删除，针对删除二叉查找树的节点，分为三种情况去操作，则可以将这个问题简单化
1、被删除节点没有左右子树
2、被删除节点只有左子树或者只有右子树
3、被删除节点有左右子树

针对第一种情况，只需要把该节点的双亲节点指向这个节点的指针设为空即可
针对第二种情况，只需要把该节点的双亲节点指向这个节点的不为空子树即可
针对第三种情况，有两种方案，把这个节点的左子树中最大的一个值，或这个节点的右子树中最小的一个值，赋值给当前节点的值，然后再把那个值删除

一个关于二叉查找树非常不错的视频

三、Go代码实现

package main

import "fmt"

type BST struct {
    val   *int
    left  *BST
    right *BST
}

func (b *BST)Insert(val int) {
    if b.val == nil {
        b.val = &val
    } else if *b.val > val {    // 左边
        if b.left == nil {
            b.left = &BST{val:&val}
        } else {
            b.left.Insert(val)
        }
    } else {
        if b.right == nil {
            b.right = &BST{val:&val}
        } else {
            b.right.Insert(val)
        }
    }
}

func (b *BST)Seach(val int) *BST {
    if b == nil {
        return nil
    }
    if val == *b.val {
        return b
    } else if val < *b.val {
        return b.left.Seach(val)
    }
    return b.right.Seach(val)
}

func (b *BST)SeachParentNote(val int) *BST {
    if b == nil {
        return nil
    }
    if (b.left != nil && *b.left.val == val) || (b.right != nil && *b.right.val == val) {
        return b
    }
    if *b.val > val {
        return b.left.SeachParentNote(val)
    }
    return b.right.SeachParentNote(val)
}

func (b *BST)Delete(val int) bool {
    var t = b.Seach(val)
    // 不存在
    if t == nil {
        return true
    }
    // 二叉查找树删除分以下三种情况
    // 1)删除叶子节点
    // 2)删除只有左子树或右子树
    // 3)删除有左右子树
    var pn = b.SeachParentNote(val)
    // 要删除的是根节点
    if pn == nil {
        if t.left == nil && t.right == nil {
            b.val = nil
        } else if (t.left != nil && t.right == nil) || (t.left == nil && t.right != nil) {
            b = t
        } else {
            var d = t.left
            for ;d.right != nil;d = d.right {}
            b.SeachParentNote(*d.val).Delete(*d.val)
            t.val = d.val
        }
        return true
    }
    // 要删除的不是根节点
    if pn != nil {
        if t.left == nil && t.right == nil {
            if pn.left == t {
                pn.left = nil
            } else {
                pn.right = nil
            }
        } else if (t.left != nil && t.right == nil) || (t.left == nil && t.right != nil) {
            if pn.left == t {
                if t.left != nil {
                    pn.left = t.left
                } else {
                    pn.left = t.right
                }
            } else if pn.right == t {
                if t.left != nil {
                    pn.right = t.left
                } else {
                    pn.right = t.right
                }
            }
        } else {
            var d = t.left
            for ;d.right != nil;d = d.right {}
            b.SeachParentNote(*d.val).Delete(*d.val)
            t.val = d.val
        }
        return true
    }
    return true
}

func main() {
    var b BST
    var s = []int{10,2,4,5,2,13}
    for i := 0;i < len(s);i++ {
        b.Insert(s[i])
    }
    fmt.Println(*b.val)
    b.Delete(10)
    fmt.Println(*b.val)
}