1.什么是树？
无向树(树):不含回路的连通无向图
森林:每个连通分支均是树的非连通无向图
平凡树:平凡图
树叶:树中度数为1的顶点
分支点:树中度数大于等于2的顶点，也就是根节点和内点
2.树的相关性质
设G=<V,E>,|V|=n,|E|=m,则下面各命题是等价的:
(1)G连通且不含回路;
(2)G的每对顶点之间有唯一的一条路径; ‘
(3)G是连通的且m=n-1;
(4)G中无回路且m=n-1;
(5)G中无回路,但在任两个不相邻的顶点之间增加一条边,就形成唯一的一条初级回路;
(6)G是连通的且每条边都是桥.
3.树的相关定理
n阶非平凡的树中至少有2片树叶
证明:非平凡树,每个顶点度数都大于等于1,
设有k片树叶,m=n-1
根据握手定理2m>=k*1+(n-k)*2k>=2
4.生成树
(1)生成树:设G=<V,E>是无向连通图,T是G的生成子图并且是树,则称T是G的生成树
G在T中的边称为T的树枝,不在T中的边称为T的弦.
T的所有弦的集合的导出子图称为T的余树（余树不一定是树,也不一定连通）
(2)设n阶连通无向图有m条边，则它的生成树有n一1条边，余树有m-n十1条边.
5.生成树的性质
(1)任何无向连通图都有生成树，只要是连通图就有树
(2)推论:设n阶无向连通图G有m条边,则m>=n-1.（未破圈之前）
6.弦的回路
基本回路:设T是连通图G=<V,E>的一棵生成树,对每一条弦e,存在唯一的由弦e和T的树枝构成的初级回路Ce, 称Ce为对应于弦e的基本回路.
基本回路系统:所有基本回路的集合为对应生成树T的基本回路系统基本回路的个数都等于m-n+1（就是余数的边数）
7.最小生成树
(1)设T是无向连通带权图G=<V,E,W>的生成树，T中所有边的权之和称为T的权,记作W(T).
(2)最小生成树: 带权图权最小的生成树
(3)最小生成树问题是：求任给的无向连通带权图的最小生成树:
求最小生成树的算法：
破圈法：去掉无向连通图中每个回路中的权值最大的边
避圈法 (Kruskal 库斯克算法) —求最小生成树的算法
1)将每条边按权值大小从小到大排列
2)按从小到大依次选取,若形成环则舍去当前选择的边,直到选n-1条边
8.有向树
有向树: 基图为无向树的有向图
根树: 有一个顶点入度为0, 其余的入度均为1的
非平凡的有向树
树根: 有向树中入度为0的顶点
树叶: 有向树中入度为1, 出度为0的顶点
内点: 有向树中入度为1, 出度大于0的顶点
分支点: 出度大于1的点，树根与内点的总称
顶点v的层数: 从树根到v的通路长度（树根为0层）
树高: 有向树中顶点的最大层数
9.家族树:
(1) 若顶点 a 邻接到顶点 b, 则称 b 是 a 的儿子, a是b 的父亲;
(2) 若b和c为同一个顶点的儿子, 则称b和c是兄弟;
(3) 若a≠b且a可达b, 则称a是b的祖先, b是a的后代.
(4)父亲也可以是儿子的祖先
10.根子树:设v为根树的一个顶点且不是树根, 称v及其所有后代的导出子图为以v为根的根子树.
11.有序树: 将根树同层上的顶点规定次序
r叉树:根树的每个分支点至多有r个儿子
r叉正则树: 根树的每个分支点恰有r个儿子
r叉完全正则树: 树叶层数相同的r叉正则树
r叉有序树: 有序的r叉树
r叉正则有序树: 有序的r叉正则树
r叉完全正则有序树: 有序的r叉完全正则树
12.最优二叉树
设2叉树T有t片树叶v1, v2, …, vt, 树叶的权分别为w1, w2, …, wt, 称为T的权, 其中
l(vi)是vi的层数. 在所有权为w1, w2, …, wt 的t片树叶的2叉树中, 权最小的2叉树称为最优2叉树.
最优二叉树的总权=为各顶点的权值与层数乘积之和
求最优2叉树的算法
Huffman（哈夫曼）算法:
给定实数w1, w2, …, wt ,
① 作t片树叶, 分别以w1, w2, …, wt为权.
② 在所有入度为0的顶点(不一定是树叶)中选出两个权最小的顶点, 添加一个新分支点, 以这2个顶点为儿子, 其权等于这2个儿子的权之和.
③ 重复②, 直到只有1个入度为0 的顶点为止.
W(T)等于：
1.所有分支点的权之和
或 2.树叶权值乘以层数之和
13.设a =α1α2…αn-1αn是长度为n的符号串
α的前缀: α1α2…αk , k=1,2,…,n-1,n
前缀码: {β1, β2, …, βm}, 其中β1, β2, …, βm为非空字符串, 且任何两个互不为前缀
2元前缀码: 只有两个符号(如0与1)的前缀码xβα
{0,10,110, 1111}, {10,01,001,110}是2元前缀码 {0,10,010, 1010} 不是前缀码
一棵2叉树产生一个二元前缀码:
对每个分支点, 若关联2条边, 则给左边标0, 右边标1;若只关联1条边, 则可以给它标0(看作左边), 也可以标1(看作右边). 将从树根到每一片树叶的通路上标的数字组成的字符串记在树叶处, 所得的字符串构成一个前缀码.
在这里插入图片描述
最佳2元前缀码:设要传输的电文中含有t个字符, 字符ai出现的频率为pi , 它的编码的长 度为li , 那么n个字符的电文的编码的期望长度是
在这里插入图片描述
称编码期望长度最小的2元前缀码为最佳2元前缀码.
关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。
这里是Ruby新手。完成一些练习后碰壁了。练习:计算一系列成绩的字母等级创建一个方法get_grade来接受测试分数数组。数组中的每个分数应介于0和100之间，其中100是最大分数。计算平均分并将字母等级作为字符串返回，即“A”、“B”、“C”、“D”、“E”或“F”。我一直返回错误:avg.rb:1:syntaxerror,unexpectedtLBRACK,expecting')'defget_grade([100,90,80])^avg.rb:1:syntaxerror,unexpected')',expecting$end这是我目前所拥有的。我想坚持使用下面的方法或.join，
matlab打开matlab，用最简单的imread方法读取一个图像clcclearimg_h=imread('hua.jpg');返回一个数组（矩阵），往往是a*b*cunit8类型解释一下这个三维数组的意思，行数、数和层数，unit8：指数据类型，无符号八位整形，可理解为0~2^8的数三个层数分别代表RGB三个通道图像rgb最常用的是24-位实现方法，即RGB每个通道有256色阶（2^8）。基于这样的24-位RGB模型的色彩空间可以表现256×256×256≈1670万色当imshow传入了一个二维数组，它将以灰度方式绘制；可以把图像拆分为rgb三层，可以以灰度的方式观察它figure(1
在应用开发中，有时候我们需要获取系统的设备信息，用于数据上报和行为分析。那在鸿蒙系统中，我们应该怎么去获取设备的系统信息呢，比如说获取手机的系统版本号、手机的制造商、手机型号等数据。1、获取方式这里分为两种情况，一种是设备信息的获取，一种是系统信息的获取。1.1、获取设备信息获取设备信息，鸿蒙的SDK包为我们提供了DeviceInfo类，通过该类的一些静态方法，可以获取设备信息，DeviceInfo类的包路径为：ohos.system.DeviceInfo.具体的方法如下：ModifierandTypeMethodDescriptionstatic StringgetAbiList()Obt
基础版云数据库RDS的产品系列包括基础版、高可用版、集群版、三节点企业版，本文介绍基础版实例的相关信息。RDS基础版实例也称为单机版实例，只有单个数据库节点，计算与存储分离，性价比超高。说明RDS基础版实例只有一个数据库节点，没有备节点作为热备份，因此当该节点意外宕机或者执行重启实例、变更配置、版本升级等任务时，会出现较长时间的不可用。如果业务对数据库的可用性要求较高，不建议使用基础版实例，可选择其他系列（如高可用版），部分基础版实例也支持升级为高可用版。基础版与高可用版的对比拓扑图如下所示。优势 性能由于不提供备节点，主节点不会因为实时的数据库复制而产生额外的性能开销，因此基础版的性能相对于
我使用irb。下面是我写的代码。“斧头”..“bc”我期待"ax""ay""az""ba"bb""bc"但结果只是“斧头”..“bc”我该如何纠正？谢谢。 最佳答案 >puts("ax".."bc").to_aaxayazbabbbc 关于ruby-从结束值创建一系列字符串，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/7617092/
ruby中有这样的东西吗？send(+,1,2)我想让这段代码看起来不那么冗余ifop=="+"returnarg1+arg2elsifop=="-"returnarg1-arg2elsifop=="*"returnarg1*arg2elsifop=="/"returnarg1/arg2 最佳答案 是的，只需像这样使用send(或者更好的是public_send):arg1.public_send(op,arg2)这是可行的，因为Ruby中的大多数运算符(包括+、-、*、/、andmore)只需调用方法。所以1+2与1.+(2)相同
使用RubyonRails，我使用给定的增量(例如每30分钟)用时间填充“选择”。目前我正在YAML文件中写出所有的可能性，但我觉得有一种更巧妙的方法。我想我想提供一个开始时间、一个结束时间、一个增量，并且目前只提供一个名为“关闭”的选项(想想“business_hours”)。所以，我的选择可能会显示:'Closed'5:00am5:30am6:00am...[allthewayto]...11:30pm谁能想出更好的方法，或者只是将它们全部“拼写”出来的最佳方法？ 最佳答案 此答案基于@emh的答案。defcreate_hour
情况:我正在编写一个程序来求解素数。我需要解决4x^2+y^2=n的问题，其中n是一个已知变量。是的，必须是Ruby。我愿意在这个项目上花费大量时间。我最好自己编写方程式的求解算法，并将其作为该项目的一部分。我真正喜欢的是:如果任何人都可以向我提供指南、网站的链接，或者关于与求解代数方程特别相关的形式算法的构造的歧义消除，或者向我提供似乎你是读者它会帮助我完成任务。请不要建议我使用其他语言。如果您在回答之前接受我真的非常想这样做，我将不胜感激。该项目没有范围或时间限制，也不以营利为目的。这是为了我自己的教育。注意:我并不直接反对为Ruby实现和使用现存的数学库/模块/其他东西，但我更喜
我发现许多Rails应用程序主要针对企业、社交网络类型的Web应用程序。我看到有人将Ruby与一些出色的OOPS语言(如Java和C#)进行了比较，但我确实发现很难获得一些数学密集型应用程序。非常感谢任何知识渊博的输入(指向示例程序的链接等)，其中轻松显示了语言的用法，就像快速启动或显示该语言如何用于各种数学问题一样。 最佳答案 不幸的是，Ruby并没有在数学和科学计算领域涉足太多。目前，有一个名为SciRuby的pre-alpha库它试图为Ruby带来更多面向数学的功能。他们正试图构建一个NumPy/SciPy等价物。SciRub
