当前位置: 首页 > article >正文

python 实现二叉搜索树的方法有哪些?

树的介绍

树不同于链表或哈希表,是一种非线性数据结构,树分为二叉树、二叉搜索树、B树、B+树、红黑树等等。

树是一种数据结构,它是由n个有限节点组成的一个具有层次关系的集合。用图片来表示的话,可以看到它很像一棵倒挂着的树。因此我们将这类数据结构统称为树,树根在上面,树叶在下面。一般的树具有以下特点:

  • 每个节点有0个或者多个子节点
  • 没有父节点的节点被称为根节点
  • 每个非根节点有且只有一个父节点
  • 每个子结点都可以分为多个不相交的子树

二叉树的定义是:每个节点最多有两个子节点。即每个节点只能有以下四种情况:

  1. 左子树和右子树均为空
  2. 只存在左子树
  3. 只存在右子树
  4. 左子树和右子树均存在

二叉搜索树

二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:

  • 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
  • 它的左右子树也分别为二叉搜索树

列举几种Python中几种常见的实现方式:

1.使用类和递归函数实现

通过定义一个节点类,包含节点值、左右子节点等属性,然后通过递归函数实现插入、查找、删除等操作。代码示例如下:

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
​
class BST:
    def __init__(self):
        self.root = None
​
    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert(value, self.root)
​
    def _insert(self, value, node):
        if value < node.data:
            if node.left is None:
                node.left = Node(value)
            else:
                self._insert(value, node.left)
        elif value > node.data:
            if node.right is None:
                node.right = Node(value)
            else:
                self._insert(value, node.right)
​
    def search(self, value):
        if self.root is None:
            return False
        else:
            return self._search(value, self.root)
​
    def _search(self, value, node):
        if node is None:
            return False
        elif node.data == value:
            return True
        elif value < node.data:
            return self._search(value, node.left)
        else:
            return self._search(value, node.right)
​
    def delete(self, value):
        if self.root is None:
            return False
        else:
            self.root = self._delete(value, self.root)
​
    def _delete(self, value, node):
        if node is None:
            return node
        elif value < node.data:
            node.left = self._delete(value, node.left)
        elif value > node.data:
            node.right = self._delete(value, node.right)
        else:
            if node.left is None and node.right is None:
                del node
                return None
            elif node.left is None:
                temp = node.right
                del node
                return temp
            elif node.right is None:
                temp = node.left
                del node
                return temp
            else:
                temp = self._find_min(node.right)
                node.data = temp.data
                node.right = self._delete(temp.data, node.right)
        return node
​
    def _find_min(self, node):
        while node.left is not None:
            node = node.left
        return node

2.使用列表实现

通过使用一个列表来存储二叉搜索树的元素,然后通过列表中元素的位置关系来实现插入、查找、删除等操作。代码示例如下:

class BST:
    def __init__(self):
        self.values = []
​
    def insert(self, value):
        if len(self.values) == 0:
            self.values.append(value)
        else:
            self._insert(value, 0)
​
    def _insert(self, value, index):
        if value < self.values[index]:
            left_child_index = 2 * index + 1
            if left_child_index >= len(self.values):
                self.values.extend([None] * (left_child_index - len(self.values) + 1))
            if self.values[left_child_index] is None:
                self.values[left_child_index] = value
            else:
                self._insert(value, left_child_index)
        else:
            right_child_index = 2 * index + 2
            if right_child_index >= len(self.values):
                self.values.extend([None] * (right_child_index - len(self.values) + 1))
            if self.values[right_child_index] is None:
                self.values[right_child_index] = value
            else:
                self._insert(value, right_child_index)
​
    def search(self, value):
        if value in self.values:
            return True
        else:
            return False
​
    def delete(self, value):
        if value not in self.values:
            return False
        else:
            index = self.values.index(value)
            self._delete(index)
            return True
​
    def _delete(self, index):
        left_child_index = 2 * index + 1
        right_child_index = 2 * index + 2
        if left_child_index < len(self.values) and self.values[left_child_index] is not None:
            self._delete(left_child_index)
        if right_child_index < len(self.values) and self.values[right_child_index] is not None:
            self

3.使用字典实现

其中字典的键表示节点值,字典的值是一个包含左右子节点的字典。代码示例如下:

def insert(tree, value):
    if not tree:
        return {value: {}}
    elif value < list(tree.keys())[0]:
        tree[list(tree.keys())[0]] = insert(tree[list(tree.keys())[0]], value)
    else:
        tree[list(tree.keys())[0]][value] = {}
    return tree
​
def search(tree, value):
    if not tree:
        return False
    elif list(tree.keys())[0] == value:
        return True
    elif value < list(tree.keys())[0]:
        return search(tree[list(tree.keys())[0]], value)
    else:
        return search(tree[list(tree.keys())[0]].get(value), value)
​
def delete(tree, value):
    if not search(tree, value):
        return False
    else:
        if list(tree.keys())[0] == value:
            if not tree[list(tree.keys())[0]]:
                del tree[list(tree.keys())[0]]
            elif len(tree[list(tree.keys())[0]]) == 1:
                tree[list(tree.keys())[0]] = list(tree[list(tree.keys())[0]].values())[0]
            else:
                min_key = min(list(tree[list(tree.keys())[0]+1].keys()))
                tree[min_key] = tree[list(tree.keys())[0]+1][min_key]
                tree[min_key][list(tree.keys())[0]] = tree[list(tree.keys())[0]]
                del tree[list(tree.keys())[0]]
        elif value < list(tree.keys())[0]:
            tree[list(tree.keys())[0]] = delete(tree[list(tree.keys())[0]], value)
        else:
            tree[list(tree.keys())[0]][value] = delete(tree[list(tree.keys())[0]].get(value), value)
    return tree

由于字典是无序的,因此该实现方式可能会导致二叉搜索树不平衡,影响插入、查找和删除操作的效率。

4.使用堆栈实现

使用堆栈(Stack)可以实现一种简单的二叉搜索树,可以通过迭代方式实现插入、查找、删除等操作。具体实现过程如下:

  1. 定义一个节点类,包含节点值、左右子节点等属性。
  2. 定义一个堆栈,初始时将根节点入栈。
  3. 当栈不为空时,取出栈顶元素,并对其进行操作:如果要插入的值小于当前节点值,则将要插入的值作为左子节点插入,并将左子节点入栈;如果要插入的值大于当前节点值,则将要插入的值作为右子节点插入,并将右子节点入栈;如果要查找或删除的值等于当前节点值,则返回或删除该节点。
  4. 操作完成后,继续从堆栈中取出下一个节点进行操作,直到堆栈为空。

需要注意的是,在这种实现方式中,由于使用了堆栈来存储遍历树的过程,因此可能会导致内存占用较高。另外,由于堆栈的特性,这种实现方式只能支持深度优先遍历(Depth-First Search,DFS),不能支持广度优先遍历(Breadth-First Search,BFS)。

以下是伪代码示例:

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
​
def insert(root, value):
    if not root:
        return Node(value)
    stack = [root]
    while stack:
        node = stack.pop()
        if value < node.data:
            if node.left is None:
                node.left = Node(value)
                break
            else:
                stack.append(node.left)
        elif value > node.data:
            if node.right is None:
                node.right = Node(value)
                break
            else:
                stack.append(node.right)
​
def search(root, value):
    stack = [root]
    while stack:
        node = stack.pop()
        if node.data == value:
            return True
        elif value < node.data and node.left:
            stack.append(node.left)
        elif value > node.data and node.right:
            stack.append(node.right)
    return False
​
def delete(root, value):
    if root is None:
        return None
    if value < root.data:
        root.left = delete(root.left, value)
    elif value > root.data:
        root.right = delete(root.right, value)
    else:
        if root.left is None:
            temp = root.right
            del root
            return temp
        elif root.right is None:
            temp = root.left
            del root
            return temp
        else:
            temp = root.right
            while temp.left is not None:
                temp = temp.left
            root.data = temp.data
            root.right = delete(root.right, temp.data)
    return root

以上是四种在Python中实现二叉搜索树的方法,在具体使用过程中还是需要合理选择,尽量以运行速度快、内存占用少为出发点,最后觉得有帮助的话请多多关注和赞同!!!

 


http://www.kler.cn/a/8173.html

相关文章:

  • LLaMA-Factory(二)界面解析
  • “AI 线索精益模型调用系统:开启精准营销新引擎
  • Go怎么做性能优化工具篇之基准测试
  • ubuntu22.04.5本地apt源部署
  • 将HTML转换为PDF:使用Spire.Doc的详细指南(一) 试用版
  • 【Leetcode 热题 100】124. 二叉树中的最大路径和
  • Unity中将项目通用的公共模块封装成类库dll
  • 如何让chatGPT变成中文-ChatGPT怎么完整输出
  • Spark 之 解析json的复杂和嵌套数据结构
  • 身临其境数字世界:探索VR全景元宇宙展厅
  • 前端学习:HTML链接
  • Linux小黑板(14):基于环形队列的生成消费者模型
  • 4款【新概念APP】对比+免费下载
  • 【开发工程师的运维小知识】docker安装gitlab
  • 【SQL Server】数据库开发指南(一)数据库设计
  • 生成式人工智能所面临的问题有哪些?
  • 苹果6信号不好的快速解决方法
  • 【多线程与高并发(锁)】1、锁的概念、分类和状态
  • Unity最新热更新框架 hybridclr_addressable
  • Obsidian:实现日记记录【设计并使用模板】
  • Linux-Shell设计
  • STM32CubeMXA安装和创建项目
  • CSS 扫盲
  • React Hooks精讲+案例
  • 使用Jmeter进行http接口测试
  • 【Unity项目实战】从零手戳一个背包系统