章节3.3.2，二叉树的性质与存储结构

基本每年都考。

本题考察几种二叉树的定义和特点。答案选B。

满二叉树：常常和另一个完全二叉树一起说。满二叉树中叶子节点的深度都一样，叶子节点都有兄弟节点。编号原则是广度优先，一层一层的依次编号。书上说的比较少，就给了一个公式：总节点个数=2的深度次方再-1，往年好像也考过。

完全二叉树：这个和满二叉树极其相似，也就是满二叉树中，上面的枝干不变，最后一层(重点)叶子节点，从右往左依次砍掉一些叶子（不能从左往右砍，也就是从左往右数的时候中间不能留空），也就是如果有节点的孩子节点只有一个的话，只允许最后一层的其中一个是左孩子。按书上的第120页的定义的话最后一层必须砍一些，不砍不行，不砍就只能叫满二叉树。

线索二叉树：在3.3.4章节。原文：“但在二叉链表存储结构中，只能找到一个结点的左、右孩子，不能直接得到结点在任一遍历序列中的前驱和后继，这些信息只有在遍历的动态过程中才能得到，因此，引入线索二叉树来保存这些动态过程得到的信息。”好像没有进一步规定是什么形状的。

最优二叉树：在3.4.5章节。又称为哈夫曼树。特点是带权的，要带权路径长度最小。所以这个树和元素的值有关系，只知道元素数量也不能确定深度。构建过程及其特点可以参考这个题：www.z21.org/question/69 

二叉排序树：在3.5.3动态查找表这个章节。又叫二叉查找树。特点：1、一边查找一边生成。2、把整棵树按结构压扁之后，从左到右是从小到大排序的。3、任意一个节点中，左子树的所有的值都比当前节点的值小(也可能没有节点)，右子树都要比当前节点大。4、中序遍历可以得到一个排好序的序列，就是前面压扁的序列。所以明显这个排序树也是和值有关系，无法确定深度。

另外在动态查找表这一章节中，还介绍了平衡二叉树(ALV树，2015、2014、2013等年份考过他们的区别)、B树(好像没考过，不过对学java和数据库的应该比较重要)一共三种树。ALV树只是对任一节点的左右子树的高度的控制，高度之差不能超过1。（当然值也是压扁后是有顺序的。另外在java中通常把实现的红黑树来和平衡二叉树进行对比异同）。