天道酬勤,学无止境

决定关闭这棵树的算法?(Algorithm to decide cut-off for collapsing this tree?)

问题

我有一个 Newick 树,它是通过比较 4-9 bp 长 DNA 序列的假定 DNA 调控基序的位置权重矩阵(PWM 或 PSSM)的相似性(欧几里德距离)构建的。

树的交互式版本在 iTol 上(这里),您可以自由地玩 - 只需在设置参数后按“更新树”:

在此处输入图片说明

我的具体目标:如果它们与最近的父进化枝的平均距离 < X(ETE2 Python 包),则将这些图案(尖端/终端节点/叶子)折叠在一起。 这在生物学上很有趣,因为一些基因调控 DNA 基序可能彼此同源(旁系同源物或直向同源物)。 这种折叠可以通过上面链接的 iTol GUI 完成,例如,如果您选择 X = 0.001,那么一些图案会折叠成三角形(图案系列)。

我的问题:有人可以提出一种算法来输出或帮助可视化哪个 X 值适合于“最大化折叠图案的生物学或统计相关性”? 理想情况下,当针对 X 绘制时,树的某些属性会出现一些明显的阶跃变化,这向算法建议一个合理的 X。是否有任何已知的算法/脚本/包? 也许代码会根据 X 的值绘制一些统计数据? 我试过绘制 X 与平均簇大小(matplotlib),但我没有看到明显的“步长增加”来告诉我要使用哪个 X 值:

在此处输入图片说明

我的代码和数据:我的 Python 脚本的链接是 [here][8],我对它进行了大量评论,它将为您生成树数据和上面的图(使用参数 d_from、d_to 和 d_step 来探索距离切割-关闭,X)。 如果您有 easy-install 和 Python,您将需要通过简单地执行这两个 bash 命令来安装 ete2:

apt-get install python-setuptools python-numpy python-qt4 python-scipy python-mysqldb python-lxml

easy_install -U ete2
回答1

您可以尝试使用类似于@Jeff 提到的树协调的东西。 但是标准的树协调实际上会失败。

和解首先包括在整个目标树中添加代表进化特征“损失”的分支。 然后指出发生进化特征“重复”的节点。 损失和重复的加权总和提供了优化的成本函数。

但是在您的情况下,您要解决的问题是“将这棵超级树分解为大小合适的直系子树”。 这意味着您并不真的想像复制一样造成损失。 您想要一种对树进行评分的方法,以便它显示有多少直系同源子树合并到您的超级树中。 因此,您可以尝试这种评分方法:

  1. 取一棵超级树,计算重复物种的数量,S1。
  2. 折叠作为旁系同源物的所有末端叶子并计算重复物种的新数量 S2。
  3. S1 和 S2 之间的差异揭示了您在超级树中大约有多少子树。
  4. 要纠正由各种大小的超级树引起的任何偏差,请除以超级树 N 中表示的独特物种的数量。

如果我们将此分数称为“子树因子”,则它等于:

S1 - S2 / N

推论:

  • 如果 S1 - S2 = S1 那么这意味着你的超级树中大约有一个真正的子树,所有多个物种的出现都只是由于最近的旁系同源。

  • 如果 S1 - S2 = 0 那么这意味着你的超级树里面有大约 S1 个真正的子树。

回答2

我想我需要了解更多才能给出具体建议。 但也许这会有所帮助。 我假设每个终端节点都是一个序列,每个内部节点都是一个 PSSM。

X 的计算是特定于应用程序的。 例如,如果您想折叠超平行同源物,您得到的 X 与您想折叠所有同系物时得到的 X 不同。

由于通过复制和物种形成不断创造基因,因此没有单一的 X 值可以通过进化关系区分序列。 因此,我不希望您仅通过查看聚类统计数据就可以找到令人满意的代理来确定序列之间的进化关系。

更严格的方法是根据每个调控基序的基因构建基因树,并将其与物种树相协调。 那里有软件和额外的启发式方法来识别直向同源物/内向同源物。

如果你这样做,你的树的内部节点将用推断的进化事件(例如,复制、物种形成)装饰。 然后你可以为你不关心的进化枝走上树折叠节点。

受限制的 HTML

  • 允许的HTML标签:<a href hreflang> <em> <strong> <cite> <blockquote cite> <code> <ul type> <ol start type> <li> <dl> <dt> <dd> <h2 id> <h3 id> <h4 id> <h5 id> <h6 id>
  • 自动断行和分段。
  • 网页和电子邮件地址自动转换为链接。

相关推荐
  • Algorithm to decide cut-off for collapsing this tree?
    I have a Newick tree that is built by comparing similarity (euclidean distance) of Position Weight Matrices (PWMs or PSSMs) of putative DNA regulatory motifs that are 4-9 bp long DNA sequences. An interactive version of the tree is up on iTol (here), which you can freely play with - just press "update tree" after setting your parameters: My specific goal: to collapse the motifs (tips/terminal nodes/leaves) together if their average distances to the nearest parent clade is < X (ETE2 Python package). This is biologically interesting since some of the gene regulatory DNA motifs may be homologous
  • storm入门教程 第四章 消息的可靠处理
    4.1 简介storm可以确保spout发送出来的每个消息都会被完整的处理。本章将会描述storm体系是如何达到这个目标的,并将会详述开发者应该如何使用storm的这些机制来实现数据的可靠处理。4.2 理解消息被完整处理一个消息(tuple)从spout发送出来,可能会导致成百上千的消息基于此消息被创建。我们来思考一下流式的“单词统计”的例子:storm任务从数据源(Kestrel queue)每次读取一个完整的英文句子;将这个句子分解为独立的单词,最后,实时的输出每个单词以及它出现过的次数。本例中,每个从spout发送出来的消息(每个英文句子)都会触发很多的消息被创建,那些从句子中分隔出来的单词就是被创建出来的新消息。这些消息构成一个树状结构,我们称之为“tuple tree”,看起来如图1所示:图1 示例tuple tree在什么条件下,Storm才会认为一个从spout发送出来的消息被完整处理呢?答案就是下面的条件同时被满足:tuple tree不再生长树中的任何消息被标识为“已处理”如果在指定的时间内,一个消息衍生出来的tuple tree未被完全处理成功,则认为此消息未被完整处理。这个超时值可以通过任务级参数Config.TOPOLOGY_MESSAGE_TIMEOUT_SECS 进行配置,默认超时值为30秒。4.3 消息的生命周期如果消息被完整处理或者未被完整处理
  • 算法:从未知数组中查找第二个最小元素的索引(Algorithm: Find index of 2nd smallest element from an unknown array)
    问题 一段时间以来,我一直在思考我的作业问题。 我欢迎(并且更喜欢)关于如何解决此问题的任何建议或方法。 基本上,我有一个大小为N的数组A。我们不知道元素,但是我们知道它们是不同的。 我唯一拥有的是一个人将以N取两个索引(i,j)。然后这个人会告诉我A [j]是<还是> A [i]。 我想通过向此人提出<= n + log n个问题来找到用于查找第二个最小元素的索引的算法。 回答1 这个答案描述了如何找到第二大元素。 查找第二个最小值可以类似地完成。 为了简单起见,我们还假定所有数字都是不同的。 为了找到最大的元素,让我们构建一棵“冠军”树:将元素配对,确定哪个更大(那个是“赢家”),然后将胜利者配对,决定哪个更大,依此类推,直到找到“冠军”,这才是最大的要素。 这需要n步。 现在,第二大要素必须与冠军进行比较。 (因为只有冠军才能击败它)。 已将log n个元素与冠军进行了比较,因此从中选择最大的元素; 这需要log n个步骤。 作为示例,让我们看一下这对于数字元组[6,4,3,5,2,1]的工作方式。 在第一轮中,对为(6,4),(3,5),(2,1)。 赢家是每对中更大的元素,即6,5,2。 在第二轮中,对为(6,5),2。(2在这里没有对,因此它将被自动提升为下一轮)。 第二轮的获胜者是6和2,在第三轮中,唯一的一对是(6,2),6是获胜者。 现在,通过配对元素并选择获胜者
  • 数据结构之并查集
    什么是并查集 并查集(Union Find),从字面意思不太好理解这东西是个啥,但从名字大概可以得知与查询和集合有关,而实际也确实如此。并查集实际上是一种很不一样的树形结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。 之所以说并查集是一种“不一样”的树形结构,是因为一般的树形结构都是父节点指向子节点的,而并查集则是反过来,子节点指向父节点,并且这棵树会是一棵多叉树。 并查集可以高效的用来解决连接问题(Connectivity Problem),我们来看下面这样的一张图: 可以看到,该图中有很多的点,有些点之间有连接,而有些点之间则没有连接。那么此时就有一个问题是:这图中任意的两个点是否可能通过一条路径连接起来。对于这个问题,我们使用并查集就可以高效的求解,因为并查集可以非常快地判断网络中节点间的连接状态。这里的网络指的是广义的网络,例如用户之间形成的社交网络,有时候也叫做图。 并查集对于一组数据来说,主要支持两种操作: 合并:union(p, q),把两个不相交的集合合并为一个集合。 查询:isConnected(p, q),查询两个元素是否在同一个集合中,也就是是否可以连接的。 根据这两个操作,我们就可以定义出并查集的接口了,这是因为并查集可以有多种实现方式,这里定义接口来做统一抽象: package tree.unionfind; /** *
  • 前端进阶必备的树与二叉树知识
    1. 有一颗树的括号表示为A(B, C(E, F(G)), D),回答下面的问题: 指出树的根结点?指出棵树的所有叶子结点?结点C的度是多少?这棵树的度为多少?这棵树的高度是多少?结点C的孩子结点是哪?结点C的双亲结点是谁? 答案: 这棵树的根结点为A 这棵树的叶子结点为B丶E丶G丶D // 叶子结点:一棵树当中没有子结点(即度为0)的结点称为叶子结点,简称“叶子”。叶子是指出度为0的结点,又称为终端结点。 结点C的度为2 // 结点度:结点拥有子结点的数量 这棵树的度是3 // 二叉树的度:是指树中各结点度的最大值 这棵树的高度为4 // 深度是从根节点到它的叶节点,高度是从叶节点数到它的根节点 节点C的孩子结点是E丶F 结点C的双亲结点是A 2. 若一棵度为4的树中度为2丶3丶4的结点个数分别为3丶2丶2,则该树的叶子结点的个数是多少? 答案: 在树中,结点有几个分叉,度就是几。 树中结点数 = 总分叉树 + 1。(这里的分叉树就是所有结点的度之和) 那么设叶子数为X,则此树的总分叉树为 2 * 3 + 3 * 2 + 4 * 2 = 20;树中结点数 = 总分叉树 + 1 = 20 + 1 = 21; 3 + 2 + 2 + X = 21,解得X = 14,即该树的叶子结点的个数为14。 3. 为了实现以下各种功能,其中X结点表示该结点的位置,给出树的最适合的存储结构:
  • 阿里深度树匹配召回体系演进
    导读:目前不管是广告还是推荐业务,最底层的技术都是检索,由于候选集合非常大,可能从千万甚至亿级别取出数十个用户感兴趣的商品。在算力和时间复杂度的约束下,往往采用分阶段漏斗的算法体系。具体来说就是分成召回 ( match ) 以及排序 ( rank )。本文主要介绍阿里在match阶段的最新实践——深度树匹配,分成几个部分:检索召回技术现状深度树匹配(TDM)技术演进TDM业务应用实践总结与展望01检索召回技术现状1. 互联网业务中检索召回技术的发展对于match这一部分来说,我们的核心问题是要从一个大规模的候选集合里面高效检索出topK。单点计算消耗和所需计算次数决定了系统性能边界。我们需要在实际设计系统的时候考虑两个平衡,首先是我们的对于每个item使用模型打分,有单点计算消耗的约束,从广告库里面解锁商品,有计算次数上限,我们需要保证在现有的系统性能边界下,无论是单点的计算消耗以及所需的计算次数,他们的乘积不能超过这个性能边界。2. 两段式Match的经典实现在我们系统里面最早期的是一个经典的两段式match,例如基于商品的协同过滤,就是说对我们对于每一条用户的请求我们去找到用户历史的item,然后再通过这些item查询离线计算好的I2I相似关系表找到我们需要召回的item,并且最终做合并取topK。这个方法它的优势在于模型非常简单,而且实现成本非常低
  • day3 机器学习 sklearn学习 集成算法-随机森林
    # todo: 集成算法模块 集成学习 ensemble # 决策树非常容易 过拟合:在训练集上表现优秀,却在测试集上表现糟糕,一般用剪枝 # 目前最受欢迎的集成算法GBDT # todo:三类集成算法: # ·装袋法(Bagging):构建多个相互独立的评估器,然后对其预测进行平均或多数表决原则来决定集成评估器的结果。装袋法的代表模型就是随机森林 # ·提升法(Boosting) :基评估器是相关的,是按顺序一一构建的。其核心思想是结合弱评估器的力量一次次对难以评估的样本进行预测,从而构成一个强评估器。提升法的代表模型有Adaboost和梯度提升树 # ·stacking # todo: # 类 类的功能 # ensemble.AdaBoostClassifier AdaBoost分类 # ensemble.AdaBoostRegressor Adaboost回归 # ensemble.BaggingClassifier 装袋分类器 # ensemble.BaggingRegressor 装袋回归器 # ensemble.ExtraTreesClassifier Extra-trees分类(超树,极端随机树) # ensemble.ExtraTreesRegressor Extra-trees回归 # ensemble.GradientBoostingClassifier
  • 《算法笔记》学习日记——9.3 树的遍历&9.4 二叉查找树(BST)
    目录 9.3 树的遍历问题 A: 树查找问题 B: 树的高度小结 9.4 二叉查找树(BST)问题 A: 二叉排序树问题 B: 二叉搜索树小结 9.3 树的遍历 Codeup Contest ID:100000612 问题 A: 树查找 题目描述 有一棵树,输出某一深度的所有节点,有则输出这些节点,无则输出EMPTY。该树是完全二叉树。 输入 输入有多组数据。 每组输入一个n(1<=n<=1000),然后将树中的这n个节点依次输入,再输入一个d代表深度。 输出 输出该树中第d层得所有节点,节点间用空格隔开,最后一个节点后没有空格。 样例输入 5 1 2 3 4 5 7 7 1 2 3 4 5 6 7 2 0 样例输出 EMPTY 2 3 思路 这题刚一拿到我还想着用vector容器来存当前结点的孩子结点,然后一遍BFS得到所有结点的层次,再根据层次输出所有结点。 但是懒癌让我发现这一题其实根本用不着用数组存(但是又得接受输入的那n个数,所以设个vector吧,节省点内存空间,输入完清了就好了),之所以这么说是因为题目说了这是一棵完全二叉树,也就是说只有最后一层的结点是满的或者半满的,其他层的结点都是满的,所以很容易就能通过数学公式算出来。 稍加列举就不难发现,深度为d(也就是第d层)的那一层第一个结点的编号是2d-1,d的下一层(也就是d+1层)的第一个结点编号是2d,因此
  • 快速掌握数据结构
    1 线性表 2 栈与队列 3 串 串的定义: 限制元素为字符的线性表 串的匹配算法: 简单模式匹配算法KMP算法(线性算法)O(m+n)KMP算法的改进 4 数组、矩阵和广义表 5 树与二叉树 概念:树的度、节点的度、高度 树的度:树中各节点度的最大值 节点的度:节点拥有的子树个数或分支的个数 高度:树中节点的最大层次 二叉树的先序、中序、后序和层次遍历 先序遍历过程(递归)(也可使用栈): 如果二叉树为空树,则什么都不做;否则 访问根节点先序遍历左子树先序遍历右子树 中序、后序遍历类似,只是访问根节点操作分别位于中间、后面。 层序遍历过程: 建立一个循环队列,将二叉树头节点入队列,然后出队列,访问该节点,如果它有左子树,则将左子树的根节点入列,如果有右子树,则右子树根节点入列,然后出列,对出队节点访问,如此,直到队列为空。 应用: 后序:求表达式的值 中序:求二叉树的深度 哈弗曼树和哈弗曼编码 平衡二叉树 6 图 图的遍历操作 DFS(递归、栈) 类似于二叉树的先序遍历。基本思想:首先访问出发点v,并将其标注为已访问过;然后选取与v邻接的未被访问的任意一个顶点w,并访问,再选取与w邻接的未被访问的任意一个顶点,重复。当一个顶点的所有邻接顶点都被访问过时,依次退回最近被访问过的顶点。直到图中所有节点都被访问为止。 BFS(队列) 类似与二叉树的层次遍历。 最小生成树 普利姆算法:
  • Union-Find算法
    Union-Find算法 声明算法简介问题基本思路平衡优化路径压缩完成代码结束 声明 本文章的内容来源于《abuladong的算法小抄》,为了加强自己的记忆,写本文章梳理学习内容。 算法简介 本算法为通常说的并查集算法,主要解决图论中“动态连通性”问题。数据结构(清华版)课本上有一节专门讲了这个算法。 问题 一个图(无向图)有5个节点(1~5),他们不是相互连通的,那么我们认为连通分量为5个。 在此我们可以实现Union-Find算法的API: class UnionFind{ public: // 将p节点和q节点连通 void union(int p, int q); //判断p节点和q节点是否连通 bool connect(int p, int q); //返回图中有多少个连通分量 int count(); } 这里得连通是建立在无向图之上的。 如果现在调用union(1,2),那么节点0和节点1被连通,连通分量就变成4个。 再调用union(2,3),那么这时1,2,3节点都被连通,再调用connected(1,3)也会返回true,连通分量变成8个。 由此可见,本算法的关键在于union和connected函数的效率。 基本思路 模型:使用森林来表示图的动态连通性 数据结构:数组实现这棵树 表示连通性:设定数的每个节点用一个指针指向其父节点,如果是根节点
  • 字典树 —— 字符串分析算法
    这里我们继续来编程训练,在《前端进阶》这个系列里面我们已经讲过一些字符串的算法了。然后这篇文章我们就来一起学习,剩下的几个字符串中比较细节的算法。 字符串分析算法 在开始之前我们先来看看字符串算法的一个整体目录。这里我们从简单到难的算法来排列,大概就分成这样一个顺序: 字典树 大量高重复字符串的储存与分析(完全匹配)比如说我们要处理 1 亿个字符串,这里面有多少出现频率前 50 的这样的字符串,1 亿这个量我们还是可以用字典树去处理的再比如说大家做搜索关键词,或者相同的字符串搜索类型的情况,很多时候我们就会需要用到类似字典树这样的一个结构 KMP 在长字符串里找模式(部分匹配)它跟字典树最大的区别就是字典树是检查两个字符串是否完全匹配,而 KMP 是两个字符串中,一个字符串是两一个字符串的一部分,但是这个就会出现一个更为复杂的问题。如果我们有一个长度为 m 的字符串和一个长度为 n 的字符串,然后让他们两个互相匹配,这个时候我们有两种匹配方法第一种就是暴力破解法,它可能是m 乘以 n 的时间复杂度,显然这个算法的性能在大量的搜索字符的时候是不行的所以后面几位计算机专家研究出了 KMP 算法,而 KMP 就是三个人的名字的首字母,K 是高德纳,一个著名的写计算机程序设计的老爷子。加上另外两个计算机专家共同发明了 KMP 算法。这个算法就是在一个长字符串里面匹配一个短字符串
  • MOOC数据结构与算法Python版-第十周测验
    1 单选(2分) 如下哪个树正确地显示了按顺序插入键值5,30,2,40,25,4后的二叉搜索树? D A.其它选项都不对 B. C. D. 2 单选(2分) 对以下这棵树: 操作,欲把根节点11删除,remove方法做完后新的根节点是(),其右子树的高度是()。A A. 12,2 B. 15,1 C. 15,2 D. 12,1 3 单选(2分) 下图有两棵树,其中a()平衡二叉树,b()平衡二叉树。D A. 不是,不是 B. 是,是 C. 是,不是 D. 不是,是 4 单选(2分) 对下面这棵树查找元素77,在查找失败前需要进行几次比对?D A.4 B.1 C.2 D.3 5 单选(2分) 高度为4的平衡二叉树最少有()个节点。D A.9 B.7 C.15 D.12 6 单选(2分) 考虑规模为n的二叉搜索树中,put, get, del, in 四个方法的时间复杂度数量级。四个方法中,有()个方法在最差情况下,具有O(n)的时间复杂度 C A.3 B.1 C.4 D.2 7 多选(3分) 将键值1,2,3,4,5,6,7的七个元素以某种顺序插入某二叉搜索树后,发现这个树的根是2。问这个树的高度可能为多少?ACD A.5 B.2 C.4 D.3 8 多选(3分) 这是一棵右重树,圈内写出其点的名称和其平衡因子: 将它进行旋转以后得到的树叫做T,选出正确的选项。AB A.T的根是D
  • 机器学习 GBDT+xgboost 决策树提升
    目录xgboost训练xgboostxgboost模型目标函数正则化项处理理论终章最终章-拨开云雾见月明多说一嘴GB思想(Gradient Boosting)DT树(Desicion Tree)横空出世的前向分步算法GB再解释GBDTCART(Classify and Regression Tree)GBDT(Gradient Boosting Desicion Tree)大BOSS——xgboostxgboostxgboost是一个监督模型,它对应的模型就是一堆CART树,即由CART树组成的随机森林。预测的最终结果是由随机森林中的所有CART树的预测分数相加。总而言之xgboost的想要解决的问题是通过前t-1棵的预测值加和我们是否能算出第t棵树的最优预测值?CART(Classify and Regression Tree)此处不多赘述,决策树一章会有较多描述。简而言之,CART就是既可以做分类又可以做回归的树。无论是做分类还是做回归他的叶节点(预测结果)都会有一个权重值(分数),而不是一个确定的类别。不清楚CART树不影响你理解xgboost。GBDT(Gradient Boosting Desicion Tree)GB思想(Gradient Boosting)GB通过迭代多棵树共同决策,并且每一棵树学的是之前所有树的预测值的总和与真实值之间的残差,残差值=真实值
  • 为什么斐波那契堆称为斐波那契堆?(Why is a Fibonacci heap called a Fibonacci heap?)
    问题 斐波那契堆数据结构的名称中有“斐波那契”一词,但数据结构中似乎没有使用斐波那契数字。 根据维基百科文章: 斐波那契堆的名称来自运行时间分析中使用的斐波那契数。 这些斐波那契数是如何在斐波那契堆中出现的? 回答1 斐波那契堆由一组遵守特定结构约束的不同“顺序”的较小堆序树的集合组成。 斐波那契数列的出现是因为这些树的构造方式使得 n 阶树中至少有 F n+2 个节点,其中 F n+2是 (n + 2)nd 斐波那契数。 要了解为什么这个结果是正确的,让我们先看看斐波那契堆中的树是如何构造的。 最初,每当将节点放入斐波那契堆时,它都会放入仅包含该节点的 0 阶树中。 每当从 Fibonacci 堆中移除一个值时,Fibonacci 堆中的一些树就会合并在一起,这样树的数量就不会变得太大。 将树组合在一起时,斐波那契堆仅将相同顺序的树组合在一起。 要将两棵 n 阶树组合成一棵 n + 1 阶树,斐波那契堆取两棵树中根值大于另一棵树的那棵,然后使该树成为另一棵树的子树。 这一事实的一个结果是n 阶树总是恰好有 n 个孩子。 斐波那契堆的主要吸引力在于它有效地支持减少键(在摊销 O(1) 中)。 为了支持这一点,斐波那契堆实现了如下的减少键:为了减少存储在某个节点中的值的键,该节点从其父树中被切割并被视为自己的独立树。 发生这种情况时,其旧父节点的顺序减一。 例如,如果一棵 4
  • 一棵树的高度的定义是什么?(What is the definition for the height of a tree?)
    问题 我似乎找不到确切的答案,我正在尝试在堆上做一些基本的证明,但是这让我有点不满意: 空树有效吗? 如果是这样,它的高度是多少? 我认为这将是0。 单节点的树的高度是多少? 我认为这将是1,但是我已经看到了在其中为0的定义(如果是这种情况,那么我不知道如何解释一棵空树)。 回答1 我认为您应该在NIST网站上查看“算法和数据结构字典” 。 高度的定义表示单个节点的高度为0。 有效树的定义确实包含一个空结构。 该站点未提及此类树的高度,但根据高度的定义,该值也应为0。 回答2 树的高度是从树的根到其最远节点(即,距离根最远的叶节点)的路径长度。 仅具有根节点的树的高度为0,而具有零节点的树的高度将为空。 一棵空树的高度为-1。 请检查一下。 我希望这有帮助。 回答3 我已经看到它以两种方式使用(将单个节点计为0或1),但是大多数来源都会将仅根树定义为高度为0的树,并且不会认为0节点树有效。 回答4 如果您的树是递归定义的数据结构,它可能为空,也可能是带有左右子树的节点(例如,搜索树或堆),那么自然定义是将0分配给空树,并将1 +最高子树到非空树的高度。 如果您的树是图,则自然定义是从根到叶的最长路径,因此仅根树的深度为0。在这种情况下,您通常甚至不考虑空树。 回答5 一棵树的高度是其两个子节点中到终端节点的最长路径的长度。 维基百科说一棵空树的高度是-1。 我不同意。
  • 树的深度和高度之间有什么区别?(What is the difference between tree depth and height?)
    问题 这是算法理论中的一个简单问题。 它们之间的区别在于,在一种情况下,您要计算根节点和具体节点之间的最短路径上的节点数,而在其他边缘上则要数。 哪一个 回答1 我了解到深度和高度是节点的属性: 节点的深度是从节点到树的根节点的边数。 根节点的深度为0。 节点的高度是从节点到叶子的最长路径上的边数。 叶节点的高度为0。 一棵树的属性: 一棵树的高度将是其根节点的高度, 或等效地,其最深节点的深度。 树的直径(或宽度)是任意两个叶节点之间的最长路径上的节点的数目。 下面的树的直径为6个节点。 回答2 一棵树的高度和深度相等... 但是节点的高度和深度不相等,因为... 高度是通过从给定节点遍历到最深的叶子来计算的。 深度是从根到给定节点的遍历计算的..... 回答3 根据Cormen等。 算法简介(附录B.5.3)中,树T中节点X的深度定义为从T的根节点到X的简单路径的长度(边数)。节点Y的高度为从Y到叶子的最长向下简单路径上的边数。 一棵树的高度定义为其根节点的高度。 注意,简单路径是没有重复顶点的路径。 一棵树的高度等于树的最大深度。 节点的深度和节点的高度不一定相等。 参见第三版Cormen等的图B.6。 这些概念的说明。 有时我会遇到一些问题,要求人们计算节点(顶点)而不是边缘,因此请澄清一下,如果您不确定在考试或工作面试中应该计算节点或边缘。 回答4 我知道这很奇怪
  • 面试题10---二叉树的镜像和对称二叉树详解
    1.题目 请完成一个函数,输入一棵二叉树,该函数输出它的镜像。二叉树结点的定义如下。 struct BinaryTreeNode { int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight;; }; 2.就题论题 树的镜像对很多人来说是一个新的概念,我们未必能够一下子想出求树的镜像的方法。为了能够形成直观的印象,我们可以自己画一棵二叉树,然后根据照镜子的经验画出它的镜像。如图一所示中右边的二叉树就是左边的树的镜像。 仔细分析这两棵树的特点,看看能不能总结出求镜像的步骤。这两棵树的根结点相同,但它们的左、右两个子结点交换了位置。因此,我们不妨先在树中交换根结点的两个子结点,就得到图二中的第二棵树。 交换根结点的两个子结点之后,我们注意到值为10、6的结点的子结点仍然保持不变,因此我们还需要交换这两个结点的左、右子结点。交换之后的结果分别是图二中的第三棵树和第四棵树。做完这两次交换之后,我们已经遍历完所有的非叶结点。此时变换之后的树刚好就是原始树的镜像。 总结上面的过程,我们得出求一棵树的镜像的过程:先前序遍历这棵树的每个结点,如果遍历到的结点有子结点,就交换它的两个子节点。当交换完所有非叶子结点的左、右子结点之后,就得到了树的镜像。 想清楚了这种思路,我们就可以动手写代码了。参考代码如下: void
  • 【算法】【回溯】回溯算法解题套路框架【转载】
    原文链接:https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/hui-su-suan-fa-xiang-jie-xiu-ding-ban 读完本文,你不仅学会了算法套路,还可以顺便去 LeetCode 上拿下如下题目: 46.全排列 51.N皇后 前言 这篇文章是很久之前的一篇《回溯算法详解》的进阶版,之前那篇不够清楚,就不必看了,看这篇就行。把框架给你讲清楚,你会发现回溯算法问题都是一个套路。 废话不多说,直接上回溯算法框架。解决一个回溯问题,实际上就是一个决策树的遍历过程。你只需要思考 3 个问题: 1、路径:也就是已经做出的选择。 2、选择列表:也就是你当前可以做的选择。 3、结束条件:也就是到达决策树底层,无法再做选择的条件。 如果你不理解这三个词语的解释,没关系,我们后面会用「全排列」和「N 皇后问题」这两个经典的回溯算法问题来帮你理解这些词语是什么意思,现在你先留着印象。 代码方面,回溯算法的框架: result = [] def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择 其核心就是 for 循环里面的递归,在递归调用之前「做选择」
  • 数据结构与算法(二叉树)
    首语 上一篇:数据结构与算法(树) 二叉树的建立 代码实现 /** * 通过前序遍历的数据序列反向生成二叉树 * A * B C * D E # F * # # # # # # * <p> * ABD##E##C#F## */ public void createBinaryTreePre(ArrayList<String> data){ createBinaryTree(data.size(),data); } public TreeNode createBinaryTree(int size, ArrayList<String> data) { if (data.size() == 0) { return null; } String d = data.get(0); TreeNode node; int index = size - data.size(); if (d.equals("#")) { node = null; data.remove(0); return node; } node = new TreeNode(index, d); if (index == 0) { //创建根节点 root = node; } data.remove(0); node.leftChild = createBinaryTree(size, data); node
  • 数据结构—树(Tree)的入门原理以及Java实现案例
    树结构和线性结构的最大的不同是,树中的节点具有明显的层级关系,并且一个节点可以对应多个节点。本文将详细及介绍树这种数据结构的基本概念,以及通用的树的Java实现方式,为后面各种树的深入学习打好基础。 文章目录 1 树的概述1.1 定义1.2 节点1.3 深度和高度1.4 节点的度1.5 有序性 2 树的通用实现2.1 父节点表示法2.2 父子节点链表示法2.3 父子兄弟表示法 3 总结 1 树的概述 1.1 定义   树结构和线性结构的最大的不同是,树中的节点具有明显的层级关系,并且一个节点可以对应多个节点。树的定义如下:   树(Tree)是n(n≥0)个节点的有限集。n=0时称为空树。在任意一棵非空树中: 有且仅有一个特定的称为根(Root)的节点r;当n>1时,其余节点可分为m(m>0)个互不相交的不为空的有限集T1、T2、……、Tm,其中每一个集本身又是一棵树,并且称为根的子树(SubTree)。   从上面树的定义可以看出使用了递归的思想,也就是在树的定义之中还用到了树的概念,根的子树节点,同时作为子树的根节点。递归思想和栈数据结构有关,可以看这篇文章:Java中的栈数据结构详解以及实现和应用案例演示。   如上图,该树具有唯一根节点r,它的子树是以a、b、c为根节点的三棵树。而子树a下面还有一颗子树d。   从递归中我们发现,一棵树是N个节点和N−1条边的集合