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