二叉查找树

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

对于树中的每个节点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)
			}
		}
	}
}