当前位置：首页 > news >正文

Go版数据结构 -【4.2 二叉搜索树】

news 来源：原创 2024/9/29 4:54:16

4.2 二叉搜索树

二叉搜索树（Binary Search Tree，简称 BST）是一种特殊的二叉树结构，它在上一节的基础上做了新的规则限制。

它的特性使得在进行查找、插入、删除等操作时效率非常高。二叉搜索树广泛应用于搜索、排序和数据存储等场景。

本节我们将介绍二叉搜索树的基本概念、其特有的规则以及在 Go 语言中的实现。

本节代码存放目录为 lesson7

概念及原理

二叉搜索树（BST） 是一种有序的二叉树，其每个节点都有以下特性：

左子树节点的值 小于 父节点的值。
右子树节点的值 大于 父节点的值。
对于每个节点，左子树和右子树 本身也都是二叉搜索树。

这样的性质使得我们可以在二叉搜索树上快速进行查找、插入、删除操作。

二叉搜索树的结构示意图如下所示：

        8/ \3   10/ \    \1   6   14/ \   /4   7 13

节点 8 是根节点，左子树上的所有节点都小于8，右子树上的所有节点都大于8。
节点 3 是8的左子节点，节点 10 是8的右子节点。
节点 1、6、14、4、7、13 也是遵循二叉搜索树的性质，左子节点小于父节点，右子节点大于父节点。

总的来说，对于二叉搜索树，我们只需要记住：左子小于父，右子大于父。

二叉搜索树具有以下几个重要特性：

查找操作：查找某个节点的过程类似于二分查找。我们根据值的大小决定是否向左子树或右子树递归查找，这样可以快速缩小查找范围。
插入操作：插入一个新值时，我们根据该值与当前节点的比较结果，递归找到合适的空位插入，确保二叉搜索树的有序性。
删除操作：删除节点时有三种情况：
- 节点没有子节点：直接删除该节点。
- 节点有一个子节点：删除节点后，直接将其子节点连接到父节点。
- 节点有两个子节点：找到该节点的中序后继节点，替换到被删除节点的位置，再递归删除后继节点。

与普通二叉树一样，二叉搜索树也可以使用前序遍历、中序遍历、后序遍历和层序遍历。特别是中序遍历，它会按照升序输出节点的值。

以上面的树为例，使用 中序遍历 的顺序就是从小到大依次输出节点值：

1 -> 3 -> 4 -> 6 -> 7 -> 8 -> 10 -> 13 -> 14

如何查找中序后继节点？

我么可以简单理解为：采用中序遍历后，第一个比当前节点大的节点。

比如在上面的中序遍历后，我们得到：

1 -> 3 -> 4 -> 6 -> 7 -> 8 -> 10 -> 13 -> 14

那么1的后继就是3，因为3是第一个比1大的；同理6的后继就是7，7的后继就是8。

删除操作示例

我们同样以上文的例子示范：

        8/ \3   10/ \    \1   6   14/ \   /4   7 13

首先我们删除13，由于13是没有任何子节点的，所以我们直接将13节点删除即可。此时结构如下：

        8/ \3   10/ \    \1   6   14/ \ 4   7

接下来我们删除10节点，由于10节点只有一个节点14，所以我们直接将14连接到父节点8即可。此时结构如下：

        8/ \3   14/ \   1   6/ \ 4   7

接下来我们删除6节点，由于6节点有两个子节点，所以我们需要找到6的中序后继节点，也就是7，之后我们将7替换到被删除的6节点。此时结构如下：

        8/ \3   14/ \   1   7/ \ 4   7

接下来我们需要删除原本的中序后继节点7。最终结构如下：

        8/ \3   14/ \   1   6/4

Go语言的实现

接下来我们使用 Go 语言实现二叉搜索树，包括插入、查找和删除等基本操作。

实现代码如下所示：

// Tree 定义树结构
type Tree struct {data  intleft  *Treeright *Tree
}func (t *Tree) insert(data int) {newTree := &Tree{data: data,}if data < t.data {if t.left == nil {t.left = newTree} else {t.left.insert(data)}} else {if t.right == nil {t.right = newTree} else {t.right.insert(data)}}
}func (t *Tree) search(data int) *Tree {if t == nil {return nil}if t.data == data {return t}// 递归查找左子树if data < t.data {return t.left.search(data)}// 递归查找右子树return t.right.search(data)
}func (t *Tree) delete(data int) *Tree {if t == nil {return nil}if data < t.data {// 递归左查找t.left = t.left.delete(data)} else if data > t.data {// 递归右查找t.right = t.right.delete(data)} else {// 没有任何子节点if t.left == nil && t.right == nil {return nil}// 只有一个子节点if t.left == nil {return t.right}if t.right == nil {return t.left}// 有两个子节点，那么需要找到中序后继节点minNode := t.right.findMin()// 用中序后继的值替换当前节点的值t.data = minNode.data// 删除中序后继节点t.right = t.right.delete(minNode.data)}return t
}// 查找最小节点（中序后继）
func (t *Tree) findMin() *Tree {if t.left == nil {return t}return t.left.findMin()
}// 中序遍历
func (t *Tree) inOrder() {if t == nil {return}t.left.inOrder()fmt.Printf("%d ", t.data)t.right.inOrder()
}func (t *Tree) printTree() {if t == nil {return}if t.left != nil {fmt.Printf("left: %d, ", t.left.data)}if t.right != nil {fmt.Printf("right-> %d\n", t.right.data)}if t.left == nil && t.right == nil {return}t.left.printTree()t.right.printTree()
}func main() {tree := &Tree{data: 8}tree.insert(3)tree.insert(10)tree.insert(1)tree.insert(6)tree.insert(14)tree.insert(4)tree.insert(7)tree.insert(13)tree.printTree()fmt.Println("\n中序遍历结果:")tree.inOrder()fmt.Println("\n\n查找节点 6")node := tree.search(6)if node != nil {fmt.Printf("找到节点: %d\n", node.data)} else {fmt.Println("节点不存在")}fmt.Println("\n删除节点 13 后的中序遍历结果:")tree = tree.delete(13)tree.inOrder()fmt.Println("\n删除节点 10 后的中序遍历结果:")tree = tree.delete(10)tree.inOrder()fmt.Println("\n删除节点 6 后的中序遍历结果:")tree = tree.delete(6)tree.inOrder()
}

执行结果输出如下：

left: 3, right-> 10
left: 1, right-> 6
left: 4, right-> 7
right-> 14
left: 13, 
中序遍历结果:
1 3 4 6 7 8 10 13 14 查找节点 6
找到节点: 6删除节点 13 后的中序遍历结果:
1 3 4 6 7 8 10 14 
删除节点 10 后的中序遍历结果:
1 3 4 6 7 8 14 
删除节点 6 后的中序遍历结果:
1 3 4 7 8 14

在上面的代码中我们实现了基本的插入、查询、删除、遍历，可能代码看起来不是太明白，我们可以先将递归了解清楚，我们主要使用的也就是递归的概念。

通过递归进行各种操作，所以代码看起来会比较抽象，我们可以拿到代码demo，去加一下日志输出详细查看一下他的整个过程。