欢迎来到 Claffic 的博客 💞💞💞
前言：
上一期给大家讲了树的基本概念和特点，现在可以试着回忆一下树的样子，还有一些关系称谓。那么今天要讲的，是二叉树，是一种特殊且实用的树，是不是有些小期待呢！
目录
先来回顾下树：倒置的，根在顶端，向下分岔... ...
所谓二叉树，二叉嘛，就是有两个叉子呗：
一颗简单的二叉树
还真是，简单说，它就是每个结点最多能分两个叉的树。
一棵二叉树是结点的一个有限集合：
• 或者为空 • 由一个根节点加上两棵别称为左子树和右子树的二叉树组成
二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
那么二叉树是不是只有二叉的情况呢？
其实并不是，下面总结二叉树的几种单元形态：
任意一种二叉树都可以由上面的形态复合而成。
这是一种特殊的二叉树
满，意味着除根节点以外的结点都拥有左右结点(子树)，即每一层的结点数达到最大值。
例：满二叉树
非常完美的二叉树~
如果设它的高度为K，那么它共有2^K-1个结点，同样可以用这条性质来判断是否为满二叉树。
这种树相比满二叉树就有些空缺了，
但是空的结点也有讲究：
从二叉树末端(右下角)开始，空到这一层的任意位置，保证空结点不间断。
换句话说，最后一层的结点都仅靠左部。
例：完全二叉树
它的准确的定义是：
对于深度为 K的，有n 个结点的二叉树，当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点。
要注意：满二叉树是一种特殊的完全二叉树，完全二叉树的范围更广一些。
• 若规定根节点的层数为 1 ，则一棵非空二叉树的 第 i 层上最多有 2^(i-1) 个结点。
最多就是满的情况，层的编号与每层最多结点的个数关系：Ni = 2^(i-1)；
可以联想一下有丝分裂... ...
• 若规定根节点的层数为1 ，则 深度为 h 的二叉树的最大结点数是2^h-1
这里就是一个等比数列求和，
在完全二叉树的情况下，第一层到第h层的结点个数：
2^0，2^1，2^2，2^3，... ... 2^(h-1)
求和：
Nh = 2^0+2^1+2^2+2^3+...+2^(h-1)
通过错位相减求和得到结点总数：
Nh = 2^h-1
• 对任何一棵二叉树， 如果度为 0 其叶结点个数为n0 , 度为 2 的分支结点个数为n2 , 则有 n0 = n2＋ 1
这个可以简单找找规律：
可以发现叶子结点的个数总比度为2的结点个数多1
• 若规定根节点的层数为 1 ，具有 n 个结点的满二叉树的深度 ， h = log2(n+1) 【log2(n+1)是以2为底，n+1的对数】
其实就是按之前求最大个数的式子 Nh = 2^h-1 把h表示出来，一个意思
• 对于具有n 个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从 0 开始编号，则对于序号为i 的结点有： 若 i>0 ， i 位置节点的双亲序号： (i-1)/2 ； i=0 ， i 为根节点编号，无双亲节点 若 2i+1<n ，左孩子序号： 2i+1 ， 2i+1>=n 否则无左孩子 若 2i+2<n ，右孩子序号： 2i+2 ， 2i+2>=n 否则无右孩子
可以看看这个标记：
所谓顺序存储，就是以数组来实现二叉树。
欸？用数组来实现二叉树，
其实这个跨度还蛮大的，心里想的是链型的，实际实现却是用数组这种顺序结构。
这里用 逻辑结构 和 物理结构 来分别表示：
逻辑结构就是心里想的，物理结构就是实际实现需要的
这种存储结构适用于满二叉树，因为满二叉树不会有数组空间的浪费。
顺序存储中有一个典型的数据结构叫做堆(一种二叉树，此堆非彼堆，彼堆是操作系统中管理内存的一块区域分段)，这里放到下期讲解。
这个链式存储就是正常的思路了：
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;这里定义一棵二叉树树的基本结构：
要存储的数据，指向左子树的指针，指向右子树的指针。
所以根据左右孩子的关系就可以创建一颗二叉树：
根据左右孩子关系创建的一颗简单二叉树
链式结构方便在遍历，后期会讲解二叉树的遍历。
总结：
这篇博客给大家介绍了二叉树，更加偏向理论层面，那么下期就会带大家敲代码实现一些特殊的二叉树：堆，二叉树的遍历等等。
码文不易
如果你觉得这篇文章还不错并且对你有帮助，不妨支持一波哦 💗💗💗
我一直在尝试在Ruby中实现BinaryTree类，但我得到了stackleveltoodeep错误，尽管我似乎没有在该特定代码段中使用任何递归:1.classBinaryTree2.includeEnumerable3.4.attr_accessor:value5.6.definitialize(value=nil)7.@value=value8.@left=BinaryTree.new#stackleveltoodeephere9.@right=BinaryTree.new#andhere10.end11.12.defempty?13.(self.value==nil)?true:
作者|Harper审核 |gongyouliu编辑|auroral-L机器学习的商业应用上期给大家介绍了机器学习的概念，但是理解机器学习最好方法之一，就是了解其在具体商业世界中的各种应用。在道格’罗斯的这本《认识AI，人工智能赋能商业》中，介绍了几类机器学习的商业应用，在这里我给大家归纳一下。第一，数据安全，为了避免被发现，制造恶意软件的人会不断更改代码，通常为2%~10%的修改，但是通过机器学习，安全软件可以适应这一小部分变化，并准确识别新创建的恶意软件。它还可以寻找访问方式的模式，以识别可能的安全威胁。第二，投资。机器学习使得计算机能够处理大量的财务数据，并利用其发现的规律预测市场及每只股
我知道在Ruby中我可以使用respond_to?来检查一个对象是否有特定的方法。但是，给定类，我如何检查实例是否具有特定方法？例如，类似Foo.new.respond_to?(:bar)但我觉得必须有比实例化新实例更好的方法。 最佳答案 我不知道为什么每个人都建议你应该使用instance_methods和include?什么时候method_defined?完成工作。classTestdefhello;endendTest.method_defined?:hello#=>true注意如果您是从另一种OO语言转向Ruby，或者您认
一.认识四位共阴极数码管（1）一位八段共阴极数码管 在认识四位共阴极数码管之前我先介绍一下一位八段共阴极数码管。如左图所示为以为数码管的实物图，其中它共有10个引脚，且上下各五个。小数点位于右下时为数码管正面，在四位共阴极数码管中也是如此，在连接组装时尤为重要。 右图所示为一位数码管示意图，将数码管引脚连接在Arduino上，由图所示我认为你可以对为什么是八段及共阴极有了自己一定的理解。其中，共阴极顾名思义是这些LED小灯公用一个阴极。对于如何在一位数码管上显示0-9，也就是指点亮数码管上位置不同的LED小灯。例如：显示0，点亮a,b,c,d,e,f，也就是将其对应的引脚2，3，
平凡、常见的用例我想要一个工具提示，它在鼠标悬停时立即显示正在加载的GIF，该GIF被AJAX成功回调产生的HTML所取代。AJAX工具提示的错误答案几乎与在线问这个确切问题的人一样多。特别是，我一直在模拟我在this上的努力。,this，尤其是几个答案here.对于所有这些解决方案(即使是那些专门声称可以解决该问题的解决方案)，我一直遇到的问题是，工具提示偶尔会延迟出现并且无法消失。这也不是库问题，因为我过去在使用jQuery-UI工具提示时遇到过同样的问题。图书馆jQueryv2.2.3Bootstrapv3.3.6之前尝试过使用jQuery1并遇到了同样的问题:jQueryv1.
我一直在研究这个:https://github.com/mikechambers/ExamplesByMesh/blob/master/JavaScript/QuadTree/src/QuadTree.js我相信我理解四叉树的一般概念，尽管我对它们的工作原理和上面的实现有两个问题:难道你不需要每隔几毫秒重建整个树吗？在Javascript中，这不会非常慢吗？如果我有这样的东西:http://davzy.com/screenshots/skitched-20120318-180324.png，那么很容易找到同一个四边形中的其他点，但我有一个矩形与3个不同的四边形相交，有没有办法让它显示为
1.1线索二叉树的原理我们现在倡导节约型社会，一切都应该以节约为本。但当我们创建二叉树时我们会发现其中一共有两个指针域，有的指针域指向的结构为空，这也就浪费了很多空间。所以为了不去浪费这些空间我们采取了一个措施。就是利用那些空地址，存放指向结点在某种遍历次序之下的前驱和后继结点的地址。就好像GPS导航仪一样，它可以告诉我们下一站是哪里，我们是从那里来的。我们把这种指向前驱和后继的指针成为线索，加上线索的二叉链表称为线索链表，相应的二叉树就成为线索二叉树。我们将对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。下图是线索化结束的图：这里存在一个问题，我们怎么知道某一个结点的lchild是
最近ChatGPT这么火，那就让他给我写点代码吧。如何注册一个账号，参考：注册ChatGPT详细指南注册不了的小伙伴们，咱们评论区见，问一个最想问的问题，看到就给你回复！我已经注册好了，下面直接开始白嫖代码！Part1给的例子十分简单，并且中文乱码，且没有声音和图片。代码：DOCTYPEhtml>html>head>title>圣诞节title>style>body{background-color:#f5f5f5;}img{display:block;margin:0auto;}h1{text-align:center;font-family:sans-serif;color:#0066c0
Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。🌈个人主页：主页链接🌈算法专栏：专栏链接 我会一直往里填充内容哒！🌈LeetCode专栏：专栏链接 目前在刷初级算法的LeetBook。若每日一题当中有力所能及的题目，也会当天做完发出🌈代码仓库：Gitee链接🌈点击关注=收获更多优质内容🌈目录题目:111. 二叉树的最小深度题解:代码实现:题目:700. 二叉搜索树中的搜索题解:代码实现:题目:701. 二叉搜索树中的插入操作题解:代码实现:题目:450. 删除二叉搜索树中的节点题解:代码实现:完结撒花：人生苦短，
我正在尝试学习/理解一些基本算法，今天我决定用Go编写一个二叉树。这是结构的样子:typeNodestruct{ValueintLeft*NodeRight*Node}这是我检查树是否包含int的函数:func(tree*Node)Contains(valint)bool{ifval==tree.Value{returntrue}elseifval>tree.Value{iftree.Right!=nil{returntree.Right.Contains(val)}else{returnfalse}}elseifval我写了一个测试函数来测试对树的不同操作需要多长时间。我的Inser