大家好。数据结构与算法
这一讲继续第五章二叉树的学习。
我们今天的主要内容是二叉树的存储结构。
二叉树是一种复杂的非线性结构。
那对于这种复杂结构，我们一般来说
是不太方便完全用顺序的方法来存储它的。
我们往往采用动态的链接的方法来存储。
因为二叉树，它有左、右子结点这样的信息。
因此，我们特别方便的就是采用
二叉链表的形式来存储它。当然中间还有它具体的这个
info的数据域的信息。现在也有很多人比较喜欢用三叉链的形式来实现。
也就是多加一个 parent 指向父指针的
这么一个指针域。有这个域，有什么好处呢？那主要的就是
我们在往上头找这些先驱的这些结点以及
找它的左右兄弟结点的时候， 比二叉链表要方便很多。
那我们来看这样一个二叉链表的
存储结构，那左边是一个二叉树。
那右边呢就是对应的二叉链表的这样的一个存储结构。
可以看到很多结点里面的指向左孩子右孩子这个指针域
都是空的。可以说几乎有一半这样的结点是空结点。
那再来看这个三叉链的形式。它的主要的
改进呢就是说，我们加了这么一个父指针域，
加了父指针域以后呢我们从任何一个结点可以非常方便的
追溯到根。那当然这个追溯的路径上头的一些其它的
祖先结点以及它们相应的兄弟的这些信息也都能够很方便的访问得到。
但是，在我们进行岔路删除操作的时候，
也需要同时维护这样的父结点的信息。
那我们怎么来实现这样一个二叉链的存储结构?
那其实在我们前面定义的这样一个二叉树结点的
ADT之上，除了这个
info，那我们主要的就是要加上这样一个left和right
这样的相应的指针信息。那在这样的一个
二叉链形式实现的数据结构里面，
我们怎么样来寻找父结点呢？
我们要注意，因为它没有往上的这样一个父结点指针，因此，
我们所有的这种操作呢，都需要从根开始来找到相应的父结点。
我们来看这样的一个递归实现。
首先，我们是要从这个
当前的这个子根开始，因为它是一个递归实现，所以最开始的时候是传入的根。然后呢，在中间是传入到某一个子根。
如果是子根结点它不空的情况下，
我们判断这个子根的左右子孩子是不是你要找的这个结点。
那如果是的话呢，这个子根本身它就是我们要寻找的结点的父结点。
如果没有找到，那我们就分别下降到
这个子根它的左子树，或者是它的右子树。
去继续查找。那我们可以观察一下这个框架，
它其实就是一个先序遍历的框架。
这边是对左子树的一个递归操作。然后这第二个语句呢是对右子树的递归。
然后，它对这个结点进行操作处理的重要的这个部分呢，
就是在这两个递归之前，
那其实就是替代我们前面说的
这样的一个递归的深搜遍历里面前序里面的这个visit的这个位子。
那我们刚才已经讨论过了这个算法它是什么框架以及是用什么序来遍历的。
那我们再来想一想，这个刚才用的是递归，
那我们能不能够用非递归的呢？另外就是说，这个算法它能不能够用宽搜来实现呢？
还有，这个算法它其实是一个比较通用的框架。
它这个框架它的主要的意思是找父结点，但是找兄弟结点其实
也是用类似的框架实现的。那我们现在来看，用非递归的方法来实现。
那我们采用的就是非递归的这个框架。因为它是对应的一个
前序遍历的这么一个框架，所以我们用的就是非递归的前序框架。
那最开始我们把根结点
赋给在一个临时的指针。然后呢，
我们在一个栈里面呢，是存了一个监视哨。
然后我们从这个指针开始往下头找。那如果这个临时指针
pointer 它的左右结点就是我们要找的那个
current。那当前的这个 pointer 呢，它就是 current
的父结点。那如果没有找到的话呢，那我们就要想，
我下面再继续操作的时候我应该怎么办。那我们要保留这个
pointer它的一个非空的右子结点，因为我们现在呢
可以进到它的左子树，因此呢，下面要左子树访问完了以后
那再继续要访问它的右子树的时候就可以从栈里面拿了。因此呢，
我们就是把它的非空的右结点入到栈里面。
然后就下到它的一个非空的左子结点。
那如果是说这个左子结点是空的，那我们就是表示左子树已经访问完了。
我们要从栈里面拿出它前面存的那些待访问的
某些右结点的信息。然后呢，弹栈再继续刚才的这样一个操作。
我们来分析一下二叉链的空间开销。
那首先我们注意一下有这么几个概念。
存储密度呢，它表达的是存储的效率，
实际上也就是说，有效的数据占整个数据它的比例。结构性开销呢，实际上就是说我为了存这些有效的数据，
我还加了哪些辅助的信息来完成这个存储。
那辅助的信息呢，它占整个数据结构的一个比例。
那对于这样的一个二叉链的结构，
那我们根据满二叉树定理，我们可以看到，就是有一半的这个指针域是空的。
那每个结点它要存两个指针域，一个数据域。
假设指针域和数据域是相等的话呢，那这个结构性的开销呢，
就会是三分之二，那实际上它的存储的密度也就只有三分之一。
那我们怎么样来提高它的这样一个存储效率呢？
在C和C++里面呢，比如说在C里面我们可以用
union的类型来定义。而似乎就是分支和叶结点可以统一。
然后我们这个，也许看看哪一个是存得更少，
那我们那一个是不是能够存得更有效一些呢。但是其实，
union它有这么一个特点，也就是union里面它有几个
类型的话，那我们要预留的存储空间是
最长的那个那些，所以这只是说，在表达形式上看起来好像统一了，但其实在存储效率上
其实没有什么本质的改进。然后在C++
里面，也可以用子类和虚函数来实现，那这个也只是说从概念上给它区分。
但，其实存储的空间其实没有特别本质的改进。
早期，因为内存资源有限，可能有一些方法来改进这个存储效率。
我们可以直接存储这个叶结点它的值，而
不需要再另外开辟一个叶结点。而这个叶结点，
它指向的就都是一些外部的这个空，有浪费那个指针。
当然，为了要区别我们是在利用了这个指针来存到别的数据，
还是说本来它就是个指针域，那就是说，还需要用一些方法来标记。
因为想节省内存，所以就想着说干脆用这个指针来
表示，就是指针我们一般它是比较大的，就是
一般也就在四字节，有的机器是八字节。那么在高位总是零的。
那么就用这个最高位的这个位来做它的标记位。那这种方法的话，
它带来算法的复杂度，就是说那种算法是非常难写难读的，难维护的。因此，我们基本上现在不怎么使用这些方法。
好，那对于一些特殊的二叉树，我们可以采用顺序存储方法。
例如对这个完全二叉树，它就可以进行顺序的储存。
因为，完全二叉树呢，它的这个结构，
它是从上到下，从左到右，满满当当的存储的。因此呢，
我们可以把它放在一个数组里头，
就是按照它的这个编号直接放进去。
那从存储上来说，它就是一个线性的了。但是，逻辑上它还是一个二叉树形的结构。
而且我们可以很方便的通过它存储在数组里面的相应的下标，
来计算出它的父结点和左右子结点的相关的下标。
那我们看一下完全二叉树的下标公式。
对于这么一个完全二叉树，我们这里的习惯编号是从0开始编。也有人是啊从
1开始编。那么，在这么一个完全二叉树里面，我们可以看到，
大约有一半的结点呢它是没有子结点的。
对于这个另外一半比较靠近根的结点，它有子结点的情况。
那么这种时候呢，它的结点i它的左孩子就是2i+1，
然后相应的右孩子是2i+2。
那我们再来看它的父结点。父结点的话呢，
就是i-1除以2取下整。那可以算出来。
而且这里面有一个规律就是在我们的编号体系里面呢，左兄弟这个情况呢它们都是奇数的，
然后，右结点这个情况呢，他们是偶数的。
因此，对于这个奇数的这么一个结点，那它的
右兄弟呢，就是i+1。
那对于偶数情况，就是把它的下标呢，再减1
就找到它的左兄弟。所以我们可以很方便的计算出他们的这种相应的逻辑的这种关系。
好，那我们给大家啊留两个思考题。
第一个呢，就是说，我们的一般的教材呢都是用二叉链的形式
来写这个二叉树的相应的算法。那如果我们用
三叉链的时候，那这些算法要做一些什么改变？
我们要特别注意对于插入删除的时候，维护这种父指针的信息。
还有就是对于完全三叉树，
我们是不是也有一套下标公式？
而且我们当然是可以把它存储在这样一个数组里头的。
好，谢谢大家。