位置: 编程技术 - 正文

Python实现二叉搜索树(python二叉树)

编辑:rootadmin

推荐整理分享Python实现二叉搜索树(python二叉树),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:验证二叉搜索树 python,python 二叉树遍历,python二叉搜索树建立,python二叉树算法,python 二叉搜索树,判断二叉搜索树的算法python,python二叉树算法,python二叉排序树怎么构造,内容如对您有帮助,希望把文章链接给更多的朋友!

二叉搜索树

我们已经知道了在一个集合中获取键值对的两种不同的方法。回忆一下这些集合是如何实现ADT(抽象数据类型)MAP的。我们讨论两种ADT MAP的实现方式,基于列表的二分查找和哈希表。在这一节中,我们将要学习二叉搜索树,这是另一种键指向值的Map集合,在这种情况下我们不用考虑元素在树中的实际位置,但要知道使用二叉树来搜索更有效率。

搜索树操作

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

Map() 创建了一个新的空Map集合。 put(key,val) 在Map中增加了一个新的键值对。如果这个键已经在这个Map中了,那么就用新的值来代替旧的值。 get(key) 提供一个键,返回Map中保存的数据,或者返回None。 del 使用del map[key]这条语句从Map中删除键值对。 len() 返回Map中保存的键值对的数目 in 如果所给的键在Map中,使用key in map这条语句返回True。

搜索树实现

一个二叉搜索树,如果具有左子树中的键值都小于父节点,而右子树中的键值都大于父节点的属性,我们将这种树称为BST搜索树。如之前所述的,当我们实现Map时,BST方法将引导我们实现这一点。图 1 展示了二叉搜索树的这一特性,显示的键没有关联任何的值。注意这种属性适用于每个父节点和子节点。所有在左子树的键值都小于根节点的键值,所有右子树的键值都大于根节点的键值。

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

现在你知道什么是二叉搜索树了,我们再来看如何构造一个二叉搜索树,我们在搜索树中按图 1 显示的节点顺序插入这些键值,图 1 搜索树存在的节点:,,,,,,。因为 是第一个被插入到树的值,它是根节点。接下来, 小于 ,因此是 的左子树。接下来, 大于 ,因此是 的右子树。我们现在填充了该树的两层,所以下一个键值,将会是 或者 的左子树或右子树。由于 大于 和 ,就变成了 的右子树。同样, 小于 和 ,因此成为了 的左子树。 也小于 ,因此必须是 的左子树。然而,它大于 ,所以是 的右子树。

为了实现二叉搜索树,我们将使用节点和引用的方法,这类似于我们实现链表和表达式树的过程。因为我们必须能够创建和使用一个空的二叉搜索树,所以我们将使用两个类来实现,第一个类我们称之为 BinarySearchTree,第二个类我们称之为TreeNode。BinarySearchTree类有一个TreeNode类的引用作为二叉搜索树的根,在大多数情况下,外部类定义的外部方法只需检查树是否为空,如果在树上有节点,要求BinarySearchTree类中含有私有方法把根定义为参数。在这种情况下,如果树是空的或者我们想删除树的根,我们就必须采用特殊操作。BinarySearchTree类的构造函数以及一些其他函数的代码如Listing 1 所示。

Listing 1

TreeNode类提供了许多辅助函数,使得BinarySearchTree类的方法更容易实现过程。如Listing 2 所示,一个树节点的结构,是由这些辅助函数实现的。正如你看到的那样,这些辅助函数可以根据自己的位置来划分一个节点作为左或右孩子和该子节点的类型。TreeNode类非常清楚地跟踪了每个父节点的属性。当我们讨论删除操作的实现时,你将明白为什么这很重要。

对于Listing 2 中的TreeNode实现,另一个有趣的地方是,我们使用Python的可选参数。可选的参数很容易让我们在几种不同的情况下创建一个树节点,有时我们想创建一个新的树节点,即使我们已经有了父节点和子节点。与现有的父节点和子节点一样,我们可以通过父节点和子节点作为参数。有时我们也会创建一个包含键值对的树,我们不会传递父节点或子节点的任何参数。在这种情况下,我们将使用可选参数的默认值。

Listing 2

现在,我们拥有了BinarySearchTree和TreeNode类,是时候写一个put方法使我们能够建立二叉搜索树。put方法是BinarySearchTree类的一个方法。这个方法将检查这棵树是否已经有根。如果没有,我们将创建一个新的树节点并把它设置为树的根。如果已经有一个根节点,我们就调用它自己,进行递归,用辅助函数_put按下列算法来搜索树:

Python实现二叉搜索树(python二叉树)

从树的根节点开始,通过搜索二叉树来比较新的键值和当前节点的键值,如果新的键值小于当前节点,则搜索左子树。如果新的关键大于当前节点,则搜索右子树。

当搜索不到左(或右)子树,我们在树中所处的位置就是设置新节点的位置。向树中添加一个节点,创建一个新的TreeNode对象并在这个点的上一个节点中插入这个对象。

Listing 3 显示了在树中插入新节点的Python代码。_put函数要按照上述的步骤编写递归算法。注意,当一个新的子树插入时,当前节点(CurrentNode)作为父节点传递给新的树。

我们执行插入的一个重要问题是重复的键值不能被正确的处理,我们的树实现了键值的复制,它将在右子树创建一个与原来节点键值相同的新节点。这样做的后果是,新的节点将不会在搜索过程中被发现。我们用一个更好的方式来处理插入重复的键值,旧的值被新键关联的值替换。我们把这个错误的修复,作为练习留给你。

Listing 3

随着put方法的实现,我们可以很容易地通过__setitem__方法重载[]作为操作符来调用put方法(参见Listing 4)。这使我们能够编写像myZipTree['Plymouth'] = 一样的python语句,这看上去就像Python的字典。

Listing 4

图 2 说明了将新节点插入到一个二叉搜索树的过程。灰色节点显示了插入过程中遍历树节点顺序。

图 2: 插入一个键值 = 的节点

一旦树被构造,接下来的任务就是为一个给定的键值实现检索。get方法比put方法更容易因为它只需递归搜索树,直到发现不匹配的叶节点或找到一个匹配的键值。当找到一个匹配的键值后,就会返回节点中的值。

Listing 5 显示了get,_get和__getitem__的代码。用_get方法搜索的代码与put方法具有相同的选择左或右子树的逻辑。请注意,_get方法返回TreeNode中get的值,_get就可以作为一个灵活有效的方式,为BinarySearchTree的其他可能需要使用TreeNode里的数据的方法提供参数。

通过实现__getitem__方法,我们可以写一个看起来就像我们访问字典一样的Python语句,而事实上我们只是操作二叉搜索树,例如Z = myziptree ['fargo']。正如你所看到的,__getitem__方法都是在调用get。

Listing 5

使用get,我们可以通过写一个BinarySearchTree的__contains__方法来实现操作,__contains__方法简单地调用了get方法,如果它有返回值就返回True,如果它是None就返回False。如Listing 6 所示。

Listing 6

回顾一下__contains__重载的操作符,这允许我们写这样的语句:

Python实现二叉堆 优先队列的二叉堆实现在前面的章节里我们学习了先进先出(FIFO)的数据结构:队列(Queue)。队列有一种变体叫做优先队列(PriorityQueue)。优先队列

Python解析树及树的遍历 解析树完成树的实现之后,现在我们来看一个例子,告诉你怎么样利用树去解决一些实际问题。在这个章节,我们来研究解析树。解析树常常用于真实

Python内建数据结构详解 一、列表(List)list是一个可以在其中存储一系列项目的数据结构。list的项目之间需用逗号分开,并用一对中括号括将所有的项目括起来,以表明这是

标签: python二叉树

本文链接地址:https://www.jiuchutong.com/biancheng/382321.html 转载请保留说明!

上一篇:Python的组合模式与责任链模式编程示例(python组合运算)

下一篇:Python实现二叉堆(python 二叉堆)

  • 未开票收入退回可以冲税吗
  • 核定征收三种方式
  • 季度费用支出怎么做
  • 工会经费网上缴费
  • 分公司可以用总公司的业绩吗
  • 隔年的发票能冲销吗
  • 固定资产未付款怎么入账
  • 金税盘服务费能抵税吗
  • 怎么开具商业承兑票据
  • 购电子承兑汇票差额计入什么科目?
  • 原材料投资入股协议约定价值公允价值
  • 暂估收入是否暂列金额
  • 手撕票验旧是什么意思
  • 公司购房、售房需要缴纳哪些税?
  • 增值税专用发票和普通发票的区别
  • 对公账户上扣缴的税怎么做分录?
  • 股东以车辆出资 涉及哪些税费
  • 定额发票上除了发票章还有其他章吗
  • 生活中都交了哪些朋友
  • linux对硬件的要求
  • 怎么给文件添加属性
  • 辞退补偿金额怎么做账
  • 个人转让股权如何缴纳个人所得税税率
  • 企业收购特殊税种有哪些
  • echarts3d地图
  • 工业企业的费用
  • php获取并显示用户的用户名
  • 什么是水利建设基金税
  • 增值税发票申报单怎么填
  • 零申报的账怎么做
  • php中的表达式简写是什么
  • php ajax 实现
  • 公司变更需要哪些资料~问华杰 财务
  • 动态设置窗体记录源属性
  • php设置title
  • 自然人税收管理系统
  • 律师费怎么要回来
  • 模型的内容
  • 企业自建房出售给员工个人后还需要缴纳土地使用税么
  • 结转生产成品
  • 红字信息表必须要原件吗
  • 微信平台的收入从哪里来
  • 月初红字冲销暂估入账
  • spring security例子
  • 待处理财产损益借方增加还是减少
  • 专利权的入账价值包括资本化支出吗
  • 对公账户是怎样的
  • 纳税对象的类型不包括
  • 长期股权投资转让收益需要交增值税吗
  • 银行汇票转入银行分录
  • 跨年工程施工如何计算成本
  • 公司员工出差住酒店费用明细有问题怎么办
  • 成本费用占营业收入比重
  • 没有到位的注资公司
  • 主营业务收入和营业外收入的区别
  • 主营业务收入分为
  • 公司坏账率一般多少
  • sql获取某个字符的位置
  • mysql里面的数据类型
  • vmware虚拟机怎么克隆
  • ubuntu怎么录音
  • xp系统升级成win7还会卡吗
  • 个人pc用户免费下载软件
  • 服务器不支持是什么意思
  • 引发脚本异常
  • js中的函数
  • javascript HTML5 Canvas实现圆盘抽奖功能
  • rhel7.6安装
  • cygwin下载教程
  • node.js [superAgent] 请求使用示例
  • 编写一个bash脚本程序,用for循环实现
  • js判断字符串字符出现的次数
  • Errors running builder 'Android Resource Manager' on Project java.lang.NullPointerException
  • shell脚本技巧
  • jq写css样式
  • javascript sort方法排序
  • 电脑兼容ie
  • Windows下Eclipse+PyDev配置Python+PyQt4开发环境
  • 税控盘状态
  • 同比减少怎么计算出来
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设