用go实现一个二叉搜索树

二叉搜索树，又叫二叉查找树、二叉排序树。

它是这样的一种二叉树：

• 若左子树不为空，则左子树上的所有值都比它的根节点的值小
• 若右子树不为空，则右子树上的所有值都比它的根节点的值大
• 左右子树又都是一个二叉搜索树

由于它的性质，查找一个值时，先从根节点开始，如果根节点的值就是要找的值则直接返回，如果根节点的值大于要找的值，则查找左节点，否则查找右节点，重复这样的过程，直到找到或找不到，这也就是二分查找。树的最左侧可以找到这棵树上的最小值，树的最右侧可以找到这棵树的最大值。

查找一个值的平均时间复杂度为 \(O(logn)\)，最好的情况查找1次即可，最差的情况查找次数为树的高度（层次）。

它有个缺点，不平衡（左右子树上的节点数量不均衡），查找效率不稳定，极端情况下可以退化为一个链表，查找的时间复杂度也就退化为了 \(O(n)\)。

下面用 go 实现了一个二叉搜索树，功能包含：

• 插入元素
• 批量插入元素
• 删除元素
• 中序遍历（左子树->根节点->右子树）
• 前序遍历（根节点->左子树->右子树）
• 后序遍历（左子树->右子树->根节点）
• 获取树的高度
• 查找最大的元素
• 查找最小的元素
• 获取指定元素
• 检查是否包含指定值
• 查找指定值的父节点
• 检查树是否为空
• 检查与其它树是否相同
• 清空树

我们先定义一下节点：

// 定义节点
type TreeNode struct {
	value int
	left  *TreeNode
	right *TreeNode
}

// 对节点中序遍历，即左子树、中节点、右子树的顺序
func (node *TreeNode) inOrder() []int {
	res := []int{}
	if node != nil {
		if node.left != nil {
			res = append(res, node.left.inOrder()...)
		}
		res = append(res, node.value)
		if node.right != nil {
			res = append(res, node.right.inOrder()...)
		}
	}
	return res
}

// 对节点前序遍历，即中节点、左子树、右子树的顺序
func (node *TreeNode) preOrder() []int {
	res := []int{}
	if node != nil {
		res = append(res, node.value)
		if node.left != nil {
			res = append(res, node.left.preOrder()...)
		}
		if node.right != nil {
			res = append(res, node.right.preOrder()...)
		}
	}
	return res
}

// 对节点后序遍历，即左子树、右子树、中节点的顺序
func (node *TreeNode) postOrder() []int {
	res := []int{}
	if node != nil {
		if node.left != nil {
			res = append(res, node.left.postOrder()...)
		}
		if node.right != nil {
			res = append(res, node.right.postOrder()...)
		}
		res = append(res, node.value)
	}
	return res
}

// 获取节点的高度
func (node *TreeNode) height() int {
	if node == nil {
		return 0
	}

	leftHeight, rightHeight := 1, 1 // 包含自身的左、右子树的高度
	if node.left != nil {
		leftHeight += node.left.height()
	}
	if node.right != nil {
		rightHeight += node.right.height()
	}
	if leftHeight >= rightHeight {
		return leftHeight
	}
	return rightHeight
}

// 获得此节点及子树上的最小值
func (node *TreeNode) min() *TreeNode {
	if node == nil {
		return nil
	}
	minNode := node
	for {
		if minNode.left == nil {
			// 自己再没有左节点了，则自己即为最小的
			return minNode
		}
		minNode = minNode.left
	}
}

// 获得此节点及子树上的最大值
func (node *TreeNode) max() *TreeNode {
	if node == nil {
		return nil
	}
	maxNode := node
	for {
		if maxNode.right == nil {
			// 自己再没有左节点了，则自己即为最小的
			return maxNode
		}
		maxNode = maxNode.right
	}
}

func (node *TreeNode) walk(ch chan int) {
	if node == nil {
		return
	}
	node.left.walk(ch)
	ch <- node.value
	node.right.walk(ch)
}

func (node *TreeNode) walker() <-chan int {
	ch := make(chan int)
	go func() {
		node.walk(ch)
		close(ch)
	}()
	return ch
}

然后我们定义一个二叉搜索树：

// 定义二叉搜索树
type BinarySearchTree struct {
	root *TreeNode
}

// 插入数据
func (tree *BinarySearchTree) insert(v int) {
	// 从顶往下插
	if tree.root == nil {
		tree.root = &TreeNode{
			value: v,
			left:  nil,
			right: nil,
		}

		return
	}
	node := tree.root
	for {
		if node == nil {
			// 节点不存在，创建新节点
			node = &TreeNode{
				value: v,
				left:  nil,
				right: nil,
			}
			return
		}
		if node.value == v {
			// 已经存在
			return
		}
		if node.value > v {
			// 往左子树上插
			if node.left == nil {
				node.left = &TreeNode{
					value: v,
					left:  nil,
					right: nil,
				}
				return
			}
			node = node.left
		} else {
			if node.right == nil {
				node.right = &TreeNode{
					value: v,
					left:  nil,
					right: nil,
				}
				return
			}
			node = node.right
		}
	}
}

// 插入数据
func (tree *BinarySearchTree) insertMany(vs ...int) {
	// 从顶往下插
	for _, v := range vs {
		tree.insert(v)
	}
}

// 删除数据
func (tree *BinarySearchTree) remove(v int) {
	node := tree.getNode(v)
	if node == nil {
		// 要删除的节点不存在
		return
	}
	nodeParent := tree.searchParent(node.value)

	// 找到节点了，但是得看看情况怎么删除
	if node.left == nil && node.right != nil {
		if nodeParent == nil {
			// 节点为根节点
			node.right = nil
			return
		}
		// 只有右节点，右节点直接接替 node 的位置
		if nodeParent.left == node {
			// node 在 parent的左子树上
			nodeParent.left = node.right
		} else {
			// node 在 parent 的右子树上
			nodeParent.right = node.right
		}
		// 孤立node，也即删除了node
		node.right = nil

	} else if node.left != nil && node.right == nil {
		// 只有左节点，左节点直接接替 node 的位置
		if nodeParent == nil {
			// 节点为根节点
			node.left = nil
			return
		}

		if nodeParent.left == node {
			// node 在 parent的左子树上
			nodeParent.left = node.left
		} else {
			nodeParent.right = node.left
		}
		node.left = nil
	} else if node.left != nil && node.right != nil {
		// 左右节点都有
		//把右子树上的最小节点放到当前节点
		rightMinNode := node.right.min()
		// 把右边最小的节点删掉
		tree.remove(rightMinNode.value)
		node.value = rightMinNode.value
	} else {
		if nodeParent == nil {
			// 节点为根节点
			tree.root = nil
			return
		}
		// 没有子节点，即其为叶子节点
		if nodeParent.left == node {
			nodeParent.left = nil
		} else {
			nodeParent.right = nil
		}
	}
}

// 中序遍历
func (tree *BinarySearchTree) inOrderTraverse() []int {
	return tree.root.inOrder()
}

// 前序遍历
func (tree *BinarySearchTree) preOrderTraverse() []int {
	return tree.root.preOrder()
}

// 后序遍历
func (tree *BinarySearchTree) postOrderTraverse() []int {
	return tree.root.postOrder()
}

// 获取树的高度
func (tree *BinarySearchTree) getHeight() int {
	return tree.root.height()
}

// 搜索最小值
func (tree *BinarySearchTree) searchMin() *TreeNode {
	// 一直往左子树找就可以了
	return tree.root.min()
}

// 搜索最大值
func (tree *BinarySearchTree) searchMax() *TreeNode {
	// 一直往右子树找就可以了
	return tree.root.max()
}

// 查找是否存在指定值
func (tree *BinarySearchTree) getNode(v int) *TreeNode {
	node := tree.root
	for {
		// 到头了
		if node == nil {
			return nil
		}
		// 找到了
		if node.value == v {
			return node
		}
		if v < node.value {
			// 要找的值偏小，往左边查找
			node = node.left
		} else {
			// 要找的值偏大，往右边查找
			node = node.right
		}
	}
}

// 查找是否存在指定值
func (tree *BinarySearchTree) contains(v int) bool {
	return tree.getNode(v) != nil
}

// 查找指定值的父节点
func (tree *BinarySearchTree) searchParent(v int) *TreeNode {
	node := tree.root
	for {
		if node == nil || node.value == v {
			return nil
		}

		if v < node.value {
			// 要查找的值比当前节点小，则它可能在当前节点的左子树上
			left := node.left
			if left == nil {
				// 左节点为空，找不到
				return nil
			}
			if v == left.value {
				// 找到了
				return node
			}
			node = left
		} else {
			// 要查找的值比当前节点大，则它可能在当前节点右子树上
			right := node.right
			if right == nil {
				// 右节点为空，找不到
				return nil
			}
			if v == right.value {
				// 找到了
				return node
			}
			node = right
		}
	}
}

// 树是否为空
func (tree *BinarySearchTree) isEmpty() bool {
	return tree.root == nil
}

// 是否和另外一个树相同
func (tree *BinarySearchTree) sameWith(another *BinarySearchTree) bool {

	c1, c2 := tree.root.walker(), another.root.walker()
	for {
		v1, ok1 := <-c1
		v2, ok2 := <-c2
		if !ok1 || !ok2 {
			// 至少一个遍历到头了，需要结束掉
			// 都到头的话，相同
			return ok1 == ok2
		}
		if v1 != v2 {
			// 值不同的话，结束，两个树肯定不同
			break
		}
	}
	return false
}

// 清空树
func (tree *BinarySearchTree) clear() {
	tree.root = nil
}

func main() {
	var tree BinarySearchTree

	tree.insertMany(13, 15, 41, 58, 60, 22, 33, 37)
	fmt.Printf("inorder,%v \n", tree.inOrderTraverse())              // inorder,[13 15 22 33 37 41 58 60]
	fmt.Printf("preorder,%v \n", tree.preOrderTraverse())            // preorder,[13 15 41 22 33 37 58 60]
	fmt.Printf("postorder,%v \n", tree.postOrderTraverse())          // postorder,[37 33 22 60 58 41 15 13]
	fmt.Printf("min,%v \n", tree.searchMin().value)                  // min,13
	fmt.Printf("max,%v \n", tree.searchMax().value)                  // max,60
	fmt.Printf("contains 15? %t \n", tree.contains(15))              // contains 15? true
	fmt.Printf("contains 50? %t \n", tree.contains(50))              // contains 50? false
	fmt.Printf("contains height, %v \n", tree.getHeight())           // contains height, 6
	fmt.Printf("find 22 parent, %v \n", tree.searchParent(22).value) // find 22 parent, 41
	fmt.Printf("find 37 parent, %v \n", tree.searchParent(37).value) // find 37 parent, 33
	fmt.Printf("find 33 parent, %v \n", tree.searchParent(33).value) // find 33 parent, 22

	var anotherTree BinarySearchTree
	anotherTree.insertMany(13, 15, 41, 58, 60, 22, 33, 37)
	fmt.Printf("same with another tree? %t \n", tree.sameWith(&anotherTree)) // same with another tree? true
	anotherTree.insert(3)
	fmt.Printf("same with another tree? %t \n", tree.sameWith(&anotherTree)) // same with another tree? false

	tree.remove(41)
	fmt.Printf("inorder after 41 removed,%v \n", tree.inOrderTraverse()) // inorder after 41 removed,[13 15 22 33 37 58 60]
	tree.remove(22)
	fmt.Printf("inorder after 22 removed,%v \n", tree.inOrderTraverse()) // inorder after 22 removed,[13 15 33 37 58 60]
	tree.remove(33)
	fmt.Printf("inorder after 33 removed,%v \n", tree.inOrderTraverse()) // inorder after 33 removed,[13 15 37 58 60]
}

二叉搜索树的最终形态和插入元素的顺序有关，如上面输入的元素顺序为 13, 15, 41, 58, 60, 22, 33, 37，真实的形态为：

当插入元素的顺序为 41, 15, 58, 13, 60, 22, 37, 33时，其真实的形态为：

当顺序插入元素时，二叉搜索树就退化为了一个单链表。

因此，二叉搜索树不是平衡树，查找效率并不稳定。如果要求一个查找效率稳定的二叉搜索树就需要使用平衡二叉搜索树（AVL树）。