[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]