内容简介:前几天Redis的作者antirez说他朋友面试的时候考到排序问题,然后他说要是他也会考实现一个二叉搜索树,我说在中国某公司,据说面试直接就撸一个红黑树。不是说你技术渣,试问在座的各位有几个现在直接裸写出红黑树?红黑树太过偏门,但是常用的二叉搜索树你能写出来吗?快排呢?堆排序呢?二叉搜索树(binary search tree,
前几天 Redis 的作者antirez说他朋友面试的时候考到 排序 问题,然后他说要是他也会考实现一个二叉搜索树,我说在中国某公司,据说面试直接就撸一个红黑树。不是说你技术渣,试问在座的各位有几个现在直接裸写出红黑树?
红黑树太过偏门,但是常用的二叉搜索树你能写出来吗?快排呢?堆排序呢?
什么是二叉搜索树
二叉搜索树(binary search tree, BST )也叫排序的二叉树,根节点比左边子树的所有节点都大,比右边子树上的所有节点都小,如下图就是一个二叉搜索树:
要实现一个二叉搜索树, 我们需要实现节点的插入和删除,要实现节点的查找(搜索),要实现前序遍历、中序遍历和后序遍历,要实现最大节点和最小节点的查找。
下面就让我们实现这个二叉搜索树。
定义基本数据结构
常规地,我们定义节点的类型,每个节点包含它的值以及左右节点。因为目前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) // 后 } }
是不是你还可以通过广度搜索按照层级进行遍历?
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 海量数据搜索---搜索引擎
- 海量数据搜索——搜索引擎
- excel vba 实现跨表单(sheet) 搜索 - 显示搜索行记录搜索历史
- 深度优先搜索和广度优先搜索
- 图解:深度优先搜索与广度优先搜索
- GitLab 搜索利器,代码搜索工具 Kooder 发布
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
图片转BASE64编码
在线图片转Base64编码工具
URL 编码/解码
URL 编码/解码