大家好。 数据结构与算法这一讲，我们开始第5章二叉树的学习。首先，我们来介绍一下基本概念。
二叉树是结点的有限集合组成的。
这个有限集合有可能是一个空集。
如果不空，也就是由一个根，以及分别称作这个二叉树的左右子树的
子二叉树组成。二叉树有5种基本形态。
也就是左右都不空，以及左空，右空，还有左右都空，就是独根的二叉树。
不要忘了，我们还有整个都空，它也是一个二叉树。
二叉树的术语里面，结点是一个非常重要的概念。
我们有父子结点，还有兄弟结点，分支结点，叶结点等等
概念。结点里面，根结点是特别的一个结点。
边，实际上是结点的有序对。
有序实际上是说，从根到叶的方向，
这个是边的方向。但是因为它都是从根发
出的，所以这里，省略掉这样的一个箭头。
在从根到二叉树里面某一个结点
它的这么一个方向的过程中，形成了一个路径。
路径的长度，实际上就是
这里面的有效边的个数。
在这条路径上，所有比较靠近根的这些
结点，就是那些比较靠近叶的结点，它们的祖先。
我们定义
二叉树里面，根是第0层。然后其它
的结点，都是它们的父结点的层数加1。
深度实际上就是最深的那一个
叶结点，它所在的层数。高度就是层数加1。
实际上，我们如果说是从根到最低的这个
叶结点，这样的一条路径上，它的深度
就是这里面的有效边的个数。
高度实际上就是它所涉及到的
结点的这样的个数。 满二叉树在数据结构里面是一个非常重要的概念。
这种二叉树，也就是
要么，这些结点呢，它就是处在树叶这一级。
要么，如果它是内部结点呢，它是都是有两个结点。这就是一个满二叉树。
完全二叉树实际上就是说从
根开始，从上到下，从左到右满满当当的，把这些结点组织起来。
只有最下一层的结点，它可以不是完全的满员的。
但是，也必须是都集中在最左边，就是像我们
右上方的树。左下方的树，它就不是一个完全的二叉树。
对于这样的一个二叉树，
如果是说它是叶结点，或者是说它的
子结点个数是一个，那我们把它扩展出
这两个外部结点，或者是只一个外部结点，这就是一个扩充二叉树。
这样的话，原来的这些结点，它都变成了内部结点，也就是分支结点。
而扩充出来的结点都是在这叶这一层。
我们有一个性质，就是说外部路径的总长度E，
等于内部总长I加上2n。 二叉树有这么一些性质。
我们来看第1个性质，就是说，第i层上，最多有
2i个结点。这个实际上就是说，这个二叉树，它能有
多么饱满。还有就是性质2，就是，深度为k的二叉树
至多有2的k加1次方减1个结点。
那实际上也是说的，我们这样一个有深度限制的这么一个二叉树，
我能够把它摆多满。性质3就是说
如果一个二叉树里面，它的终端结点，就是度为0的这些叶结点，
为n0个。那度为2是n2个，那么我们有一个关系，就是n0等于n2加1。
其实，性质4就跟性质3有点关系了。
那就是满二叉树性质，这个满二叉树
性质，就是说，有非空的满二叉树。
那么，它的树叶的数目就等于分支结点的数目加1。 对它还有一个推论。
性质6说的就是，如果有n个结点，
我们能构成，一个多高的
二叉树呢？我们看一下特殊情况，就对于这个完全二叉树。
它就比较饱满，又满又胖。那排到满满当当的情况下，
它的高度会是logn级的。这也就是说
如果你有n个结点，你至少也是logn这样的高度。
好，我们思考一下这两个问题，扩充二叉树
它和满二叉树有什么关系，以及
刚才说的6个性质，它们之间有什么关系呢？
谢谢大家。