二叉查找树

发表于 | 分类于

Go 语言实现 二叉查找树。 日常笔记。原文

定义

二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
任意节点的左、右子树也分别为二叉查找树。
没有键值相等的节点（no duplicate nodes）。

实现

结构体

1
2
3
4
5
6
7
8
9
10
11
// 二叉查找树
type Tree struct {
	Root *Node
}
// 结点
type Node struct {
	Value int
	Left *Node
	Right *Node
	Parent *Node
}

添加一个结点

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
27
func (this *Tree) Insert(v int) {
	n := new(Node)
	n.Value = v
	if this.Root == nil {
		this.Root = n
		return
	}
	cur := this.Root
	for {
		n.Parent = cur
		if v < cur.Value {
			if cur.Left == nil {
				cur.Left = n
				break
			} else {
				cur = cur.Left
			}
		} else {
			if cur.Right == nil {
				cur.Right = n
				break
			} else {
				cur = cur.Right
			}
		}
	}
}

遍历树

1
2
3
4
5
6
7
8
9
10
11
func (this *Tree) Select() {
	var mapSearch func(n *Node)
	mapSearch = func(n *Node){
		if n != nil {
			mapSearch(n.Left)
			fmt.Println(n.Value)
			mapSearch(n.Right)
		}
	}
	mapSearch(this.Root)
}

查找一个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func (this *Tree) Search(v int) *Node{
	cur := this.Root
	for {
		if v < cur.Value {
			cur = cur.Left
			if cur == nil {
				return nil
			}
		} else if v > cur.Value {
			cur = cur.Right
			if cur == nil {
				return nil
			}
		} else {
			return cur
		}
	}
}

最小结点

1
2
3
4
5
6
7
8
9
10
func (this *Tree) Min() *Node{
	cur := this.Root
	for {
		if cur.Left != nil {
			cur = cur.Left
		} else {
			return cur
		}
	}
}

最大结点

1
2
3
4
5
6
7
8
9
10
func (this *Tree) Max() *Node{
	cur := this.Root
	for {
		if cur.Right != nil {
			cur = cur.Right
		} else {
			return cur
		}
	}
}

删除一个结点

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
func (this *Tree) Delete(v int) {
	fmt.Printf("del: %d\n",v)
	var (
		mapDel func (n *Node)
		cur = this.Search(v)
	)
	mapDel = func (cur *Node) {
		if cur == nil {
			return
		}
		if cur.Left == nil && cur.Right == nil {
			if cur.Parent.Left == cur {
				cur.Parent.Left = nil
			} else {
				cur.Parent.Right = nil
			}
		} else if cur.Left == nil && cur.Right != nil {
			cur.Right.Parent = cur.Parent
			if cur.Parent.Left == cur {
				cur.Parent.Left = cur.Right
			} else {
				cur.Parent.Right = cur.Right
			}
		} else if cur.Left != nil && cur.Right == nil {
			cur.Left.Parent = cur.Parent
			if cur.Parent.Left == cur {
				cur.Parent.Left = cur.Left
			} else {
				cur.Parent.Right = cur.Left
			}
		} else {
			fmt.Println("both")
			curs := cur.Right
			for {
				if curs.Left != nil {
					curs = curs.Left
				} else {
					break
				}
			}
			cur.Value = curs.Value
			mapDel(curs)
		}
	}
	mapDel(cur)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func main() {
	var t Tree
	t.Insert(100)
	t.Insert(120)
	t.Insert(80)
	t.Insert(70)
	t.Insert(90)
	t.Insert(85)
	t.Insert(95)
	t.Insert(110)
	t.Select()
	t.Delete(80)
	t.Select()
	fmt.Println("---------------")
	val := t.Search(110)
	fmt.Println(val)
	fmt.Println(t.Min())
	fmt.Println(t.Root.Value)
	fmt.Println(t.Root.Left.Value)
	fmt.Println(t.Root.Right.Value)
	t.Edit(80,125)
	t.Select()
}