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