[Powered by Google Translate] [第7条] [舒适]
内特 - 哈迪森] [哈佛大学]
这是CS50。[CS50.TV]
>> 欢迎来到第7。
由于飓风沙地，
有一个正常的部分，而不是本周，
我们这样做是步行通过，通过的部分问题。
我要跟着问题设置6规格，
和经历中的问题
A组的问题部分。
如果有任何问题，
请上发布这些CS50讨论。
>> 好吧。让我们开始吧。
现在，我期待在第3页的习题集规范。
我们将第一次开始谈论二叉树
因为有很多这一周的问题集中相关 -
Huffman树的编码。
我们谈到CS50的第一个数据结构的数组。
请记住，数组是一个序列的元素 -
所有相同类型的 - 彼此旁边存储在内存中。
如果我有，我可以得出一个整数数组使用这盒数的整数风格 -
比方说，我在第一个框中有5个，我有7个在第二，
然后，我有8个，10和20在最后中。
记住，真正的好东西，关于这个数组
是，我们有这个固定时间的任何特定元素的访问
在阵列中，如果我们知道它的索引。
例如，如果我想要抓住的第三个元素的数组 -
索引2处使用我们的从零开始的索引系统 -
我真的只是做一个简单的数学计算，
跳，在数组中的位置，
拔出存储8，
我好到哪里去。
>> 这个数组的一个不好的地方 - 我们谈论
当我们讨论链表 -
是，如果我想这个数组中插入一个元素，
我将做一些转移周围。
例如，该阵列在这里
在排序 - 升序排序 -
5，然后7，然后是8，然后10，然后20 -
但如果我要插入到这个数组中的数字9，
我将不得不改变一些元素，以腾出空间。
我们可以得出这样的在这里。
我要移动5星，7，然后是8;
创建一个差距在哪里，我可以把9，
，然后在10和20可以去的9的权利。
这是一种痛苦，因为在最坏的情况下 -
当我们插入的开始或结束时
数组，取决于我们如何转变 -
我们可能最终不得不将所有的元素
我们目前存储在数组中。
>> 那么，究竟是什么办法解决这个问题？
解决这个问题的办法是去我们的链表方法 -
代替存储元件5，7，8，10和20的所有在内存中彼此旁边 -
是我们，而不是没有被存储他们种的地方，我们希望将它们存储
我在这些链表节点绘制出在这里，种专案。
然后我们使用这些next指针连接在一起的。
我可以有一个指针从5到7，
从7到8的指针，
从8到10的指针，
最后，从10到20，一个指针
然后在20表示一个空指针，有什么也没有留下。
说，我们这里的权衡
是，现在如果我们要插入到我们的排序列表中的数字9，
所有我们要做的是创建一个新的节点9，
它添加到相应的地方，
，然后再线8点到9。
这是相当快的，如果我们确切地知道我们要插入的9。
但权衡，以换取这是我们现在已经失去了固定时间的访问
任何特定的元素在我们的数据结构。
例如，如果我想找到这个链表中的第四个元素，
我要开始在一开始的列表
通过计算节点的节点，直到我找到工作，我的第四个。
>> 为了获得更好的访问性能比链表 -
但也保留了一些的好处，我们有
在一个链表插入时间方面 -
一个二叉树将需要使用多一点的内存。
在特定的，而不是仅仅有一个二叉树结点的指针 -
，如链表节点 -
我们要添加第二个指针的二进制树节点。
而不是仅仅有一个指针指向下一个元素，
我们将有一个左孩子和右孩子指针。
>> 让我们来画一幅画，看什么，实际上看起来像。
同样，我要使用这些方框和箭头。
二叉树节点将开始只是一个简单的框。
这将有空间的价值，
然后它也有一个空格的左孩子和右孩子。
我要在这里贴上标签。
我们将有左孩子，然后我们要正确的孩子。
这样做有很多不同的方式。
有时空间与便利性，
实际上，我会像我在这里做的底部画
我要去的地方在顶部的价值，
然后右子上的右下角，
和左子节点上的左下方。
回去这个顶部图，
我们的价值在最高层，
然后我们有左孩子指针，然后我们有右孩子指针。
>> 在问题设置规范，
我们谈论绘制一个节点，有一个价值7，
然后左子指针，该指针是空值，和一个右子节点指针为null。
我们可以写资本NULL的空间
无论是左孩子和右孩子，或者我们可以得出这样的斜线
通过每个框的，以表明它是空的。
我要做的，只是因为这是简单的。
你在这里看到的是一个很简单的二进制树节点的绘图两种方式
我们的价值和空的子结点指针。
>> 我们的规范谈如何用链表的第二部分 -
请记住，我们只需要保持在列表中的第一个元素
记得整个列表 -
同样地，用二叉树，我们只有坚持一个指针指向树
为了保持控制在整个数据结构。
这种特殊的元件被称为树的树的根节点。
例如，如果这一个节点 - 包含该值的7此节点
空的左和右孩子指针 -
在我们的树是唯一的价值，
那么这将是我们的根节点。
这是一开始我们的树。
我们可以更清楚地看到这一点，一旦我们开始将更多的节点添加到树中。
让我牵了新的一页。
>> 现在，我们要画一棵树，有7根，
3内的左孩子，和9的右子内。
再次，这是非常简单的。
我们已经拿到了7，为3，绘制一个节点一个节点9，
我要设置的左孩子指针指向的节点包含3，
和含有7到节点含有9的节点的右子节点指针。
现在，因为3和9没有任何儿童，
我们要设置其所有的子结点指针为空。
这里，我们的树的根目录对应到含的节点的数目7。
你可以看到，如果我们所拥有的是一个指针，该根节点，
然后，我们可以步行通过我们的树和访问这两个子节点 -
3和9。
没有需要保持树的每一个节点上的指针。
好吧。现在，我们要到另一节点添加到这个图。
我们要添加一个节点包含6，
我们要添加为右子节点包含3。
要做到这一点，我要抹去空指针在3个节点
，并将其连接到指向的节点包含6。好吧。
>> 在这一点上，让我们去一点点的术语。
要启动的原因，这就是所谓的二进制树，特别是
是，它有两个子结点指针。
还有其他类型的树木，有更多的孩子指针。
特别是，你做了习题集5“尝试”。
你会发现，在试图，不同的孩子有27个不同的指针 -
在英语字母表的26个字母，
然后在27日的所有格符号 -
所以，这是一种类型的树相似。
但在这里，因为它是二进制的，我们只能有两个子结点指针。
>> 除了我们刚才谈到这个根节点，
我们也被扔围绕这个词的孩子。“
一个节点是一个孩子的另一个节点是什么意思？
它的字面意思，子节点是孩子的另一个节点
如果其子结点指针设置为指向该节点，其他节点有一个。
为了把这个更具体的条款，
如果有3所指向的孩子指针7，然后是一个孩子的7。
如果我们要弄清楚什么是儿童的7 -
好，我们看到，7具有指针3至9和一个指针，
所以9和3的孩子7。
九无儿无女，因为它的子结点指针是空的，
3只生育一个孩子，6。
六还没有孩子，因为它的指针是空的，现在我们将绘制。
>> 此外，我们还谈论一个特定节点的父母，
这是，正如你所期望的，这个孩子描述的相反。
每个节点只有一个父 - 你可能期望与人类，而不是两个。
例如，父3是7。
的父9也是7，和3的父6是。没有太多的不同。
我们也有谈论的祖父母和孙子女的条款，
更普遍的是，我们谈论的祖先
特定节点的后裔。
一个节点的祖先 - 祖先，而是一个节点 -
是位于从根到该节点的路径上的所有节点。
例如，如果我期待在节点6，
然后祖先都将是3和7。
的祖先，例如，9 - 如果我在寻找的节点9 -
然后的祖先9 7。
及后裔刚好相反。
如果我想看7的后裔，
然后，我要看看它下面的所有的节点。
所以，我有3，9，和6 7所有的后裔。
>> 最后一个学期，我们将谈论的是这个概念的兄弟姐妹。
兄弟姐妹 - 种这些家庭的条款 -
的节点树中，在同一水平。
因此，图3和图9是同级的，因为他们是在树中的相同的水平。
他们都具有相同的父，7。
6有没有兄弟姐妹，因为没有任何儿童。
7并没有任何兄弟姐妹，因为它是我们的树的根，
而且也只有1根。
在未来的7到有兄弟姐妹就必须在7以上是一个节点。
将必须是有一个父如图7所示，在这种情况下，7将不再是树的根节点。
7新的母公司也必须有一个孩子，
和那个孩子，然后是兄弟姐妹7。
>> 好吧。移动。
当我们开始讨论二叉树，
我们谈到了我们如何去使用它们来
获得数组和链表的优势。
的方式，我们要做到这一点，是这个顺序属性。
我们说，一个二进制树是有序的，根据本说明书，
如果在我们的树的每个节点，其后代在左侧 -
左子的左子的后裔 -
有较小的值，并且在右边的所有的节点 -
右边的孩子和右孩子的后裔 -
有节点大于当前节点的值，我们正在寻找。
简单起见，我们将假设在我们的树，不会有任何重复的节点。
例如，在这棵树中，我们要处理的情况下，
我们有7根
那么我们也必须值7在树中的其他地方。
在这种情况下，你会发现，这棵树确实是有序的。
我们有7根。
一切以左侧的7 -
如果我取消所有的这些小标记 -
一切左侧的7 - 在3和6 -
这些值都小于7，一切的权利 - 这仅仅是这9 -
大于7。
>> 这不是唯一的有序树包含这些值，
但让我们画一些更多的人。
其实是有一大堆的方法，我们可以做到这一点。
我要使用速记，只是为了让事情简单的地方 -
而不是整个框和箭头 -
我只是要绘制的数字和箭头连接。
开始，我们就写我们原来的树又在哪里，我们有7个，然后3，
然后3指出返回到6的权利，
孩子有权利为9。
好吧。另一种方式，我们可以写这棵树什么？
而不是有3的左子7，
我们也可以有6左子7，
然后是左子6。
这看起来像这棵树在这里我得到了7，
然后6，然后3，和一个9右侧列表。
我们也不必作为我们的根结点中有7个。
我们也可以作为我们的根节点。
那么，具体怎么样的？
如果我们要保持这种有序的属性，
6左侧的一切有小于它。
只有一个可能，那就是3。
但是，当6的右孩子，我们有两种可能性。
首先，我们可以有7，然后9，
或者我们可以借鉴 - 就像我要在这里做的 -
我们有9 6的右子，
然后7的左子9。
>> 现在，图7和图6是不是唯一可能的值为根。
我们还可以有3根。
如果是在根会发生什么情况呢？
在这里，事情就变得有点有趣。
三不小于它的任何值，
使整个左侧的树是为空。
不会是什么。
的权利，我们可以列出按升序排列。
我们可以有3，然后按6，然后按7，然后9。
或者，我们可以做3，然后6，然后按9，然后7。
或者，我们可以做3，然后按7，然后6，然后按9。
，3，7 - 其实也没什么，我们不能做了。
这是我们的一件事。
我们可以做9，然后从9中，我们可以做6，然后7。
或者，我们可以做3，然后按9，然后7，然后6。
>> 提请您注意，这里的一件事是
这些树是一个有点怪异的前瞻性。
特别是，如果我们看一下右侧的4棵树上的 -
我会圈，这里 -
这些的树木看起来几乎完全一样的一个链表。
每个节点都只有一个孩子，
所以我们不具有任何类似树的结构，我们看到，例如，
在这一个孤独的树在这里的左下角。
事实上，这些树被称为退化二进制树，
我们将讨论这些更多的未来 -
特别是如果你采取其他的计算机科学课程。
这些树是退化的。
他们不是非常有用的，因为事实上，这种结构本身
类似于一个链表的查找时间。
我们没有得到充分利用额外的内存 - 这额外的指针 -
因为我们的结构，这种方式是坏的。
而不是去和画出来的二进制树，有9根，
这是最后的情况下，我们将不得不，
，在这一点上，而不是我们要谈一点点关于这个其他条款
我们使用时，谈论的树，这被称为高度。
>> 树的高度是从根到的最遥远的节点的距离，
或者更确切地说，跳数，你将不得不作出以
从根开始，然后结束在最遥远的树中的节点。
如果我们看一下这些树在这里，我们已经制定，
我们可以看到，如果我们采取这种树在左上角，我们开始在3，
然后，我们有1跳6，第二跳的7，
和三分之一一跳得到的9。
所以，这种树的高度是3。
我们可以做同样的练习，概述了这个绿色的树木，
我们看到，所有这些树的高度也确实是3。
这是什么使他们堕落的一部分 -
它们高度仅仅是一个小于在整个树中的节点的数目。
如果我们看看这树用红色包围，另一方面，
我们看到，最远处的叶节点是6和9 -
的叶子有没有孩子的节点。
所以，为了得到从根节点到6或9，
我们必须做出一个跃点得到的7，然后得到的第二跳到9，
同样地，只有一个第二跳从7到6。
因此，这棵树的高度，在这里只有2个。
你可以回去和做到这一点，我们前面所讨论的所有其他树木
开始与7和6，
你会发现，所有这些树的高度也是2。
>> 究其原因，我们一直在谈论有序二元树
以及为什么他们很酷，是因为你可以搜索他们的
在一个排序的数组中搜索一个非常类似的方式。
这是我们谈论获得该改进的查找时间
在简单的链表。
通过链接的列表中 - 如果你想找到一个特定的元素 -
你最好做某种线性搜索
你从哪里开始的一个列表，跳一个接一个开始 -
一个节点由一个节点 -
整个列表，直到你发现你要寻找的。
然而，如果你有一个二叉树的存储在这个漂亮的格式，
实际上，你可以得到更多的二进制搜索
分而治之
通过适当的一半在每一步的树和搜索。
让我们来看看它是如何工作。
>> 如果我们有 - 再次，要回我们原来的树 -
我们从7点开始，我们有3个在左侧，9的右边，
和下方的3，我们有6。
如果我们想要搜索的数量在这棵树，我们就从根开始。
我们将比较的价值，我们要寻找的，说6，
在节点中存储的值，我们目前正在观察，7，
找到6是确实小于7，所以我们会向左侧移动。
6如果该值大于7，我们将，而不是移动到右侧。
因为我们知道 - 由于我们的排序二叉树的结构 -
所有的值小于7的将被存储到7的左侧，
有没有必要通过右侧的树，甚至懒得看。
一旦我们移动到左边，我们现在在节点3，
我们比较了3和6，我们可以再次做同样的比较。
我们发现，6 - 我们正在寻找的价值 - 大于3，
我们可以去含有3的节点的右侧。
这里有没有左侧，因此，我们可以忽略了。
但是，我们只知道，因为我们正在寻找在树的本身，
我们可以看到，树有没有孩子。
>> 这也很容易看在这棵树，如果我们这样做，我们自己作为人类，
但机械，让我们按照这个过程就像一台计算机做
要真正理解算法。
在这一点上，我们现在看到的一个节点，其中包含6，
我们正在寻找的价值6，
因此，事实上，我们已经找到了合适的节点。
我们发现，在我们的树，和值6，我们可以停止我们的搜索。
在这一点上，这是怎么回事，
我们可以说，是的，我们已经找到了价值6，它存在于我们的树。
或者，如果我们打算插入一个节点，或者做了什么，我们可以做的，在这一点。
>> 让我们做一对夫妇更多的查询只是为了看看它是如何工作的。
让我们来看看会发生什么，如果我们要尝试，并期待值10。
如果我们要查找的值是10，我们从根开始。
我们会看到，10比7，所以我们要移动到右边。
我们会得到的9与比较9到10，请参阅图9是确实小于10。
所以，再一次，我们会想办法移动到正确的。
但在这一点上，我们会发现，我们正处在一个空节点。
什么也没有。其中10应该是没有什么。
这是我们可以报告失败 - 这确实是树中的10号。
最后，让我们通过的情况下，我们试图查找树中的。
这是会发生什么，如果我们看一下上涨了10，除了要正确的，而不是相似，
我们要去去左边。
首先，我们在7和1小于7，所以我们向左侧移动。
我们得到的3和1小于3，所以我们再次尝试移动到左边。
在这一点上，我们有一个空节点，所以我们可以再一次失败。
>> 如果你想了解更多有关二进制树，
有一大堆有趣的小问题，你可以与他们无关。
我建议实行这些图一
和之后通过的所有的不同步骤，
因为这会在超级方便
不仅是当你在做的霍夫曼编码问题集
而且在未来的课程 -
只是在学习如何绘制出这些数据结构和思考的问题
笔和纸，在这种情况下，iPad和手写笔。
>> 虽然在这一点上，我们要继续前进做一些编码实践
玩这些二进制树和看到的。
我要切换回我的电脑。
对于这部分的部分，而不是使用CS50运行或CS50空间的，
我要使用的设备。
>> 之后随着习题集的规格，
我看我应该打开的设备，
去我的Dropbox文件夹，创建一个文件夹，名为第7，
然后创建一个名为binary_tree.c。
在这里，我们走了。我有的家电已经打开。
我要拉一个终端。
我要到Dropbox文件夹，创建一个目录称为第七条第
这是完全空的。
现在，我要开拓binary_tree.c。
好吧。在这里，我们走 - 空文件。
>> 让回去的规范。
该规范要求，以创建一个新的类型定义
包含int值的二进制树节点 -
一样的价值，我们在我们的图表前抽出。
我们将使用这个样板的typedef，我们在这里做了
你应该认识到，从习题集5 -
如果你做了哈希表的方式征服了拼写检查程序。
你也应该认识到它从上周的部分
我们谈到链表。
我们走了这么一个结构节点的typedef，
，我们给这个结构节点结构节点名称事先
所以，我们就可以引用它，因为我们会希望有结构的节点指针
我们的结构的一部分，但我们已经包围这 -
或者更确切地说，附上 - 一个typedef
这样一来，后面的代码中，我们可以参考这个结构只是一个节点，而不是一个结构节点。
>> 这将是非常相似的单链表的定义，我们看到上周。
要做到这一点，我们刚开始写的样板。
我们知道，我们必须有一个整数值，
所以我们把int值，然后，而不是只是一个指针指向下一个元素 -
我们做的单链表 -
我们将有左，右孩子指针。
这是非常简单 - 节点左孩子;
和节点右子树。酷。
这看起来是一个不错的开始。
让回去的规范。
>> 现在，我们需要声明一个全局变量节点*树的根。
我们将会使这个全球性的，就像我们第一个指针链表也是全球。
这是如此，在我们写的功能
我们不必通过围绕这根 -
虽然我们会看到，如果你想递归写的这些功能​​，
它可能会更好，甚至没有传递它作为一个全球性摆在首位
，而不是在本地初始化它的主要功能。
但是，我们会做它在全球范围内启动。
同样，我们将一对夫妇的空间，我要声明一个节点*根。
只是，以确保我不离开这个未初始化的，我将它设置为null。
现在，在主要功能 - 我们会写的真的很快在这里 -
INT主要（INT ARGC，为const char *的argv []） -
我要开始我的argv数组声明为const只是让我知道
这些参数是，我可能不希望修改的参数。
如果我想修改我也许应该副本。
你会看到这是一个很大的代码。
这是无论哪种方式。它的优良把它作为 - 省略cons​​t如果你想。
我通常把它放在这样我提醒自己
我可能不希望修改这些参数。
>> 与往常一样，我要包括的主要在0线。
在这里，我将我的根节点初始化。
既然这样，现在，我有一个指针，该指针被设置为空，
因此，它指向不惜一切代价。
为了真正开始建设的节点，
我首先需要为它分配内存。
我要做到这一点，使内存使用malloc在堆上。
我要设置root的malloc的结果，
我，我会用sizeof运算符的大小来计算的节点。
究其原因，我使用sizeof节点，而不是，比方说，
做这样的事情 - 的malloc（4 +4 +4）或malloc 12 -
是因为我想我的代码是尽可能地兼容。
我希望能够借此c文件，在设备上编译它，
然后编译它在我​​的64位Mac -
或在一个完全不同的架构 -
我想这一切都是为了工作。
>> 如果我的假设变量的大小 -
一个int或一个指针的大小尺寸 -
然后我也假设有关的各种架构
我的代码可以成功编译运行。
始终使用sizeof，而不是手动总结的结构域。
另一个原因是，也有可能是，编译器将结构体的填充。
即使只是总结的各个字段，您通常需要做的事情，
因此，删除该行。
现在，要真正初始化这个根节点，
我要为每个不同领域的价值有堵塞。
例如，我知道我要的值初始化为7，
现在我要设置的左孩子为空
和孩子也为空。太好了！
我们已经这样做了部分的规范。
>> 规格在第3页的底部，问我到创建三个节点 -
一个含有3，一个含有6，和一个与9 -
然后将它们连接起来，所以它看起来完全像我们的树形图
我们都在谈论以前。
现在让我们来很快在这里。
你会看到，真的很快，我要开始写一堆重复的代码。
我要创建一个节点*，我会打电话给它3。
我将它设置为等于对malloc（如sizeof（节点））。
我要设置三个值= 3。
三 - > left_child = NULL; 3 - >右键_child = NULL;以及。
这看起来非常相似初始化的根，这正是
我会做，如果我开始初始化第6和第9。
我会做的真的很快在这里 - 其实，我打算做一个小的复制和粘贴，
，并确保我 - 好吧。
现在，我已经把它复制，我可以去进取，这等于6。
你可以看到，这需要一段时间，而不是超高效。
只是一点点，我们将编写一个函数，我们将做到这一点。
我想更换了9，将其更换为6。
>> 现在我们已经得到了我们所有的节点创建和初始化。
我们有我们的根设置等于7，或包含该值的7，
我们的节点3，节点6，节点包含9。
在这一点上，我们需要做的是线的一切行动。
我初始化的指针为NULL的原因是，只是让我确保
我没有任何未初始化的指针，在那里意外。
还因为，在这一点上，我只有实际连接的节点彼此 -
那些他们实际上是连接到 - 我没有去，并
确保在适当的地方，所有的零点都在那里。
>> 从根开始，我知道根的左孩子是3。
我知道根的右孩子是9。
之后，其他的孩子，我已经离开了担心
3的右孩子，这是6。
在这一点上，它看起来很不错。
我们将删除这些行。
现在，一切都看起来很不错。
让我们回到我们的规范，看看我们下一步需要做的。
>> 在这一点上，我们必须写一个函数叫做'包含'
“布尔包含（int值）的原型。
这包含函数将返回true
如果树指出，我们在全球的根目录变量
包含的值传递到功能，否则返回false。
让我们继续这样做。
这将是完全一样的查找，我们没有在iPad上只是一点点前的手。
让我们在一点点放大，向上滚动。
我们打​​算把这个功能超出了我们的主要功能
所以，我们没有做任何形式的原型设计。
因此，布尔（int值）。
我们走吧。这就是我们的样板声明。
只是为了确保这将编译，
我要继续前进，就设置它等于返回false。
现在这个功能只是不会做任何事情，总是报告说，
我们正在寻找的价值是不是在树中。
>> 在这一点上，它可能是一个好主意 -​​
因为我们已经写了一大堆的代码，我们甚至还没有尝试过测试，但 -
以确保所有编译。
有一对夫妇的事情，我们需要做的，以确保这实际上将编译。
首先，看看我们是否已经使用在任何图书馆的任何功能，我们还没有计算在内。
的功能，我们一直使用的是malloc的，
然后，我们也一直在使用这种类型的 - 这非标准型名为“bool'的 -
它包含在标准的bool头文件。
我们一定要到包括标准bool.h的为bool类型，
我们也希望＃标准库包括标准的lib.h
包括malloc和自由，所有这一切。
因此，缩小，我们要退出。
让我们尝试作出肯定，这确实编译。
我们可以看到它，所以我们在正确的轨道。
>> 让我们再次打开binary_tree.c。
它编译。让我们下去，并确保我们将我们的包含函数调用 -
只是为了确保一切都很好，好。
例如，当我们做了一些我们的树中查找，
我们试图寻找的值6，10，1，我们知道在树中，
10，是不是在树中，1个是不是在树中。
让我们用这些样本要求，以此来找出是否
我们包含了功能是否正常工作。
为了做到这一点，我要使用printf函数，
我们要打印出包含调用的结果。
我打算把字符串中的“包含（D）=因为
我们将插头的价值，我们要去看看，
=％S \ n“，并用它作为我们的格式化字符串。
我们只是从字面上看 - 在屏幕上打印出 -
什么看起来像一个函数调用。
这是不是真正的函数调用。
这仅仅是一个字符串，看起来像一个函数调用。
>> 现在，我们要插入的值。
我们将尝试包含6，
然后我们要在这里做的是使用该三元运算符。
让我们来看看 - 包含6 - 所以，现在我已经含有6个，如果包含6个是真实的，
，我们将发送到％s格式字符的字符串
将是字符串“true”。
让我们多一点点滚动。
否则，我们要发送的字符串“false”，如果包含6个返回false。
这是一个有点愚蠢的前瞻性，但我想我还不如说明
三元运算符看起来像什么，因为我们还没有看到它一段时间。
这将是一个不错的，方便的方法计算出，如果我们的工作包含函数。
我要滚动到左边，
我要复制和粘贴这行几十倍。
它改变了一些值左右，
所以这会是1，而这将是10。
>> 在这一点上，我们已经有了一个很好的包含函数。
我们已经有了一些测试，我们将看到如果这一切工作。
在这一点上，我们已经写了一些代码。
退出时间，确保一切都还编制。
退出了，现在让我们尝试再次二叉树。
好了，看起来我们已经得到了一个错误，
我们已经得到了这个显式声明的库函数printf的。
看起来我们需要去和＃include standardio.h。
有了这样的，一切都应该编译。我们都很好。
现在，让我们尝试运行的二进制树，看看会发生什么。
我们在这里，/ binary_tree，
我们看到，正如我们的预期 -
因为我们还没有实现，还包含，
或者说，我们刚刚返回false -
我们可以看到，它只是返回false，所有的人，
所以这一切都工作在大多数情况下，相当不错。
>> 让我们回去，真正实现包含在这一点上。
我要向下滚动，放大， -
请记住，我们所使用的算法是，我们的根节点开始
然后我们遇到的每个节点，我们做了比较，
并根据对这样的比较中，我们可以移动到左子或右子。
这是怎么回事，我们先前写在长期的二进制搜索代码看起来非常相似。
当我们开始时，我们知道，我们要坚持到当前节点
，我们正在寻找与当前节点将被初始化到根节点。
而现在，我们要继续通过树，
记住，我们的终止条件 -
当我们真正完成手头的例子 -
当我们遇到一个空节点，
当我们看着一个空的孩子，
而当我们实际移动中的一个节点树
并发现，我们正处在一个空节点。
我们要迭代，直到电流不等于空。
那我们该怎么办？
如果我们要测试（电流 - >值==值），
那么我们就知道我们实际上已经发现的节点，我们正在寻找。
所以在这里，我们可以返回true。
否则，我们希望看到与否的值小于该值。
如果当前节点的值是小于该值，我们正在寻找，
我们要移动到右边。
因此，电流=电流 - > right_child;否则，我们将要移动到左边。
电流=电流 - > left_child;。很简单。
>> 您可能认识的循环，看起来非常相似，这从
二进制搜索在长期，但那时我们正在处理的低，中，高。
在这里，我们只需要看看在当前值，
所以这是不错的，简单的。
让我们确保代码工作。
首先，请确保它编译。看起来喜欢它。
让我们尝试运行它。
而事实上，它打印出的一切，我们预计。
它发现树中，没有找到10，因为10是不是在树中，
并没有发现要么是因为1是不是在树中。
很酷的东西。
>> 好吧。让我们回到我们的规范，看看接下来会发生什么。
现在，要添加一些节点到树中。
要加5，2，8，并确保我们的包含的代码
仍如预期般运作。
让我们做到这一点。
在这一点上，而不是再这样做恼人的复制和粘贴，
让我们写一个函数创建一个节点。
如果我们向下滚动的方式为主，我们看到，我们一直在做这
一遍又一遍，每次，我们要创建一个节点非常相似的代码。
>> 让我们写一个函数，将实际为我们建立一个节点，并将其返回。
我要把它称为build_node。
我要建立一个节点，一个特定的值。
在这里放大。
我首先要做的是创造空间的节点上堆的。
因此，节点* N =的malloc（sizeof（节点）的）; N - >值=值;
那么在这里，我只是要初始化所有字段是适当的值。
在最后，我们将回到我们的节点。
好吧。有一点要注意的是，这个函数就在这里
会返回一个指针一直堆分配的内存。
有什么好有关的是，这个节点 -
我们要声明，因为如果我们宣布它在栈上的堆
我们将无法在这个函数中这样做。
该内存走出去的范围
将是无效的，如果我们试图稍后访问。
自从我们宣布堆中分配的内存，
我们要照顾释放后
我们的程序没有任何内存泄漏。
我们一直在踢，一切在代码中
只是为了简单起见，在时间，
但如果你写一个函数，看起来像这样
，你就有了 - 有人称之为一个malloc或realloc内 -
你想知道，你提出某种意见在这里说，
嘿，你知道，返回与传入的值初始化堆分配的节点。
然后你要确保你把某种提示说
调用者必须释放返回的内存。
这样一来，如果有人会去，并使用该功能，
他们知道，无论他们获得从该函数
在某些时候需要被释放。
>> 假设在这里一切都很好，好，
我们可以去到我们的代码，并更换所有这些线路在这里
我们构建节点功能的调用。
让我们做的真的很快。
在这里的一个部分，我们不是要取代的是这部分
在底部，我们实际上连接起来的节点指向对方，
因为我们不能做我们的功能。
但是，让我们做根* 3 = build_node（7）;节点= build_node（3）;
节点* 6 = build_node（6）;节点* 9 = build_node（9）;。
而现在，我们也想添加节点 -
节点* 5 = build_node（5）;节点* 8 = build_node（8）;
什么是其他节点？让我们来看看这里。我们也想添加2 -
节点* 2 = build_node（2）;
好吧。在这一点上，我们知道，我们已经得到了，3，9，7和6
所有的有线，适当的，但5日，8日和2？
为了保持一切以适当的顺序，
我们知道，3的右孩子是6。
所以，如果我们要添加5，
5还属于树的右侧，其中3是根
等5属于左子6。
为此，我们可以说，6 - > left_child = 5;
然后在8属于左子9，9 - > left_child = 8;
，然后是左子3，所以我们可以做的，在这里 - 你 - > left_child = 2;
如果你没有相当跟着，我建议你画出来自己。
>> 好吧。让我们拯救。让我们走出去，以确保编译，
然后我们就可以加入我们的CONTAINS调用。
看起来一切都还编制。
让我们去，并添加一些包含调用。
再次，我会做一点点的复制和粘贴。
现在，让我们来搜索5，8，和2。好吧。
让我们相信，这一切看起来还不错。太好了！保存并退出。
现在，让我们编译，现在让我们来运行。
从结果来看，它看起来一切都刚刚好工作和好。
太好了！所以，现在我们已经得到了我们的包含函数写的。
让我们继续前进，并开始工作如何插入到树中的节点
因为，我们现在做的是正确的，事情是不是很漂亮。
>> 如果我们回去的规范，
它要求我们称为“插入” - “再编写一个函数，返回一个布尔值，
我们是否可以插入到树节点 -
然后插入到树中的值被指定为
我们的插入函数的唯一参数。
我们将返回true，如果我们确实可以插入到树的节点上，
这意味着我们，一，有足够的内存，
然后两个，则该节点没有已经存在的树，因为 -
请记住，我们不会在树中有重复的值，只是为了让事情简单。
好吧。回到代码。
打开它。放大一点，然后向下滚动。
让我们把正上方的contains插入功能。
再次，它被称为布尔插入（int值）。
给它多一点空间，然后，在默认情况下，
让我们在最后返回false。
现在已经降到底部，让我们继续前进，而不是手动构建的节点
在主自己，并把它们连接指向对方，就像我们正在做的，
要做到这一点，我们将依靠我们的插入功能。
我们将不依赖于我们的插入功能来构建整个树从头开始，只是还没有，
而是我们将摆脱这些线路 - 我们就会注释掉这些行 -
建立结点5，8，和2。
而我们将插入调用我们的插入功能
以确保实际工作。
在这里，我们走了。
>> 现在，我们已经发表了这些行。
我们只有7，3，9，和6在我们的树在这一点上。
要知道，这是所有工作，
我们可以放大，使我们的二进制树，
运行它，我们可以看到，包含现在告诉我们，我们是完全正确的 -
5，8，和图2是不再在树中。
返回到代码中，
以及我们如何去插入呢？
记住，我们做了什么时，我们实际上是插入5个，8和2以前。
我们打​​了Plinko游戏，我们开始从根本上，
逐一走下树1
直到我们找到了合适的间隙，
然后我们有线该节点中，在适当的位置。
我们将做同样的事情。
这基本上是喜欢写代码，我们使用包含功能
找到节点应该的地方，
然后我们要插入的节点就在那里。
让我们开始这样做。
>> 因此，我们有一个节点*电流=根源;我们只是按照包含的代码
直到我们发现，它并没有完全为我们工作。
我们要通过树而目前的元素不为空，
如果我们发现，当前的价值等于价值，我们正试图插入 -
好了，这是一个在何种情况下，我们不能真正地接入节点
树，因为这意味着我们有一个重复的值。
在这里，我们将返回false。
现在，否则，如果电流的值是小于值，
现在我们知道，我们向右移动，
因为该值属于在右半当前树。
否则，我们将要移动到左侧。
这基本上是我们的包含函数在那里。
>> 在这一点上，我们已经完成了这个while循环，
我们当前的指针指向空
如果功能尚未恢复。
因此，我们当前在那个地方，我们要插入新的节点。
仍有许多工作要做的，是建立新的节点，
我们可以做很容易。
我们可以用我们的超级方便的构建节点功能，
的东西，我们并没有做早期 -
我们只是一种想当然的，但现在我们要做的只是为了确保 -
我们将进行测试，以确保新的节点返回的值实际上是
不为null，因为我们不希望开始访问的内存，如果它是空的。
我们可以测试，以确保新的节点是不等于空。
或相反，我们可以看到它实际上是空，
，如果它是空的，那么我们就可以返回false早。
>> 在这一点上，我们来连接新节点到其适当的位置在树中。
如果我们回头看主，我们实际上是价值布线之前，
我们可以看到，我们用什么方法做这件事的时候，我们希望把树中的
我们访问的左子根。
当我们把在树中，我们不得不访问右子树的根。
我们必须有一个指针，指向父，为了把树的一个新值。
滚动到插入，不会完全工作在这里
因为我们没有父指针。
我们希望能够做到的，在这一点上，是
检查父级的值 - 哦，天哪，
如果父级的值是小于当前值，
然后，父母的权利，孩子应该是新的节点;
否则，父的左孩子应该是新的节点。
但是，我们没有这个父指针相当，但。
>> 为了得到它，我们实际上是要跟踪它，因为我们去通过树
在我们上面的循环，并找到适当的位置。
我们可以做到这一点的滚动备份到我们的顶部插入功能
跟踪另一个指针变量称为父。
我们将它设置为null最初，
然后我们每次去通过树，
我们要设置父指针，以匹配当前的指针。
设置等于当前父。
这样一来，每次我们去通过，
我们要确保当前指针会递增
父指针如下 - 只有一个级别高于当前指针在树中。
这一切都看起来很不错。
>> 我认为，我们将要调整的一件事，这是构建节点则返回null。
为了构建节点，居然成功地返回null，
我们就必须修改的代码，
因为在这里，我们从来没有进行测试，以确保的malloc返回一个有效的指针。
所以，如果（N = NULL），然后 -
如果malloc返回一个有效的指针，那么我们就对它进行初始化;
否则，我们就返回，这将最终为我们返回null。
现在，一切看起来还不错。让我们相信，这实际上编译。
使二进制树，哦，我们有一些东西在这里。
>> 我们已经有了一个隐式声明的函数构建节点。
同样，使用这些编译器，我们要开始的顶部。
什么是必须的意思是，我给你打电话，构建节点之前，我已经宣布它。
让我们回去的代码真的很快。
向下滚动，果然，我的插入函数被声明
上面构建节点的功能，
但我试图用建立内部节点插入。
我要去和复制 - 然后将其粘贴在顶部构建节点的作用方式。
通过这种方式，希望这将工作。让我们给另一个去。
现在，这一切编译。一切都很好。
>> 但在这一点上，我们实际上没有叫我们插入功能。
我们只知道它编译，所以让我们进去，把一些调用中。
让我们这样做，在我们的主函数。
在这里，我们注释掉5，8，2，
然后我们并没有将它们连接起来这里。
让我们打几个电话插入，
让我们也使用同一种东西，我们使用
当我们做这些printf调用，以确保一切都没有得到正确插入。
我要复制和粘贴，
而不是包含我们要做的插入。
，而不是6，10，1，我们要使用5，8，和2。
这应能插入5，8，2到树中。
编译。一切都很好。现在我们来运行我们的程序。
>> 一切都返回false。
因此，5，8，和2没有去，和它看起来像CONTAINS没有找到他们。
这是怎么回事呢？让我们缩小。
第一个问题是，插入似乎返回false，
它看起来像，这是因为我们留在我们返回false，调用，
我们从来没有真正返回true。
我们可以设置了。
第二个问题是，现在即使我们这样做 - 保存这个，不干这个，
再次运行make，编译，然后运行它 -
我们看到的东西都在这里发生。
5，8，2例在树中仍然没有找到。
所以，这是怎么回事呢？
>> 让我们来看看在代码中。
让我们看看我们是否能够明白这一点。
我们开始与父不空。
我们设定的电流等于根指针的指针，
我们要工​​作的方式，通过树。
如果当前节点不为空，那么我们就知道，我们可以向下移动一点点。
我们的父母是平等的当前指针指针，
检查的价值 - 如果值是相同的，我们返回false。
如果值是我们移动到右边;
否则，我们移动到左侧。
然后，我们建立了一个节点。我会在一点点放大。
在这里，我们要尝试连接起来的值是相同的。
这是怎么回事呢？让我们来看看，如果可能Valgrind可以给我们一个暗示。
>> 我喜欢用Valgrind的只是因为Valgrind的真的很快运行
告诉你，如果有任何的内存错误。
当我们的代码运行Valgrind的，
你可以看到右here--Valgrind./binary_tree--and回车。
你看，我们没有任何记忆错误，所以看起来一切都还好至今。
我们的确有一些内存泄漏，我们知道，因为我们不
发生在释放我们的节点。
让我们尝试运行GDB来看看到底发生了。
我们会尽GDB / binary_tree。它启动起来就好了。
让我们设置插入一个破发点。
让我们来运行。
看起来我们从来没有真正被称为插入。
它看起来只是，当我改变了这里的主要问题是 -
所有这些printf调用包含 -
我从来没有真正改变了这些调用插入。
现在，让我们给它一个尝试。让我们编译。
一切看起来很好。现在，让我们尝试运行它，看看会发生什么。
好吧！一切看起来有相当不错的。
>> 最后一点要考虑的是，是否有任何边缘的情况下，这个插入？
而事实证明，好了，一个边缘的情况下，始终是有趣的思考
是，会发生什么情况，如果你的树是空的，你调用这个插入的功能吗？
会奏效吗？好了，让我们给它一个尝试。
- binary_tree C -
我们要测试的是，我们要深入到我们的主函数，
，而不是这样的连接这些节点，
我们只是要注释掉整个事情，
，而不是节点自己的布线了，
实际上，我们可以继续删除所有这一切。
我们将调用插入，使一切。
所以，让我们做的 - 而不是5，8和2，我们要插入7，3，和9。
然后，我们将要插入6。
保存。退出。二叉树。
这一切都进行编译。
我们可以直接运行它，看看会发生什么，
但它也将是非常重要的，以确保
我们没有任何的内存错误，
因为这是我们的优势情况下，我们知道。
>> 首先我们要确定它的工作原理以及在Valgrind下，
我们要做的只是运行Valgrind的/ binary_tree。
它看起来就像从一个背景下，我们确实有一个错误 -
我们有这样的分割故障。
发生什么事了吗？
Valgrind的实际上告诉了我们它在哪里。
缩小一点点。
它看起来就像是发生在我们的插入功能，
我们有一个在插入无效的读取大小为4，第60行。
让我们回去看看是怎么回事。
缩小非常快的。
我想，以确保它不会去在屏幕的边缘，所以我们所看到的一切。
拉一点点。好吧。
向下滚动，问题就在这里。
会发生什么事，如果我们得到了我们当前节点已经是空的，
我们的父节点是空的，所以如果我们在最高层，就在这里看 -
如果从来没有真正执行这个while循环
因为我们目前的值是空的 - 我们的根是空的，所以当前是空的 -
然后我们的父母从来没有被设置为当前一个有效的值，
因此，家长也将是空的。
我们需要记住检查
的时候，我们在这里，我们开始访问父级的值。
因此，会发生什么呢？那么，如果母公司是空的 -
（“母公司”== NULL） - 那么，我们知道，
绝不能在树中的任何东西。
我们必须试图将它的根。
我们能做到这一点，只需通过设置到新的节点等于根。
在这一点上，我们实际上并不想通过这些其他的东西。
相反，在这里，我们可以做一个else if-else的，
或者我们可以将所有在这里的其他，
但在这里我们就用别人这样做的。
现在，我们要进行测试，以确保我们的父母不为空
在此之前实际上是试图访问其字段。
这将有助于我们避免分割故障。
所以，我们就退出了，放大，编译，运行。
>> 没有错误，但我们仍然有一堆的内存泄漏
因为我们没有释放任何对我们的节点。
但是，如果我们去了，我们期待在我们的打印输出，
我们看到，嗯，看起来像我们所有的插入返回true，这是很好的。
刀片都是真实的，
再恰当不过了载有来电也是如此。
>> 干得好！看起来我们已经成功地写入插入。
这是我们这个星期的习题集规范。
一个有趣的挑战，要考虑的是你将如何去
免费在这棵树的所有节点。
我们可以这样做了一些不同的方法，
但我会离开，给你做实验，
一个有趣的挑战，尝试，并确保您可以确保
Valgrind的报告，这不返回任何错误和无泄漏。
>> 好运气在这一周的Huffman编码问题集
我们会下周见！
[CS50.TV]