用Go撸一个二叉搜索树

栏目: IT技术 · 发布时间: 4年前

内容简介:前几天Redis的作者antirez说他朋友面试的时候考到排序问题,然后他说要是他也会考实现一个二叉搜索树,我说在中国某公司,据说面试直接就撸一个红黑树。不是说你技术渣,试问在座的各位有几个现在直接裸写出红黑树?红黑树太过偏门,但是常用的二叉搜索树你能写出来吗?快排呢?堆排序呢?二叉搜索树(binary search tree,

前几天 Redis 的作者antirez说他朋友面试的时候考到 排序 问题,然后他说要是他也会考实现一个二叉搜索树,我说在中国某公司,据说面试直接就撸一个红黑树。不是说你技术渣,试问在座的各位有几个现在直接裸写出红黑树?

红黑树太过偏门,但是常用的二叉搜索树你能写出来吗?快排呢?堆排序呢?

什么是二叉搜索树

二叉搜索树(binary search tree, BST )也叫排序的二叉树,根节点比左边子树的所有节点都大,比右边子树上的所有节点都小,如下图就是一个二叉搜索树:

用 <a href='https://www.codercto.com/topics/6127.html'>Go</a> 撸一个二叉搜索树

要实现一个二叉搜索树, 我们需要实现节点的插入和删除,要实现节点的查找(搜索),要实现前序遍历、中序遍历和后序遍历,要实现最大节点和最小节点的查找。

下面就让我们实现这个二叉搜索树。

定义基本数据结构

常规地,我们定义节点的类型,每个节点包含它的值以及左右节点。因为目前Go泛型还没有发布,所以这里我们实现一个元素为int类型的具体的二叉搜索树,等泛型实现后可以改成抽象的二叉搜索树。

树只要包含根节点可以了。

// Node 定义节点.
type Node struct {
	value int   // 因为目前Go的泛型还没有发布,所以我们这里以一个int具体类型为例
	left  *Node // 左子节点
	right *Node // 右子节点
}

// BST 是一个节点的值为int类型的二叉搜索树.
type BST struct {
	root *Node
}

数据结构有了,接下来就是实现各个方法。

插入和删除

既然是一棵树,就需要增加节点用来构造树,大部分情况下也需要删除节点。

增加节点的时候,需要判断应该往左边子树上添加,还是往右边子树上添加。天然地,既然二叉搜索树是一个有序的,那么我们就可以进行比较,然后递归的实现。

// Insert 插入一个元素.
func (bst *BST) Insert(value int) {
	newNode := &Node{value, nil, nil}

	// 如果二叉树为空,那么这个节点就当作跟节点
	if bst.root == nil {
		bst.root = newNode
	} else {
		insertNode(bst.root, newNode)
	}
}

// 从根节点依次比较
func insertNode(root, newNode *Node) {
	if newNode.value < root.value { // 应该放到根节点的左边
		if root.left == nil {
			root.left = newNode
		} else {
			insertNode(root.left, newNode)
		}
	} else if newNode.value > root.value { // 应该放到根节点的右边
		if root.right == nil {
			root.right = newNode
		} else {
			insertNode(root.right, newNode)
		}
	}

	// 否则等于根节点
}

删除有些麻烦,如果是删除叶节点就比较容易,删除即可。但是如果不是删除叶节点,那么就需要将子节点提升。


// Remove 删除一个元素.
func (bst *BST) Remove(value int) bool {
	_, existed := remove(bst.root, value)
	return existed
}

// 用来递归移除节点的辅助方法.
// 返回替换root的新节点,以及元素是否存在
func remove(root *Node, value int) (*Node, bool) {
	if root == nil {
		return nil, false
	}

	var existed bool
	// 从左边找
	if value < root.value {
		root.left, existed = remove(root.left, value)
		return root, existed
	}

	// 从右边找
	if value > root.value {
		root.right, existed = remove(root.right, value)
		return root, existed
	}

	// 如果此节点正是要移除的节点,那么返回此节点,同时返回之前可能需要调整.
	existed = true

	// 如果此节点没有孩子,直接返回即可
	if root.left == nil && root.right == nil {
		root = nil
		return root, existed
	}

	// 如果左子节点为空, 提升右子节点
	if root.left == nil {
		root = root.right
		return root, existed
	}
	// 如果右子节点为空, 提升左子节点
	if root.right == nil {
		root = root.left
		return root, existed
	}

	// 如果左右节点都存在,那么从左边节点找到一个最小的节点提升,这个节点肯定比左子树所有节点都大.
	// 也可以从左子树节点中找一个最大的提升,道理一样.

	smallestInRight, _ := min(root.right)
	// 提升
	root.value = smallestInRight
	// 从右边子树中移除此节点
	root.right, _ = remove(root.right, smallestInRight)

	return root, existed
}

搜索

检查一个节点是否存在比较简单,因为二叉搜索树是有序的。

// Search 搜索元素(检查元素是否存在)
func (bst *BST) Search(value int) bool {
	return search(bst.root, value)
}

func search(n *Node, value int) bool {
	if n == nil {
		return false
	}
	if value < n.value {
		return search(n.left, value)
	}
	if value > n.value {
		return search(n.right, value)
	}
	return true
}

同时,我们还可以实现查找一个二叉搜索树的最大最小值。

// Min 二叉搜索树中的最小值
func (bst *BST) Min() (int, bool) {
	return min(bst.root)
}

func min(node *Node) (int, bool) {
	if node == nil {
		return0, false
	}

	n := node
	// 从左边找
	for {
		if n.left == nil {
			return n.value, true
		}
		n = n.left
	}
}

// Max 二叉搜索树中的最大值
func (bst *BST) Max() (int, bool) {
	return max(bst.root)
}

func max(node *Node) (int, bool) {
	if node == nil {
		return0, false
	}

	n := node
	// 从右边找
	for {
		if n.right == nil {
			return n.value, true
		}
		n = n.right
	}
}

遍历

可以实现先序遍历、中序遍历和后序遍历,先中后指的是根节点相对子节点的处理顺序。

// PreOrderTraverse 前序遍历
func (bst *BST) PreOrderTraverse(f func(int)) {
	preOrderTraverse(bst.root, f)
}

func preOrderTraverse(n *Node, f func(int)) {
	if n != nil {
		f(n.value) // 前
		preOrderTraverse(n.left, f)
		preOrderTraverse(n.right, f)
	}
}

// PostOrderTraverse 后序遍历
func (bst *BST) PostOrderTraverse(f func(int)) {
	postOrderTraverse(bst.root, f)
}

func postOrderTraverse(n *Node, f func(int)) {
	if n != nil {
		postOrderTraverse(n.left, f)
		postOrderTraverse(n.right, f)
		f(n.value) // 后
	}
}

是不是你还可以通过广度搜索按照层级进行遍历?


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Haskell Programming from first principles

Haskell Programming from first principles

Christopher Allen、Julie Moronuki / 2015 / USD 59.00

I am writing this book because I had a hard time learning Haskell. It doesn't have to be that way. I've spent the last couple years actively teaching Haskell online and in person. Along the way, I ......一起来看看 《Haskell Programming from first principles》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器