Python数据结构与算法笔记(4)

problem-solving-with-algorithms-and-data-structure-using-python 中文版 6 树和树的算法

树的属性:

  • 分层
  • 一个节点的子节点独立于另一个节点的子节点
  • 每个叶节点是唯一的

分析树可以用于表示诸如句子或数学表达式的真实世界构造。

前序、中序、后序遍历

前序遍历中,我们首先访问根节点,然后递归地做左侧子树的前序遍历,随后是右侧子树的递归前序。

中序遍历中,递归地对左子树进行一次遍历,访问根节点,最后递归遍历右子树。

后序遍历中,递归地对左子树和右子树进行后序遍历,然后访问根节点。

队列的一个重要变种称为优先级队列。优先级队列的作用就像一个队列,可以通过前面删除一个项目来出队。然而,在优先级队列中,队列中的项的逻辑顺序由他们的优先级确定,最高优先级的项在队列的前面,最低优先级的项在后面。因此,当你将项排入优先级队列时,新项可能一直移动到前面。

实现优先级队列的经典方法是使用称为二叉堆的数据结构。二叉堆允许将我们在O(logn)中排队和取出队列。

二叉堆有两个常见的变体,最小堆(最小的键总在最前面)和最大堆(最大的键总在最前面)。

二叉堆的基本操作如下:

  • BinaryHeap()创建一个新的空的二叉堆
  • insert(k)向堆添加一个新项
  • findMin()返回具有最小键值的项,并将项留在堆中
  • delMin()返回具有最小键值得项,从堆中删除该项
  • 如果堆是空的,isEmpty()返回true,否则返回false
  • size()返回堆中的项数
  • buildHeap(list)从键列表中构建一个新的堆

平衡二叉树在根的左和右子树中具有大致相同数量的节点

完整二叉树是一个树,其中每个层都有其所有的节点,除了树的最底层,从左到右填充

下图是一个完整二叉树

完整二叉树的另一个有趣的属性是,我们可以使用单个列表来表示它。我们不需要节点和引用,甚至列表的列表。因为树是完整的,父节点的左子节点(在位置p处)是在列表中位置2p中找到的节点。类似的,父节点的右子节点在列表中的2p+1。

用堆中存储项的方法依赖于维护堆的排序属性。堆得排序属性如下:在堆中,对于具有父p的每个节点x,p中的键小于或等于x中的键,上图也具有堆顺序属性

二叉搜索树依赖于在左子树中找到的键小于父节点的属性,并且在右子树中找到的键大于父代。这个属性为bst属性。

平衡二叉搜索树

节点的平衡因子:左子树的高度和右子树的高度之差

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习与自然语言处理

二叉树的遍历:先序中序后序遍历的递归与非递归实现及层序遍历

  对于一种数据结构而言,遍历是常见操作。二叉树是一种基本的数据结构,是一种每个节点的儿子数目都不多于2的树。二叉树的节点声明如下: 1 typedef str...

34660
来自专栏决胜机器学习

PHP数据结构(十三) ——动态查找表(二叉排序树)

PHP数据结构(十三) ——动态查找表(二叉排序树) (原创内容,转载请注明来源,谢谢) 一、概念 1、动态查找表特点 当对动态查找表进行查...

542100
来自专栏算法与数据结构

PTA 循环单链表区间删除 (15 分)

本题要求实现带头结点的循环单链表的创建和单链表的区间删除。L是一个带头结点的循环单链表,函数ListCreate_CL用于创建一个循环单链表,函数ListDel...

27080
来自专栏编程理解

数据结构(二):二叉搜索树(Binary Search Tree)

二分法的查找过程是,在一个有序的序列中,每次都会选择有效范围中间位置的元素作判断,即每次判断后,都可以排除近一半的元素,直到查找到目标元素或返回不存在,所以

33710
来自专栏数据结构与算法

洛谷P2827 蚯蚓(单调队列)

有$m$个时间,每个时间点找出长度最大的蚯蚓,把它切成两段,分别为$a[i] * p$和$a[i] - a[i] * p$,除这两段外其他的长度都加一个定值$q...

7420
来自专栏ACM算法日常

算法合集 | 神奇的笛卡尔树 - HDU 1506

笛卡尔树是一个很有意思的树形结构,因为它同时满足两个性质,从key(key就是索引位置,如下图中9的key为1,3的key为2......)来看...

40820
来自专栏老付的网络博客

Java中的容器

在Java中有常用的三种类型的容器,分别是List 、Map、Set,基于这个三个基本的类型,派生出很多其它的类型,具体关系如下:

32720
来自专栏技术专栏

无向图最短路径问题

题目:无向图G有N个结点(1<N<=1000)及一些边,每一条边上带有正的权重值。 找到结点1到结点N的最短路径,或者输出不存在这样的路径。

54320
来自专栏Android知识点总结

Java总结之容器家族--Collection

Set的操作比较少,基本上也就是Collection传下来的方法 Set一般基于Map来实现:HashSet、LinkedHashSet、TreeSet的特性...

16920
来自专栏算法channel

图解用栈数据结构对树的遍历

本公众号主要推送关于如何构思算法使之应用到我们的工作中。计算机常用算法思想大致来说有,分而治之,动态规划,贪心算法,搜索算法,回溯 ,训练这些思维的一个很好的平...

378110

扫码关注云+社区

领取腾讯云代金券