[Powered by Google Translate] [第7条:更舒适] 罗布·鲍登] [哈佛大学] [这是CS50] [CS50.TV] 好的。所以,像我在我的电子邮件中说, 这将是一个二进制树密集的部分。 但也有很多问题。 因此,我们将尝试并绘制出每一个问题 进入痛苦的细节做的事情的最好方法。 所以,在开始的时候,我们去通过二进制树之类的东西的样品图纸。 所以在这里,“请记住,一个二进制树有类似的链表节点, 除,而不是一个指针有两种:一种为在左边的'孩子' 和一个正确的'孩子'。“ 因此,一个二进制树就像是一个链表, 除了结构有两个指针。 三元树,这将有个三分球, 有N-叉树,其中有一个通用的指针 就是你必须对malloc足够大,有 足够的指点所有可能的孩子。 因此,二叉树正好有两个固定数量的。 如果你愿意,你可以给一个链接列表为一元树, 但我不认为任何人都需要它,。 “画一个方框和箭头图的二进制树节点 Nate的最喜欢的数字,7,每个孩子指针为空。“ 因此,iPad模式。 这将是非常简单的。 我们只是有一个节点,我会画一个矩形。 我会在这里得出的值。 因此,该值将在这里, ,然后在这里我们将不得不在右边的左指针在左,右指针。 这是非常多,所以约定来调用它左,右,指针名。 这些都将是空。 这将是空的,这只会是空的。 好吧。因此,回到这里。 “一个链表,我们只需要存储一个指针 在列表中的第一个节点是为了记住整个链表,或整个列表。 同样,树木,我们只需要存储一个指针 为了记住整个树到单个节点。 这是卡莱节点树的“根”。 从之前建立在你的图,或画一个新的 这样,你有一个盒子和箭头描绘的二叉树 与7的值,然后3在左, 然后9在右边,然后6在右侧的3。“ 让我们来看看,如果我能记得所有这一切在我的脑海。 因此,这将是我们的根在这里。 的地方,我们还会有一些指针的东西,我们会打电话给根, 它指向了这个家伙。 现在一个新的节点, 我们有什么,在左边吗? 因此,一个新的节点3,并它最初指向空。 我就把N. 现在,我们希望去左边的7。 因此,我们改变这个指针指向这个家伙。 我们这样做。我们希望有一个在这里 它最初只是说空。 我们要改变这个指针,指向9, 现在我们要放6到右边的3。 因此,它要 - 6。 那小子将指向。 好吧。所以,这一切都要求我们做的。 现在,让我们多一些术语。 我们已经讨论了如何树的根是最顶端的树中的节点。 一个包含7。在树的底部的节点被称为叶子。 任何节点作为其子空是叶。 因此,它是可能的,如果我们的二进制树只是一个单一的节点, 一棵树是一片叶子,就是这样。 “”高度“的树是你必须做的跳数 得到从顶端到叶子。“ 我们将进入,在第二,不同的 之间的平衡和非平衡二叉树, 但现在,这种树的整体高度 我想说的是3,但如果你的跳数计数 你必须为了得到9,那么它真的只是一个身高2。 现在这是一个不平衡的二叉树, 但我们会谈论平衡时,它得到相关的。 所以,现在我们可以谈论一棵树的节点在条款 相对于树中的其他节点。 所以,现在我们有父母,子女,兄弟姐妹,祖先和子孙。 他们是相当普遍的意义上说,他们的意思。 如果我们问 - 它的父母。 那么,什么是3的父? [学生] 7。 >>呀。家长只是要分给你。 那么什么是儿童的7? [学生] 3和9。 >>呀。 请注意,“孩子们”的字面意思是儿童, 所以将不适用,因为它就像一个孙子。 不过,如果我们去的后裔,所以是什么7的后裔? [学生] 3,第6和第9。 >>呀。 根节点的后代将是树中的一切, 可能除了根节点,如果你不想认为的后裔。 最后,祖先,所以它是相反的方向。 那么,什么是6的祖先吗? [学生] 3和7。 >>呀。 9不包括在内。 这仅仅是直接的后裔回到根 将是你的祖先。 “我们说,一个二叉树是”责令“如果在树中的每个节点, 其后代在左侧有小的值 和在右边的所有的那些有较大的值。 例如,上面的树是有序的,但它不是唯一可能的有序安排。“ 在我们到达, 有序二元树也被称为二叉查找树。 在这里,我们要求有序二元树, 但我从来没有听到它被称为有序二元树前, 一个测验,我们更倾向于把二叉搜索树。 它们是同一个, 重要的是你认识二叉树和二叉搜索树的区别。 二叉树只是一棵树,两件事情。 每个结点两件事情。 有没有推理,它指向的值。 所以想在这里,因为它是一个二叉搜索树, 我们知道,如果我们向左走7, 然后,我们能接触到的所有的值 将剩下的7必须是小于7。 请注意,所有的值小于7的第3和第6。 这些都是7左侧。 如果我们去7的权利,一切都必须大于7, 因此9 7是正确的,所以我们是很好的。 这是一个不为一个二进制树的情况下, 一个正规的二进制树中,我们就可以有3个在顶部,7的左侧, 9至7的左侧; theres没有的值的任何顺序。 现在,我们将不能真正做到这一点,因为它的繁琐和不必要的, 但“试图吸引尽可能多的有序树,你能想到的 使用的数字7,3,9和6。 有多少个不同的安排?的高度,每一个是什么?“ 我们会做一对夫妇,但其主要思想是, 这是在没有办法包含这些值的二进制树的一个唯一的表示。 我们需要的是一些二进制树,它含有7,3,6,和9。 另一个可能的有效的将3根, 去的左侧和它的6,去左边,它是7, 去的左侧和它的9。 这是一个非常有效的二叉搜索树。 这是不是非常有帮助,因为它就像一个链表 所有这些指针是空的。 但是,它是一个有效的树。是吗? [学生]值必须在正确的吗? 或者是这样的 - ? >>我的意思是这些走另一条路。 还有 - 是的,让我们切换,。 9,7,6,3。良好的渔获物。 它仍然有,服从什么是二进制树搜索是应该做的。 所以一切向左侧是小于任何给定的节点。 我们可以只动,说,这6,把它放在这里。 不,我们不能。我为什么这样做呢? 让我们做 - 这里是6,7,6点到3点。 这仍然是一个有效的二叉搜索树。 什么是错的,如果我 - 让我们来看看,如果我能想出​​的安排。 是啊,好吧。那么,什么是错的这棵树吗? 我想我已经给你一个暗示,有什么不对的地方。 我为什么这样做呢? 好吧。这看起来很合理的。 如果我们看一下在每个节点上,如7,然后到左边的7 3。 因此,我们有3个,3的权利的东西是一个6。 如果你看的东西的权利6 6,9。 那么,为什么这不是一个有效的二叉搜索树吗? [学生] 9仍是7左侧。 >>呀。 它必须是真实的,所有你所能达到的左7的值都小于7。 如果我们向左走7,我们得到的,我们仍然可以到6, 我们仍然可以得到为9,但通过在经历小于7, 我们不应该能够得到一个数字,大于7。 因此,这是不是一个有效的二叉搜索树。 我哥哥其实是有一个面试问题, 这基本上是一些东西来验证这一点,只是代码 一棵树是一个二叉搜索树, 所以他做的第一件事是检查,看看 如果左边和右边是正确的,然后循环。 但你不能做到这一点,你必须跟踪 的事实,现在,我已经走了剩下的7, 在这个子树中的一切必须小于7。 正确的算法需要跟踪 的值的范围可能里钻 通过所有这些,我们不会去。 有一个很好的递推关系, 虽然我们没有得到这些,我们不会让那些, 确定有多少实际上是。 因此,有14人。 的想法,你会怎么做数学是一样的, 你可以选择任何一个节点是根, 然后如果我选择7根节点, 再有,说一些数字,可以去我的左节点, 有一些数字,可以成为我的右节点, 但如果我有n个总人数,然后可以去左边的金额 加量,可以去右边的是N - 1。 因此,剩余的数字,它们可以去的左侧或右侧。 这似乎很难,如果我把第一,然后一切都去左边, 但如果我把7,有些事情是可以走左边,有些事情可以去正确的。 '3第一,我的意思是什么都可以去正确的。 这是真的,你就必须把它作为, 有多少东西可以去上了一个层次的树。 出来是14,或您可以绘制所有的这些, 然后你会得到14。 让我们再回到这里, 非常酷,因为我们可以通过搜索“有序二叉树 在一个非常类似的方式来寻找在一个排序的数组。 要做到这一点,我们从根开始和工作的方式,在树 向叶,检查每个节点的值与我们正在寻找的值。 如果当前节点的值是小于该值,我们正在寻找, 你去下一个节点的右孩子。 否则,你去结点的左孩子。 在某些时候,你会发现你正在寻找的价值,你会碰到一个空, 的价值不是在树上。“ 我要重绘我们面前的树,要花几秒钟。 但是,我们想看看是否6,10,和1是在树中。 因此,它是什么,7,9,3,6。好吧。 你想看看这些数字,我们要查找6。 这种算法是如何工作的? 好了,我们也有一些到树的根指针。 我们会去根说,这是价值相等的价值,我们正在寻找吗? 因此,我们正在寻找6,所以它是不相等的。 因此,我们继续前进,现在我们说,好了,所以6是小于7。 这是否意味着我们想要去的左侧,我们要向右走? [学生]。 >>呀。 这是明显更容易,所有你必须​​做的就是画一个可能的树节点 然后你不知道不知道 - 而不是试图想在你的头上, 没关系,如果它的不足,我去左边或走右边, 只是在看这幅画,这是非常清楚的,我必须去左边 如果此节点是大于我在寻找的值。 所以,你去左边,现在我在3。 我想 - 3是不到我在寻找的价值,这是6。 所以,我们去正确的,现在我结束了在6, 这是我要找的,所以我返回真值。 我要寻找的下一个值是10。 好吧。所以,现在,10 - 切断 - 要遵循的根本。 如今,10个是要大于7,所以我想看看的权利。 10我要到这里来,是要大于9, 所以我想看看的权利。 我来这里,但在这里,现在我在空。 我该怎么做,如果我打空? [学生]:返回假的? >>呀。我没有找到10。 1将是几乎相同的情况下, 除了它只是要翻转,而不是寻找 右侧向下,我要看看左侧。 现在,我认为我们真正的代码。 这里的地方 - 打开CS50设备和导航用自己的方式, 但你也可以做到这一点的空间。 做到这一点的空间,这也可能是理想的, 因为我们可以工作的空间。 他说:“首先,我们需要一个新的类型定义一个包含int值的二进制树节点。 使用的typedef以下的样板, 创建一个新的类型定义为一个二进制树中的节点。 如果你被卡住。 。 。 “等等,等等,等等。好。 因此,让我们把这里的样板, typedef结构节点和节点。是啊,好吧。 那么,什么样的领域,我们将要在我们的节点吗? [学生]:int,然后两个指针吗? >> int值,两个指针吗?我怎样写指针吗? [学生]结构。 >>我要放大是啊,所以结构节点离开, 和结构节点*。 请记住最后一次讨论, 这是没有意义的,这是没有意义的, 这是没有意义的。 你需要的一切,以便确定这种递归结构。 好了,所以这就是我们的树是怎么回事的样子。 如果我们做了一个三叉树,然后一个节点可能看起来像B1,B2,结构节点* B3, 其中b是一个分支 - 其实,我更听到它的左,中,右,但不管。 我们关心的只是二进制,右,左。 “现在,声明一个全局变量为根的树节点*。” 因此,我们不打算这样做。 为了使事情变得稍微更困难,更广义的, 我们不会有一个全球性的节点变量。 相反,在主,我们将宣布我们的所有节点的事情, 这意味着,在下面,当我们开始运行 包含函数和我们的插入功能, 而不是我们的CONTAINS函数只是使用这一全球性的节点变量, 我们将它作为参数树,我们希望它来处理。 有全局变量应该使事情变得更容易。 我们将让事情变得更糟糕。 现在只需要一分钟左右的时间做这样的事情, 内的主要你要创建这个树,这就是所有你想做的事。 尝试和构造这棵树在您的主要功能。 好吧。所以,你甚至不必构建了树的整个方式。 但是,任何人有什么我可以拉起来 如何开始构建这样的树吗? [学生]:有人撞,试图摆脱。 鲍登]的任何舒适与自己的树建设? [学生]:当然可以。它没有这样做。 >>这是正常的。我们就可以完成 - 哦,你可以将它保存吗?万岁。 所以,在这里,我们有 - 哦,我有点切断。 我放大? 缩放,滚动。 >>我有一个问题。 >>呀? [学生]:当你定义结构,是类的东西初始化到什么? [鲍登号>>好。所以,你必须初始化 - [鲍登号当你定义,或当你声明一个结构, 未初始化默认情况下,它就像如果你声明一个int。 这是完全一样的东西。这就像其各自的领域 可以有一个垃圾的价值所在。 “和它可能的定义 - 定义了一个struct 在一种方式,它初始化它们? 波顿:是的。所以,快捷的初始化语法 是怎么回事的样子 - 有两种方法,我们可以做到这一点。我认为,我们应该编译它 以确保锵也这样做了。 参数顺序的结构, 你把这些花括号内的参数的顺序。 所以,如果你想要初始化它9空,然后右边是空的, 这将是9,NULL,NULL。 另一种方法是,编辑器不喜欢这种语法, 认为我想要一个新的块, 但选择是一样的东西 - 这里,我把它放在一个新行。 你可以明确地说,我忘了确切的语法。 所以,你可以明确地解决他们的名字,并说, c或。值= 9,左= NULL。 我猜这些需要逗号。 右= NULL,所以这样一来,你不这样做 确实需要知道的结构顺序, 当你读这篇文章,它更明确 什么价值被初始化。 这种情况发生的事情,是一个 - 因此,在大多数情况下,C + +是一个C的超集 你可以把C代码,将其移动到C + +,和它应该编译。 这是一个C + +不支持的事情,这样的人往往不这样做。 我不知道如果这是唯一的原因,人们往往不这样做, 但需要的情况下,我需要使用C + +,所以我不能使用此工作。 另一个例子的东西,不与C + +是 如何malloc返回一个“无效*,”从技术上说, 但你可以说的char * x = malloc的什么, 它会自动转换为char *。 该自动转换不会发生在C + +。 这将无法编译,你会明确地说 是char *,malloc的,不管结果如何,将它转换为一个char *。 不会有太多的事情,C和C + +不同意, 但这些都是两个。 因此,我们将用这个语法。 但是,即使我们没有去与语法, 是什么 - 可能是错的吗? [学生]:我不需要取消对它的引用? >>呀。 请记住,箭头有一个隐含的间接引用, 所以当我们只是处理与结构, 我们要使用的。在一个领域内的结构。 我们想要做的唯一的一次是,当我们使用箭头 - ,箭头相当于 - 这将意味着什么,如果我用箭头。 所有的箭头表示,取消引用此,现在我在一个结构,我可以得到该领域。 要么领域直接或间接引用,并获得字段 - 我想这应该是价值。 但是,我在这里只是一个结构,而不是一个结构的指针来处理, 所以我不能使用的箭头。 但是,这样的事情我们可以做的所有节点上。 哦,我的上帝。 这是6,7,和3。 然后我们就可以在我们的树,设立了分公司,我们可以有7个 - 我们可以有,其左应指向3。 那么,如何才能做到这一点呢? [学生,不知所云] >>呀。节点3的地址, ,如果你没有地址,那么就无法编译。 但要记住,这些都是到下一个节点的指针。 正确的应该点到9, 3至6点。 我认为这是所有设置。有任何意见或问题? [学生,不知所云]根正在为7。 我们只能说节点* = 或根,=&node7的。 对于我们的目的,我们将要处理的插入, 所以,我们将要编写一个函数插入到这个二叉树 并插入不可避免地会调用malloc来创建一个新的节点,这棵树。 因此,事情会变得混乱的事实,有些节点 当前堆栈上 与其他节点要结束的堆,当我们插入。 这是完全有效的,但唯一的原因 我们能够做到这一点的堆栈 是因为它是一个人为的例子,我们知道 树应该被构造为7,3,6,9。 如果我们不具备这一点,那么我们就没有对malloc摆在首位。 正如我们将看到的晚了一点,我们应该malloc'ing。 现在它是完全合理的,放在堆栈中, 但让我们改变一个malloc实现。 因此,这些现在是这样的 的节点* node9 = malloc的(如sizeof(节点))。 现在,我们将不得不做我们的检查。 (node9 == NULL) - 我不想 - 返回1,那么我们就可以做node9因为现在它是一个指针, 值= 6,node9的左= NULL, node9 - > = NULL, 我们将要做到这一点,每个节点。 所以,让我们把它里面的一个单独的函数。 让我们叫该节点* build_node, 这是有点类似的API,我们提供的霍夫曼编码。 我们为您提供的初始化函数的树 拆解为这些树木和森林相同的“功能”。 所以,在这里我们将有一个初始化函数 只是为我们建立一个节点。 它看起来几乎完全一样这是怎么回事。 我我什至会偷懒,不改变的变量名, 即使node9没有任何意义了。 哦,,我想node9的价值不应该被6。 现在我们可以回到node9。 在这里,我们应该返回null。 每个人都同意,构建一个节点的功能吗? 所以,现在我们可以直接调用的任何节点,建立与给定值和空指针。 现在,我们可以调用,我们可以做节点* node9 = build_node(9)。 让我们做。 。 。 6,3,7,6,3,7。 现在我们要设置相同的指针, 但现在一切都已经在指针 因此不再需要的地址。 好吧。那么,什么是我想要做的最后一件事吗? 有一个错误检查,我不这样做。 什么构建节点回报吗? [学生,不知所云] >>呀。如果malloc失败,它会返回null。 所以,我要在这里懒洋洋地把它放下,而不是做各自的条件。 如果(node9 == NULL,或者 - 甚至更简单, 这相当于只是如果不node9。 因此,如果不node9,或不node6,或没有节点3,或不node7,返回1。 也许我们应该打印的malloc失败,或某事。 [学生]:是虚假等于NULL作为吗? 鲍登任何零值是假的。 因此,null是一个零值。 零是零值。 False是一个零值。 任何 - 几乎只有2个零值是空的,零, 假的就是哈希值被定义为“0”。 这也适用于我们声明了全局变量。 如果我们确实有节点*的根在这里, - 有关全局变量是很好的事情,他们总是有一个初始值。 这是不正确的功能,在这里, 如果我们有,像,节点*节点x。 我们不知道x.value,x.whatever, 或者我们也可以打印出来,他们可以是任意的。 这是不正确的全局变量。 所以的节点根或节点x。 默认情况下,这是全球的一切,如果没有显式初始化为某个值, 具有零值作为其值。 节点*根,所以在这里,我们没有显式初始化它的任何事情, 所以它的默认值将是空的,这是零值的指针。 默认的x的值将表示x.value为零, x.left为空,是空x.right。 所以,因为它是一个结构,该结构中的所有领域的零值。 我们并不需要使用,在这里,虽然。 [学生]比其他变量的结构是不同的,和其它变量 垃圾值,这些都是零? [鲍登其他值。因此,在x,x将是零。 如果它在全球范围内,它有一个初始值。 “好了。 鲍登无论是初始值你给或零。 我认为所有这一切负责。 好吧。所以接下来的部分是问, “现在,我们要编写一个函数调用包含 布尔的原型包含的int值。“ 我们不打算做布尔包含的int值。 我们的原型看起来像 包含布尔(int值。 然后,我们也将传递给它的树 它应该被检查,看它是否具有该值。 因此,节点树)。好吧。 然后,我们可以把它喜欢的东西, 也许我们会想printf或什么的。 包含6,我们的根。 这应该返回一个或真, 而包含5根应该返回false。 因此,需要实现这一点。 你可以做到这一点的迭代或递归。 的方式,我们已经设置的东西是美好的事情, 它本身的递归解决方案更容易 比全局变量的方式。 因为如果我们只是有包含的int值,那么我们就没有办法搜索子树。 我们就必须有一个单独的辅助函数,递归我们的子树。 但因为我们已经改变了它的树作为参数, 它应该一直摆在首位, 现在我们可以递归更容易。 因此,迭代或递归的,我们就去了两种, 但我们会看到,递归端起来是很容易的。 好吧。有没有人有什么我们可以使用吗? [学生]:我有一个迭代的解决方案。 >>所有权利,迭代。 好吧,这看起来不错。 所以,想通过它我们走? [学生]:当然可以。所以我设置一个临时变量来获得的第一个节点树。 然后我就通过,而温度不等于空循环, 因此,虽然仍然在树中,我猜。 并且如果该值是相等的值,temp被指向 然后它返回该值。 否则,它会检查,如果是上的右侧或左侧。 如果你有机会的情况下,有没有更多的树, 那么它的回报 - 退出循环,返回false。 鲍登]好吧。因此,这似乎不错。 在任何问题上有任何人有任何意见? 我没有在所有的正确意见。 有一件事我们可以做的就是这个家伙。 哦,这是要去一个小稍长。 我会解决这个问题了。好吧。 每个人都应该还记得三元工作。 有肯定是测验在过去 给你一个三元运算符的功能, 说,翻译,做一些不使用三元。 所以这是一个很常见的情况时,我会觉得使用三元, 其中,如果某些条件设置一个变量的东西, 其他设置相同的变量别的东西。 这件事情,这样的事情很经常可以转化为 在那里设置该变量 - 或者说,好了,这是真的吗?然后,否则这一点。 [学生]:第一个是,如果真实的,对不对? 鲍登]是啊。我总是看它的方式是,温度大于等于温度值, 然后,否则这一点。问一个问题。 它更大的吗?然后做的第一件事。否则做的第二件事情。 我几乎总是 - 结肠,我只是 - 我的头,我读别的。 有没有人有一个递归的解决方案吗? 好吧。这一次,我们要 - 它可能已经是巨大的, 但我们要使其更好。 这几乎是完全相同的想法。 好,只是,你想解释一下吗? [学生]:当然可以。因此,我们确定该树不为空,第一, 因为如果树是空的,那么它会返回false,因为我们还没有找到它。 如果还是有一棵树,我们进入 - 我们首先检查该值是当前节点。 如果是,则返回true,如果没有,我们递归向左或向右。 这听起来是适当的吗? >>嗯,嗯。 (协议) 所以注意到这几乎是 - 结构非常相似,迭代求解。 只是,而不是递归的,我们有一个while循环。 而基地的情况下,这里的树不等于空 的条件下,我们爆发出的while循环。 他们是非常相似的。但是,我们要进一步采取这一步。 现在,我们做同样的事情在这里。 请注意,我们正在返回同样的事情在这些线路, 除了一个参数是不同的。 因此,我们要到一个三元。 我打选项的东西,它的象征。好吧。 因此,我们将返回包含。 这是多行,好,放大它。 通常情况下,作为一个文体的事情,我不认为很多人 加一个空格后的箭头,但我想,如果你是一致的,它的罚款。 如果值是小于树的价值,我们希望在树上左递归的, 否则,我们要递归树权。 所以这是第一个步骤,使这个看起来小一些。 这个看起来小一些的第二步 - 我们可以将多行。 好吧。使它看起来更小的第二步是在这里, 返回值等于树的值,或包含什么。 这是一个重要的事情。 我不知道,如果他在课堂上说,它明确, 但它被称为短路的评价。 这里的想法是价值==树价值。 如果这是真的,那么这是真实的,我们要'或',无论是在这里。 因此,无论是在这里,甚至没有考虑, 整个表达式将返回是什么? [学生]:真? >>是的,因为真实的东西, 用OR - 或真或运算与任何必然是真实的。 因此,只要我们看到的返回值= tree值, 我们只是返回true。 甚至不打算进一步递归包含了就行了。 我们可以采取这一步。 返回树不等于空,所有的一切。 它做了一个在线的功能。 这也是一个例子短路评价。 但现在,它也是同样的想法 - 而不是 - 所以,如果树不等于空 - 或者说,好, 如果树不等于空,这是不好的情况下, 如果树等于null,那么第一个条件是假的。 所以假“与”与什么将是什么? [学生]假。 >>呀。这是短路评价的另一半, 如果树不等于空,然后我们都不会,甚至去的地方 - 独木等于空,那么我们就不会做价值==树价值。 我们只是要立即返回false。 这是非常重要的,因为如果没有短路求值, 那么,如果树不等于空,这第二个条件是要赛格故障, 因为树>的值被提领空。 所以,就是这样。这一点 - 一旦过了转移。 这是一个很常见的事情,这个没有这一行, 但它是一个共同的东西的条件下,也许不正确的, 但如果(树!= NULL,和树>的值==值),做任何事情。 这是一个非常常见的情况,在那里,而不必 要打破这个分为两个中频,在那里一样,是树空? 好吧,这不是空的,所以现在是树的值等于值吗?做到这一点。 相反,这种情况下,这将永远段错误 因为它会破坏,如果发生这种情况是空的。 嗯,我想,如果你的树是完全无效的指针,它仍然可以赛格故障, 但它不能赛格故障,如果树是空的。 如果是空的,这将打破之前你曾经解除引用的指针摆在首位。 [学生]:这是所谓的懒惰的评价吗? [鲍登]懒惰的评价是一个独立的东西。 懒惰的评价更像是你要求的值, 你问计算出一个数值,种,但你并不需要它立即。 所以,直到你真正需要它,它不评估。 这是不完全一样的东西,但在霍夫曼的pset, 它说,“懒洋洋”的编写。 我们这样做的原因是因为我们实际上是在缓冲写 - 我们不希望在同一时间写的各个位, 或单个字节的时间,而不是要得到一个块的字节。 然后,一旦我们有一个块的字节,然后我们将它写出来。 即使你问它来写 - FWRITE和fread做同样的事情。 他们缓冲的读取和写入操作。 即使你要求它立即写入,它可能不会。 你不能确定的东西都将被写入 直到你调用hfclose或不管它是什么, 然后说,好吧,我关闭我的文件, 这意味着更好,我写的一切,但我没有写。 它不需要编写了 直到您关闭该文件,然后需要的地方。 所以,这只是什么懒 - 等待,直到它发生的。 - 以51你将进入更详细, 因为OCaml和一切,一切都在51递归。 有没有迭代的解决方案,基本上。 一切都是递归和懒惰的评价 很多情况下是非常重要的 在那里,如果你没有懒洋洋地评估,这将意味着 - 该示例是流,这是无限长。 从理论上讲,你能想到的自然数为1-2-3-4-5-6-7流, 所以,懒洋洋地评估事情的罚款。 如果我说我想要的第十号,然后我就可以评估的10号。 如果我想百分之一的数量,然后我就可以评估到百分之数量。 没有懒惰的评价,那么它会尝试立即评估所有的数字。 您正在评估无限多的数字,这是根本不可能的。 因此,有很多情况下,懒惰的评价 得到的东西的工作是必不可少的。 现在,我们要编写INSERT插入将是 同样改变在其定义中。 所以,现在它的布尔插入(int值)。 我们要改变这种状况为bool插入(int值,节点树)。 我们实际上会改变,再次一点,我们就会明白为什么。 让我们继续前进build_node,只为它赫克, 上面插入,所以我们没有写一个函数原型。 这是一个暗示,你将要使用build_node在插入。 好吧。 ,一分钟的时间。 我想我保存的版本,如果你想拉, 或者,至少,我现在这样。 我想稍作休息时间,思考的逻辑插入, 如果你无法想起来了。 基本上,你将永远只能被插入的叶子。 想,如果我插入,然后我不可避免地将要插入1 - 我会改以黑色 - 我会在这里插入1。 或者,如果我插入,我要在这里插入4。 所以无论你做什么,你要插入的叶子。 所有你必须​​做的是遍历树,直到你得到的节点 这应该是节点的父节点,新节点的父节点, 然后改变其向左或向右的指针,这取决于是否 它是大于或小于当前节点。 修改这个指针指向新节点。 所以遍历树的叶点到新的节点。 也觉得为什么会禁止这类情况之前, 我构建二叉树,它是正确的 如果你只看着一个单一的节点, 但9左侧7,如果你遍历了所有的方式。 所以在这种情况下这是不可能的,因为 - 想插入的东西;(9)在第一个节点, 我会看,我只是要到正确的。 所以不管我做什么,如果我插入到叶, ,并使用合适的算法的叶, 这将是不可能的,我插入9日至7左 因为,只要我打7,我会去的权利。 有没有人有东西开始? [学生]:我做的。 “当然可以。 [学生,不知所云] [其他学生,不知所云] [鲍登的赞赏。好吧。要解释? [学生]因为我们知道,我们将 新的节点,在树的结尾, 我循环通过迭代树 直到我得到了一个节点,指出为空。 然后,我决定把它的右侧或左侧 使用此变量,它告诉我把它放在哪里。 然后,从本质上讲,我只是做,最后 - 该临时结点,它是创造新的节点, 无论是在左侧或右侧,这取决于什么值权。 最后,我设置了新的节点值,其测试值。 [鲍登]好了,所以我在这里看到一个问题。 这是95%的方式存在的。 一个问题,我看到,没有任何人看到一个问题吗? 的情况下,他们跳出循环是什么? [学生]:如果temp是空的? >>呀。因此,如何跳出循环,是如果温度为空。 但是,我该怎么办就在这里吗? 我解引用的温度,这是不可避免的空。 因此,其他的事情,你需要做的不只是跟踪,直到温度是空的, 你要跟踪的父母在任何时候都。 我们也希望*父节点,我想我们可以保持,空第一。 这是要为根的树有怪异的行为, 但我们会得到的。 如果值是大于任何,然后TEMP =临时的权利。 但在此之前我们做到这一点,父母温度。 或者父母总是平等的温度吗?是这样呢? 如果温度不为空,然后我要向下移动,不管是什么, temp是父节点。 所以,家长会为temp,然后我谨温度下降。 现在的温度是空的,但父母的事情是空的父。 所以在这里,我不希望设置等于1。 所以,我移动到右侧,因此,如果右= 1, 我猜你也想这样做 - 如果你移动到左边,你要设置等于0。 否则,如果你移动到右侧。 所以右侧= 0。如果右= 1, 现在我们要父权指针newnode, 否则,我们想使父左指针newnode。 该问题吗? 好吧。因此,这是我们的方式 - 好吧,其实不是这样做,而是 我们一半预计您使用build_node。 然后,如果newnode等于null,则返回false。 就是这样。现在,这是我们希望你做什么。 这是工作人员解决方案做什么。 我不同意这是“正确”的方式去了解它 但是,这是完全没有问题的,它会工作。 有一件事,这是一个有点古怪,现在是 如果树为空,我们传递了一个空树。 我想这取决于你如何定义传递一个空树的行为。 我认为,如果你传递一个空树, 然后插入值到一个空的树 应该只返回一个唯一的价值是单个节点的树中。 人们同意吗?你可以,如果你想, 如果你传递一个空的树 你想插入值,则返回false。 它是由你来定义。 要我说,然后做的第一件事 - 好了,你打算这样做有问题,因为 如果我们有一个全局指针的东西,它会更容易, 但我们没有,所以,如果树是空的,有什么我们可以做的。 我们就可以返回false。 所以我要改变插入。 我们在技术上可以只改变这一权利在这里, 它是如何遍历的事情, 但我要改变插入一个节点**树。 双指针。 这是什么意思呢? 而不是处理的节点的指针, 我要操作的东西是这样的指针。 我要操纵这些指针。 我要直接操纵指针。 这是有道理的,因为,想想下来 - 好了,现在这点为空。 我想要做的是操作这个指针指向为NOT NULL。 我想它指向我的新节点。 如果我只是记录我的指针的指针, 然后,我不需要跟踪的父指针。 我就可以跟踪看,如果指针指向空, 如果指针指向为null, 将其更改为指向我想要的节点。 我可以改变它,因为我有一个指针的指针。 让我们来看看这个权利。 实际上,你可以递归很容易地做到这一点。 我们要做到这一点呢? 是的,我们做的。 让我们来看看它递归。 首先,什么是我们的基本情况又如何呢? 几乎永远是我们的基本情况,但实际上,这是一种棘手的。 首先第一件事情,如果(树== NULL) 我想我们只是要返回false。 树是空的,这是不同的。 这就是指针到你的根指针为null 这意味着你的根指针不存在。 因此,在这里,如果我这样做 节点* - 让我们只是重复。 节点根= NULL, ,然后我就打电话给插入,做这样的事情, 和根中插入4。 因此,根,如果根是一个节点* 然后与根将是一个节点**。 这是有效的。在这种情况下,树,在这里, 树不为空 - 或插入。 在这里。树不空; *树为空,这是很好 *树,因为如果是空的,那么我可以操纵它 现在指向什么,我想它指向。 但是,如果树是空的,这意味着我来到这里,说空。 这没有任何意义。我不能做什么用的。 如果树是空的,则返回false。 所以,我基本上已经说了我们真正的基本情况是什么。 那是什么打算? [学生,不知所云] 波顿:是的。所以,如果(*树== NULL)。 这涉及到的情况下在这里 我的红色指针,如果指针,我很专注, 我集中在这指针一样,现在我专注于这个指针。 现在我专注于这个指针。 所以,如果我的红色指针,这是我的节点** 曾经是 - 如果*,我的红色指针,是以往任何时候都为空, 这意味着,我在我专注于一个指针指向的情况下 - 这是一个指针,属于一片叶子。 我想改变这个指针指向我的新节点。 快回来。 我的newnode将是节点* N = build_node(值) 那么n,如果n = NULL,则返回false。 否则,我们要改变指针指向 现在我们新建的节点。 事实上,我们可以做到这一点。 而不是说Ň,我们说* = *树的树。 每个人都明白吗? ,处理指向指针的指针, 我们可以改变空指针指向它们指向我们想要的东西。 这是我们的基本情况。 现在,我们的复发,或我们的递归, 将是非常相似,我们已经做了所有其他的递归。 我们将要插入的值, 现在我要再次使用三元,但我们的条件是什么要? 它是什么,我们要寻找的决定,我们是否要向左走还是向右? 让我们这样做在单独的步骤。 (值)是什么? [学生]:这棵树的价值? 鲍登所以请记住,我目前 - [学生,不知所云] [鲍登]是啊,所以就在这里,让我们说,这个绿色的箭头 是什么树目前是一个例子,是一个指针,该指针。 因此,这意味着我是一个​​指针,指向一个指针,指向3。 两次解引用听起来不错。 这是什么 - 怎么我做的是什么? [学生]:取消引用一次,然后做箭头? [鲍登](树)提领一次, - >值 是想给我的价值,我间接指向的节点。 所以我也可以写它** tree.value的,如果你喜欢。 无论是工作的。 如果是这样的话,那么我想打电话给插入与价值。 什么是我更新的节点又如何呢? 我想往左走,所以** tree.left的将是我的左手。 我想这东西的指针 所以,如果左边的结束是空指针, 我可以修改它指向我的新节点。 其他情况下,可以是非常相似的。 其实,我的三元现在。 插入值,如果值<(**树)。值。 然后我们要更新我们的**的左侧, 否则,我们要更新我们的**的权利。 [学生]:那拿到的指针的指针? 鲍登 - ** tree.right是节点的明星。 [学生,不知所云] >>呀。 ** tree.right是这样的指针或什么的。 因此,通过一个指向,这给了我我想要的 那家伙的指针。 [学生]:我们能不能​​走一遍,为什么我们使用的是两个指针吗? 鲍登]是啊。所以 - 不,你可以,而且该解决方案之前 一种方法做这件事而不做两个指针。 你需要能够了解两个指针, 这是一个清洁的解决方案。 另外,请注意,会发生什么,如果我的树 - 发生什么,如果我的根目录为空?在这里如果我这样做的情况下,会发生什么情况? 因此,节点*根= NULL,插入4到与根。 什么是根将是在此之后呢? [学生,不知所云] >>呀。 根值是4。 根左边的这个是空的,根本的权利是空的。 的情况下,我们没有通过根地址, 我们不能修改根。 树 - 根为空的情况下, 我们刚刚返回false。我们没有什么可以做的。 我们不能插入到一个空的树节点。 但现在我们可以到一个节点树,我们只是一个空的树。 这通常是预期的方式,它应该工作。 此外,这是显着短于 跟踪的父母,所以你遍历了所有的方式。 现在,我有我的父母,我只是有我的父权的任何指针。 相反,如果我们这样做迭代,它会是一个while循环同样的想法。 但不是我的父指针处理, 而不是我现在的指针的东西 我直接修改指向我的新节点。 我没有处理,无论是指向左边。 我没有处理是否指向正确的。 这只是不管这个指针,我将其设置为指向我的新节点。 每个人都明白它是如何工作的? 如果没有,为什么我们想这样做,这样一来, 但至少,这个工程作为一个解决方案? [学生]:我们从哪里传回是真的吗? 鲍登这很可能就在这里。 如果我们正确地插入,则返回true。 否则,在这里我们将要返回任何插入的回报。 和有关这个递归函数有什么特别呢? 这是尾递归的,所以只要我们编译了一些优化, 它会认识到,你将永远不会得到一个堆栈溢出, 即使我们的树的高度1万或10万。 [学生,不知所云] [鲍登]我认为它在短跑 - 优化级别 需要被认可为一个尾递归。 我认为它承认 - GCC和Clang的 也有不同的含义的优化水平。 我想说这是达绍2,为确保它会识别尾递归。 但是,我们 - 你可以构建这样一个Fibonocci的例子或什么的。 这是不容易的测试,因为它是难以建立 这么大的一个二叉树。 但是,是的,我认为这是达绍2, 如果在编译时使用达绍2,它会寻找尾递归 并优化了这一点。 让我们回去 - 插入从字面上它需要的最后一件事。 让我们回到在这里插入 我们要去的地方,做同样的想法。 它仍然有缺陷,不能够完全处理 当根目录本身是空的,或在过去的项目是空的, 但是,而不是处理与父母指针, 让我们应用同样的逻辑,保持指针的指针。 如果我们保持我们的节点**当前, 而我们不需要跟踪了, 但节点**当前和树。 现在,我们的while循环将是*电流不等于空。 不需要跟踪的父母了。 不要需要跟踪的左边和右边。 我会打电话给它温度,因为我们已经使用温度。 好吧。所以,如果(值> *温度), (临时) - >右键 TEMP =&(*温度) - >离开。 而现在,在这一点上,这个while循环后, 我只能这样做,因为也许它更容易比递归迭代想想, 但这个while循环后, * temp是我们要改变的指针。 之前,我们的父母,我们想改变父母任何一方左或父权, 但如果我们想改变家长的权利, *温度是父母的权利,我们可以直接改变它。 所以在这里,我们可以做TEMP = newnode,这就是它。 因此,通知,我们在这行代码。 为了保持轨道是额外的努力在所有的父。 在这里,如果我们只是一味地跟踪指针的指针, 即使我们想摆脱现在所有这些大括号中, 使它看起来更短。 这现在是完全一样的解决方案, 但更少的代码行。 一旦你开始认识到这是一个有效的解决方案, 它也更容易的原因有关,而不像,没关系, 为什么我有这个标志的诠释权吗? 这是什么意思呢?哦,这是表示 我每次去正确的,我需要设置, 否则,如果我向左走,我需要将其设置为0。 在这里,我没有原因有关,它只是更容易思考的问题。 有问题吗? [学生,不知所云] >>呀。 好了,所以在最后一位 - 我想一个快速和简单的函数,我们可以做的是, let's - 一起,我想尝试写一个包含功能 不关心它是否是一个二叉搜索树。 这包含函数应返回TRUE 如果在此二叉树的价值是我们正在寻找的任何地方。 因此,让我们第一次做递归和迭代,我们将做到这一点。 事实上,我们可以做起来,因为这将是非常短的。 什么是我的基本情况又如何呢? [学生,不知所云] [鲍登]所以,​​如果(树== NULL),然后呢? [学生]:返回false。 [鲍登否则,好了,我不需要别的。 如果是我的基本情况。 [学生]:树的价值呢? >>呀。 所以,如果(树 - >值==值。 请注意,我们又回到了节点*,而不是节点的**吗? 蕴涵永远不会需要使用一个节点** 因为我们没有修改指针。 我们只是遍历。 如果出现这种情况,那么,我们要返回true。 否则,我们要遍历的孩子。 因此,我们不能推理是否所有的左边是 的一切权利。 那么,什么是我们的条件,要在这里 - 或者说,什么是我们该怎么办? [学生,不知所云] >>呀。 返回包含(价值树 - >左) 或(价值树 - >右)。就是这样。 发现有短路的评价, 如果我们碰巧发现在左边的树形, 我们永远需要寻找正确的树。 这是整个函数。 现在,让我们做迭代, 这将是那么好。 我们将采取一贯的起始节点的电流=树。 虽然(当前= NULL)。 快速将看到一个问题。 如果电流 - 在这里,如果我们打破这个, 然后,我们已经用完了的事情来看待,所以返回false。 如果(当前值==值),则返回true。 所以,现在,我们是在一个地方 - 我们不知道,我们是否要向左走还是向右。 所以,随意,让我们去离开。 显然,我遇到一个问题,我已经完全放弃一切 - 我将永远只能检查左侧的树。 我永远都不会检查任何孩子的东西是正确的。 我该如何解决这个问题? [学生]:您有堆栈跟踪的左,右。 鲍登]是啊。所以,让我们把它 结构列表,节点n,然后节点**吗? 我认为正常工作。 我们想要去的左,或let's - 在这里。 结构列表的列表=,它会开始 出在这个结构列表。 *列表= NULL。所以这将是我们的链表 子树,我们已经跳过了。 我们要遍历现在剩下的, 但由于我们无可避免地要回来的右侧, 我们要保持我们的结构列表内的右侧。 然后,我们,将有new_list或结构, 结构列表,new_list的malloc(sizeof(列表)的)。 我要忽略错误检查,但你应该检查,看它是否为NULL。 New_list的节点,它的指向 - 哦,我想这就是为什么它在这里。要指出的第二个结构列表。 这是多么链表的工作。 这是相同的作为一个int链表 除了我们刚刚更换的int节点*。 这是完全一样的。 所以new_list,的价值我们的new_list节点, 会是电流>右键。 我们new_list的价值 - >明年将是我们原来的名单, 然后我们来更新我们的列表中指向new_list的。 现在,我们需要某种方式拉的东西, 就像我们所走过的整个左子树。 现在我们需要把它拉出来的东西, 如当前是空的,我们不希望只是返回false。 我们现在要在外面拉我们新的列表。 一种方便的方法,这样做的 - 其实,有多种方式这样做。 任何人有建议吗? 在哪里我应该这样做,或者我应该这样做吗? 我们只有一两分钟,但有什么建议? 相反 - 的一种方式,而不是我们的条件,同时, 我们目前正在不为空, 相反,我们要继续走,直到我们的名单本身是空的。 因此,如果我们的列表为空, 然后我们跑出来的东西,寻找,搜寻。 但是,这意味着在我们的名单的第一件事,只是将第一个节点。 的第一件事是 - 我们不再需要看到的。 所以列表 - > n将是我们的树。 列表 - >下一个会是空的。 而现在名单不等于空。 cur是要拉的东西从我们的名单。 因此,当前要平等列表 - > N。 ,然后列出要平等列表 - > N,或列表下。 因此,如果当前值等于值。 现在我们可以添加我们的权利,指针和我们的左指针 只要他们不为空。 到这里,我想我们应该这样做,是摆在首位。 如果(电流>好吧!= NULL) 那么,我们该节点将要插入到我们的名单。 如果(电流左),这是一点点额外的工作,但它的罚款。 如果(电流左!= NULL), 我们要我们的链表中插入左, 这应该是它。 我们遍历 - 只要我们有一些在我们的名单, 我们有另一个节点来看看。 因此,我们期待在该节点上, 我们推进我们的列表中的下一个。 如果该节点是我们正在寻找的价值,我们就可以返回true。 否则插入我们的左,右子树, 只要他们不为空,进入我们的名单 所以,我们不可避免地走了他们。 所以,如果他们不为空, 如果我们的根指针指向两件事情, 然后我们把车停在第一的东西,所以我们的列表为空。 然后我们把两件事情回来,所以现在我们的名单是大小为2。 那我们是要循环,我们只是要拉, 比方说,我们的根结点的左指针。 那将只是不断发生,我们将结束循环一切。 请注意,这是显着更复杂 在递归的解决方案。 我已经说过多次, 的递归解决方案通常有很多共同之处,与迭代求解。 在这里,这是什么做的递归解决方案。 唯一的变化是,而不是隐式地使用堆栈,程序堆栈, 跟踪哪些节点需要访问的方式, 现在,你必须明确地使用链表。 在这两种情况下,你跟踪哪些节点仍然需要访问。 在递归的情况下,它只是更容易,因为堆栈 你的程序堆栈来实现。 请注意,此链接的列表,这是一个堆栈。 无论我们只是把在堆栈上 我们马上要去拉断的堆栈访问下。 我们没时间了,但什么问题吗? [学生,不知所云] 鲍登]是啊。所以,如果我们有我们的链接列表, 当前要指向这个家伙, 现在我们只是推动我们的联名单专注于这家伙。 我们穿越过该行的链表中。 然后,我想我们应该帮助我们的链表之类的东西 前一次返回true或false,我们需要 我们的链表遍历,并一直在这里,我想, 如果我们当前不等于,添加它,所以现在我们要释放 电流,因为,我们完全忘了该列表?是啊。 所以,这就是我们想要做的。 指针在哪里? 当前是 - 我们需要一个结构列表* 10等于列表旁边。 免费列表,列表温度。 的情况下,我们返回true,我们需要遍历 在剩余的联系列表中解放出来的东西。 美好的事情被释放的递归解决方案 只是意味着会发生堆栈中弹出承购关闭。 因此,我们已经走了的东西,就像3行认为难以对代码 显著更多的东西,是很难认为有关的代码行。 还有什么问题吗? 好的。我们是很好的。再见! [CS50.TV]