Python实现与理解：二叉搜索树(BST)

5星 · 超过95%的资源 121 浏览量更新于2024-08-31 收藏 108KB PDF 举报

"Python实现二叉搜索树是一种数据结构，其中每个节点包含一个父节点指针、一个左孩子指针、一个右孩子指针以及节点自身的数据。二叉搜索树的特性在于，每个节点的左子树中的所有节点值都小于该节点，而右子树中的所有节点值都大于该节点。这种数据结构支持高效地进行搜索、插入和删除操作，与列表的二分查找和哈希表类似。在Python中，我们可以创建一个类来实现二叉搜索树，提供类似于字典的接口，包括创建新树、添加键值对、获取值、删除键值对、检查键是否存在以及计算键值对的数量。通过遵循二叉搜索树的性质，可以确保数据的有效组织和快速访问。例如，插入节点时，新节点会根据其值相对于当前节点的大小被放置在正确的位置，保持树的平衡。在实际应用中，二叉搜索树常用于数据库索引和搜索算法，提供快速的数据查找功能。"

Python实现二叉搜索树实现二叉搜索树

二叉搜索树(二叉排序树)它的每个节点的数据结构为1个父节点指针,1个左孩子指针,1个有孩子指针,还有就是自

己的数据部分了,因为只有左右两孩子,所以才叫二叉树,在此基础上,该二叉树还满足另外一个条件:每个结点的左

孩子都不大于该结点&&每个结点的右孩子都大于该结点.

二叉搜索树二叉搜索树

我们已经知道了在一个集合中获取键值对的两种不同的方法。回忆一下这些集合是如何实现ADT（抽象数据类型）MAP的。

我们讨论两种ADT MAP的实现方式，基于列表的二分查找和哈希表。在这一节中，我们将要学习二叉搜索树，这是另一种键

指向值的Map集合，在这种情况下我们不用考虑元素在树中的实际位置，但要知道使用二叉树来搜索更有效率。

搜索树操作搜索树操作

在我们研究这种实现方式之前，让我们回顾一下ADT MAP提供的接口。我们会注意到，这种接口和Python的字典非常相似。

1. Map() 创建了一个新的空Map集合。

2. put(key,val) 在Map中增加了一个新的键值对。如果这个键已经在这个Map中了，那么就用新的值来代替旧的值。

3. get(key) 提供一个键，返回Map中保存的数据，或者返回None。

4. del 使用del map[key]这条语句从Map中删除键值对。

5. len() 返回Map中保存的键值对的数目

6. in 如果所给的键在Map中，使用key in map这条语句返回True。

搜索树实现搜索树实现

一个二叉搜索树，如果具有左子树中的键值都小于父节点，而右子树中的键值都大于父节点的属性，我们将这种树称为BST搜

索树。如之前所述的，当我们实现Map时，BST方法将引导我们实现这一点。图 1 展示了二叉搜索树的这一特性，显示的键没

有关联任何的值。注意这种属性适用于每个父节点和子节点。所有在左子树的键值都小于根节点的键值，所有右子树的键值都

大于根节点的键值。

图 1：一个简单的二叉搜索树

现在你知道什么是二叉搜索树了，我们再来看如何构造一个二叉搜索树，我们在搜索树中按图 1 显示的节点顺序插入这些键

值，图 1 搜索树存在的节点：70,31,93,94,14,23,73。因为 70 是第一个被插入到树的值，它是根节点。接下来，31 小于 70，

因此是 70 的左子树。接下来，93 大于 70，因此是 70 的右子树。我们现在填充了该树的两层，所以下一个键值，将会是 31

或者 93 的左子树或右子树。由于 94 大于 70 和 93，就变成了 93 的右子树。同样，14 小于 70 和 31，因此成为了 31 的左子

树。23 也小于 31，因此必须是 31 的左子树。然而，它大于 14，所以是 14 的右子树。

为了实现二叉搜索树，我们将使用节点和引用的方法，这类似于我们实现链表和表达式树的过程。因为我们必须能够创建和使

用一个空的二叉搜索树，所以我们将使用两个类来实现，第一个类我们称之为 BinarySearchTree，第二个类我们称之为

TreeNode。BinarySearchTree类有一个TreeNode类的引用作为二叉搜索树的根，在大多数情况下，外部类定义的外部方法只

需检查树是否为空，如果在树上有节点，要求BinarySearchTree类中含有私有方法把根定义为参数。在这种情况下，如果树

是空的或者我们想删除树的根，我们就必须采用特殊操作。BinarySearchTree类的构造函数以及一些其他函数的代码如Listing

1 所示。

Listing 1

class BinarySearchTree:

def __init__(self):

self.root = None

self.size = 0

def length(self):

下载后可阅读完整内容，剩余3页未读，立即下载

weixin_38707826

粉丝: 5
资源: 907

Python实现与理解：二叉搜索树(BST)

二叉搜索树的后序遍历序列，python，jupyter

Python实现二叉搜索树BST的方法示例

python实现二叉查找树实例代码

python实现二叉搜索树

Python实现二叉搜索树的删除功能

Python实现二叉搜索树查询功能

Python实现二叉搜索树的原理与操作

Python实现二叉搜索树：高效的Map集合实现方式

基于python实现二叉搜索树和Huffman树的原理

python实现二叉查找树1

最新资源