[Powered by Google Translate] 你将如何代表所有家庭成员在一台电脑吗？
我们可以简单地使用一个列表，
但这里有一个清晰的层次结构。
>> 比方说，我们已经开始与你的伟大的祖母，爱丽丝。
她有两个儿子，鲍勃
和你的祖父，查理。
查理有3个孩子，
戴夫，你的叔叔，阿姨，夏娃，你的父亲，弗雷德。
你是弗雷德唯一的孩子。
>> 为什么会以这种方式组织你的家庭成员
比简单的列表表示？
其中一个原因是，这种分层结构中，
被称为“树”，不是一个简单的列表中包含更多的信息。
我们知道每个人的家庭之间的关系
仅仅通过审查树。
此外，它可以加快
看时间大幅增加，如果树对数据进行排序。
>> 我们不能利用的，在这里，但我们会很快看到一个这样的例子。
每个人的表示的树的一个节点上。
节点可以有子节点
以及作为父节点。
这些技术术语，
即使在使用树木的事情，除了家庭。
Alice的节点有2个孩子，没有父母，
而查理的节点有3个孩子和1父。
>> 叶节点是一个没有任何儿童
的外边缘上的树。
最上面的节点树的根节点，
没有父。
>> 二叉树是一种特殊类型的树，
每个节点都有，最多2名儿童。
下面是C中一个节点的二进制树的结构的
每个节点都有与它相关的一些数据
和2到其他节点的指针。
>> 在我们的家谱，
的相关联的数据是每个人的名字。
在这里，它是一个int，但它可以是任何东西。
事实证明，
一个二叉树不会是一个很好的家庭表示，
因为人们经常有2个以上的孩子。
>> 二叉搜索树
二叉树是一种特殊的，有序的类型
让我们看看在价值迅速。
您可能已经注意到
每个节点的树的根目录下
是另一棵树的根，称为“子树。”
在这里，树的根是6，
和其子，2，是根的子树。
>> 在二叉搜索树
所有节点的值的右子树
大于该节点的值。 ：6。
那么，一个节点的左子树中的值
小于该节点的值。
如果我们需要处理重复的值，
我们可以改变这些松散的不平等，
这意味着相同的值，可以向左或向右下降，
只要我们保持一致，整个。
此树是二叉搜索树
因为它遵循这些规则。
>> 这是怎么会看，如果我们把所有的节点C的结构。
请注意，如果一个孩子失踪，
指针为空。
我们如何检查，看看在树上吗？
我们从根开始。
七是大于6，所以如果是在树中，它必须是正确的。
然后，它是小于8，因此必须将其留下。
在这里，我们发现了7。
现在，我们将检查5。
五是小于6，所以它必须是向左侧。
五是大于2，
所以它必须是正确的，
也是大于4，所以它必须是便又。
然而，这里没有孩子。
指针为NULL。
这意味着，5是不是在我们的树。
>> 我们可以用下面的代码的二进制树搜索：
在每一个节点上，我们要检查一下，如果我们发现
我们正在寻找的价值。
如果我们不找到它，我们确定它应该是
向左或向右子树检查。
这个循环将继续向下树
直到有没有子节点上的左侧或右侧。
>> 请记住，是不是在树中。
我们怎么插入呢？
这个过程看起来类似搜索。
我们遍历树从6
左为2，
右至4，
对了，但4有没有孩子这一边。
5，这将是新的位置，
它会开始无子女。
>> 二叉搜索树的操作速度有多快？
请记住，Bigohnotation的目的是提供一个上限。
在最坏的情况下，
我们的树可能仅仅是一个链表
也就是说，插入，缺失，和搜索
可能需要时间在树中的节点的数目成正比。
这是O（n）的。
>> 例如，下面是一个有效的二进制搜索树。
但是，如果我们试图找到9，
我们要遍历的每个节点。
这是没有比一个链表。
理想的情况下，我们希望每一个节点
我们的二叉搜索树，有2个孩子。
通过这种方式，插入，删除和搜索
所做的那样，在最坏的情况下，O（log n）的时间。
从之前的树更加平衡，
是这样的。
现在，任何价值需要，顶多3个步骤。
此树是平衡的，
的意义，这有一个最小的深度
相对于节点的数目。
>> 寻找平衡的二叉搜索树中的一个值
类似二进制搜索排序的数组。
事实上，如果我们不需要插入或删除项目，
他们的行为完全一样的方式。
然而，一个树结构是更好的
处理插入和删除
>> 我的的名字是Bannus范德Kloot。
这是CS50。