二叉查找树
二叉查找树是一种特殊的二叉树,该数据结构的核心性质是:
对于树中的每个节点X,它的左子树中所有关键字值小于X的关键字值,而它的右子树中所有关键字值大于X的关键字值
二叉查找树ADT
- MakeEmpty:清空二叉查找树
- Find:给出关键字值,返回该关键字值的节点指针
- FindMin与FindMax:返回最小关键字值和最大关键字值的节点指针
- Insert:插入一个给定关键字值的节点
- Delete:删除一个指定关键字值的节点
代码实现
结构体
1 2 3 4 5 6 7 8 9 10 11
| 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 }
|
构造函数
1 2 3 4 5 6 7 8 9
| 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 }
|
清空方法
1 2 3 4 5 6 7 8 9 10
| 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{} }
|
查找方法
查找时:
- 当待查标号大于本节点标号时,向右子树查询
- 当待查标号小于本节点标号时,向左子树查询
- 当待查标号等于本节点标号时,命中,返回本节点指针
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| 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 } }
|
查找最小值/最大值方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| 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 } }
|
插入方法
插入时:
- 当插入标号大于本节点标号,向右子树插入
- 当插入标号小于本节点标号,向左子树插入
- 当插入标号等于本节点标号,覆盖原值
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| 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) } } } }
|