二叉查找树二叉查找树
二叉查找树二叉查找树
月见樽
发布于 2018-04-27 12:08:38
发布于 2018-04-27 12:08:38
二叉查找树
二叉查找树是一种特殊的二叉树，该数据结构的核心性质是：
对于树中的每个节点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)
}
}
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017.12.14 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录