Go语言数据结构和算法-BinarySearchTree(二叉搜索树)

9/5/2018 Go算法

Go语言数据结构和算法-BinarySearchTree(二叉搜索树)Insert(val) // 在二叉搜索树中插入一个元素Search(val) // 在二叉搜索树中搜索一个元素Parent(val) // 返回当前节点的父节点 Contai

# Go语言数据结构和算法-BinarySearchTree(二叉搜索树)

Insert(val)         // 在二叉搜索树中插入一个元素
Search(val)         // 在二叉搜索树中搜索一个元素
Parent(val)         // 返回当前节点的父节点    
Contains(val)       // 在二叉搜索中是否包含这个元素
Min()               // 返回二叉搜索树中的最小的元素   
Max()               // 返回二叉搜索树中的最大的元素
Remove(val)         // 删除二叉搜索树中的一个元素
PreOrder()          // 前序遍历二叉搜索树
InOrder()           // 中序遍历二叉搜索树
PostOrder()         // 后续遍历二叉搜索树
1
2
3
4
5
6
7
8
9
10

# 二叉搜索树的数据结构

type Node struct {
	val   int
	left  *Node
	right *Node
}

type BinarySearchTree struct {
	root *Node
}
1
2
3
4
5
6
7
8
9

# Insert(val) 在二叉搜索树中插入一个元素

func (tree *BinarySearchTree) Insert(val int) {
	if tree.root == nil {
		tree.root = &Node{val, nil, nil}
	} else {
		insertNode(val, tree.root)
	}
}

func insertNode(val int, root *Node) {
	if val < root.val {
		if root.left == nil {
			root.left = &Node{val, nil, nil}
		} else {
			insertNode(val, root.left)
		}
	} else {
		if root.right == nil {
			root.right = &Node{val, nil, nil}
		} else {
			insertNode(val, root.right)
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# Search(val) 在二叉搜索树中搜索一个元素

func (tree *BinarySearchTree) Search(val int) *Node {
	if tree.root != nil {
		return findNode(val, tree.root)
	}
	return nil
}

func findNode(val int, root *Node) *Node {
	if val == root.val {
		return root
	} else if val < root.val {
		if root.left != nil {
			return findNode(val, root.left)
		}
	} else {
		if root.right != nil {
			return findNode(val, root.right)
		}
	}
	return nil
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# Parent(val) 返回当前节点的父节点

func (tree *BinarySearchTree) Parent(val int) *Node {
	if tree.root != nil {
		return findParent(val, tree.root)
	}
	return nil
}

func findParent(val int, root *Node) *Node {
	if val == root.val {
		return nil
	} else if val < root.val {
		if root.left != nil {
			if val == root.left.val {
				return root
			} else {
				return findParent(val, root.left)
			}
		}
	} else {
		if root.right != nil {
			if val == root.right.val {
				return root
			} else {
				return findParent(val, root.right)
			}
		}
	}
	return nil
}
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

# Contains(val) 在二叉搜索中是否包含这个元素

func (tree *BinarySearchTree) Contains(val int) bool {
	if tree.root != nil {
		return containNode(val, tree.root)
	}
	return false
}

func containNode(val int, root *Node) bool {
	if val == root.val {
		return true
	} else if val < root.val {
		if root.left == nil {
			return false
		} else {
			return containNode(val, root.left)
		}
	} else {
		if root.right == nil {
			return false
		} else {
			return containNode(val, root.right)
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# Min() 返回二叉搜索树中的最小的元素

func (tree *BinarySearchTree) Min() *Node {
	if tree.root != nil {
		return findMin(tree.root)
	}
	return nil
}

func findMin(root *Node) *Node {
	if root.left == nil {
		return root
	} else {
		return findMin(root.left)
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# Max() 返回二叉搜索树中的最大的元素

func (tree *BinarySearchTree) Max() *Node {
	if tree.root != nil {
		return findMax(tree.root)
	}
	return nil
}

func findMax(root *Node) *Node {
	if root.right == nil {
		return root
	} else {
		return findMax(root.right)
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# Remove(val) 删除二叉搜索树中的一个元素

func (tree *BinarySearchTree) Remove(val int) bool {
	nodeToRemoved := tree.Search(val)
	if nodeToRemoved == nil {
		return false
	}

	parent := tree.Parent(val)
	if tree.root.left == nil && tree.root.right == nil {
		tree.root = nil
		return true
	} else if nodeToRemoved.left == nil && nodeToRemoved.right == nil {
		if nodeToRemoved.val < parent.val {
			parent.left = nil
		} else {
			parent.right = nil
		}
	} else if nodeToRemoved.left == nil && nodeToRemoved.right != nil {
		if nodeToRemoved.val < parent.val {
			parent.left = nodeToRemoved.right
		} else {
			parent.right = nodeToRemoved.right
		}
	} else if nodeToRemoved.left != nil && nodeToRemoved.right == nil {
		if nodeToRemoved.val < parent.val {
			parent.left = nodeToRemoved.left
		} else {
			parent.right = nodeToRemoved.left
		}
	} else {
		largestValue := nodeToRemoved.left
		for largestValue.right != nil {
			largestValue = largestValue.right
		}
		tree.Remove(largestValue.val)
		nodeToRemoved.val = largestValue.val
	}

	return true
}
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

# PreOrder() 前序遍历二叉搜索树

func (tree *BinarySearchTree) PreOrder() {
	preOrder(tree.root)
}

func preOrder(root *Node) {
	if root != nil {
		fmt.Print(root.val, "->")
		preOrder(root.left)
		preOrder(root.right)
	}
}
1
2
3
4
5
6
7
8
9
10
11

# InOrder() 中序遍历二叉搜索树

func (tree *BinarySearchTree) InOrder() {
	inOrder(tree.root)
}

func inOrder(root *Node) {
	if root != nil {
		inOrder(root.left)
		fmt.Print(root.val, "->")
		inOrder(root.right)
	}
}
1
2
3
4
5
6
7
8
9
10
11

# PostOrder() 后续遍历二叉搜索树

func (tree *BinarySearchTree) PostOrder() {
	postOrder(tree.root)
}

func postOrder(root *Node) {
	if root != nil {
		postOrder(root.right)
		postOrder(root.left)
		fmt.Print(root.val, "->")
	}
}
1
2
3
4
5
6
7
8
9
10
11

源码 (opens new window)