二叉查找树

二叉查找树是一种特殊的二叉树，该数据结构的核心性质是：

对于树中的每个节点X，它的左子树中所有关键字值小于X的关键字值，而它的右子树中所有关键字值大于X的关键字值

二叉查找树ADT

• MakeEmpty：清空二叉查找树
• Find：给出关键字值，返回该关键字值的节点指针
• FindMin与FindMax：返回最小关键字值和最大关键字值的节点指针
• Insert：插入一个给定关键字值的节点
• Delete：删除一个指定关键字值的节点

代码实现

结构体

type tree_data struct {
    data int
}

type tree_node struct {
    num         int
    data        tree_data
    left_point  *tree_node
    right_point *tree_node
    parent      *tree_node
}

构造函数

func New_tree_node(num int, data tree_data, parent *tree_node) *tree_node {
    node := tree_node{}
    node.num = num
    node.data = data
    node.left_point = nil
    node.right_point = nil
    node.parent = parent
    return &node
}

清空方法

func (t *tree_node) MakeEmpty() {
    if t.left_point != nil {
        t.left_point.MakeEmpty()
    }
    if t.right_point != nil {
        t.right_point.MakeEmpty()
    }
    t.num = 0
    t.data = tree_data{}
}

查找方法

查找时：

• 当待查标号大于本节点标号时，向右子树查询
• 当待查标号小于本节点标号时，向左子树查询
• 当待查标号等于本节点标号时，命中，返回本节点指针

func (t *tree_node) Find(num int) (*tree_node, error) {
    if num > t.num {
        if t.right_point == nil {
            return &tree_node{}, errors.New("num not exsist")
        } else {
            return t.right_point.Find(num)
        }
    } else if num < t.num {
        if t.left_point == nil {
            return &tree_node{}, errors.New("num not exsist")
        } else {
            return t.left_point.Find(num)
        }
    } else {
        return t, nil
    }
}

查找最小值/最大值方法

func (t *tree_node) FindMin() *tree_node {
    if t.left_point != nil {
        return t.left_point.FindMin()
    } else {
        return t
    }
}
func (t *tree_node) FindMax() *tree_node {
    if t.right_point != nil {
        return t.right_point.FindMax()
    } else {
        return t
    }
}

插入方法

插入时：

• 当插入标号大于本节点标号，向右子树插入
• 当插入标号小于本节点标号，向左子树插入
• 当插入标号等于本节点标号，覆盖原值

func (t *tree_node) Insert(num int, data tree_data) {
    if num > t.num {
        if t.right_point != nil {
            t.right_point.Insert(num, data)
        } else {
            t.right_point = New_tree_node(num, data, t)
        }
    } else if num < t.num {
        if t.left_point != nil {
            t.left_point.Insert(num, data)
        } else {
            t.left_point = New_tree_node(num, data, t)
        }
    } else {
        t.data = data
    }
}

删除方法

删除时，若删除的是本节点，则：

• 当本节点没有子树（是树叶）时，直接将母节点指向该节点指针置nil（删除该节点）
• 当本节点仅有一个子树时，直接将本节点替换为子节点
• 当本节点有两个子树时，找到右节点的最小节点a，将本节点数据与标号替换为a节点的数据和标号，再递归的删除节点a

func (t *tree_node) Delete(num int) {
    if num < t.num {
        t.left_point.Delete(num)
    } else if num > t.num {
        t.right_point.Delete(num)
    } else {
        if t.left_point == nil && t.right_point == nil {
            if t.parent.left_point.num > t.num {
                t.parent.left_point = nil
            } else {
                t.parent.right_point = nil
            }
        } else {
            if t.left_point == nil {
                t.parent = t.right_point
            } else if t.right_point == nil {
                t.parent = t.left_point
            } else {
                temp := t.right_point.FindMin()
                t.num = temp.num
                t.data = temp.data
                temp.Delete(temp.num)
            }
        }
    }
}