problem-solving-with-algorithms-and-data-structure-using-python 中文版 6 树和树的算法
树的属性:
分析树可以用于表示诸如句子或数学表达式的真实世界构造。
前序、中序、后序遍历
前序遍历中,我们首先访问根节点,然后递归地做左侧子树的前序遍历,随后是右侧子树的递归前序。
中序遍历中,递归地对左子树进行一次遍历,访问根节点,最后递归遍历右子树。
后序遍历中,递归地对左子树和右子树进行后序遍历,然后访问根节点。
队列的一个重要变种称为优先级队列。优先级队列的作用就像一个队列,可以通过前面删除一个项目来出队。然而,在优先级队列中,队列中的项的逻辑顺序由他们的优先级确定,最高优先级的项在队列的前面,最低优先级的项在后面。因此,当你将项排入优先级队列时,新项可能一直移动到前面。
实现优先级队列的经典方法是使用称为二叉堆的数据结构。二叉堆允许将我们在O(logn)中排队和取出队列。
二叉堆有两个常见的变体,最小堆(最小的键总在最前面)和最大堆(最大的键总在最前面)。
二叉堆的基本操作如下:
平衡二叉树在根的左和右子树中具有大致相同数量的节点
完整二叉树是一个树,其中每个层都有其所有的节点,除了树的最底层,从左到右填充
下图是一个完整二叉树
完整二叉树的另一个有趣的属性是,我们可以使用单个列表来表示它。我们不需要节点和引用,甚至列表的列表。因为树是完整的,父节点的左子节点(在位置p处)是在列表中位置2p中找到的节点。类似的,父节点的右子节点在列表中的2p+1。
用堆中存储项的方法依赖于维护堆的排序属性。堆得排序属性如下:在堆中,对于具有父p的每个节点x,p中的键小于或等于x中的键,上图也具有堆顺序属性
二叉搜索树依赖于在左子树中找到的键小于父节点的属性,并且在右子树中找到的键大于父代。这个属性为bst属性。
平衡二叉搜索树
节点的平衡因子:左子树的高度和右子树的高度之差