哨兵
- 在数组中查找某个元素
- 能不能把循环内的判断条件缩减一下呢？这个时候我们可以建立哨兵
- 将第0号元素设为待查找元素，这样循环中断的条件就只能是当前元素等于待查找元素了。
二分查找
- 比方说有11个元素从小到大（一定要按顺序）存放在数组中，那么二分查找某个元素，首先访问第6个元素，然后接下来可能访问第3/9个元素，再一层层二分下去，可能访问的元素的下标（+1）整理成一棵二叉树是这样的：
- 判定树上每个结点需要的查找次数指的是访问到该结点时是第几次查找了。
- n个结点的判定树的深度的计算方法：因为每次查找都将查找范围除以2（缩小一半），所以判断n能除几个2就行了，也就是log n，+1是因为最后范围应该是缩小到1而不是2
- ASL表示查找某个元素所需查找次数的平均值
树
- 对于A来说，它的子树就是那么4个了
- 结点的度也就是一个结点下面连有多少边了
- 树的度就是找哪个结点下面的边最多了，最多的边数就是树的度了
树的表示
- 如果每个结点的指针域要存放所有指向子结点的指针的话，那么就要根据最多的子结点来设计，会造成空间浪费。
- 多数情况下我们会选择用链表来存储二叉树，因为如果一个二叉树有很多结点是空的话（非完全二叉树）,数组当中就会浪费很多空间来存放这些没有的结点。
- 要对一棵树进行层序遍历的话，如果这棵树是用数组存储的，那直接顺序打印数组就是层序遍历的结果了。
特殊二叉树
- 完美二叉树：除了最底层是叶节点，其余每个结点都有两个子结点。
- 完全二叉树：从满二叉树中按顺序从尾到头拿掉一些结点后形成的树。比如，如果把上面I结点拿掉的话那么6原本9号应该是D的儿子H的兄弟，现在却变了，因而不是完全二叉树。
- 完全二叉树可以用数组来存储，不会浪费空间的。
二叉树的性质
二叉树的存储
- 由上述遍历过程可以总结出，每个结点都会被碰到三次
- 算法实例：第三讲->3.3第2小节
- 那个初始化栈不知道是怎么初始化的，反正就是能保证未压栈前非空，全部弹栈后为空就对了。
二叉树遍历的运用
- 算法实例：第三讲->3.3第3小节
- 在先序遍历的打印语句上加个条件判断是否叶子结点，是才打印。
- 利用后序遍历的框架来做
- 根结点是运算符，叶结点是运算数；每个运算符都要把左右子树相加。
- 中缀表达式是不准的，如果把某两个符号调换一下：
- 显然所得的就不是原本的二叉树想要计算的表达式了。但是，我们可以在输出左子树的时候先输出左括号，左子树结束的时候再输出右括号。这样就可以输出正确的表达式了。
- 至少要给出两种遍历序列，并且其中一种必须是中序遍历 (因为前序和后序分别将根结点放到了最前和最后访问，因此前序遍历序列的首元素就是、后序遍历的尾元素就是二叉树的主根，但是有时候其他元素是左是右我们是不清楚的)。
- 比如上面那个就是了
- 算法实例：第三讲->3.3第4小节
二叉搜索树
- 总之就是左子树比根结点小，右子树比根结点大。
- 有可能不平衡，不一定是完全二叉树的。堆才是完全二叉树。
- 尾递归一般都能用循环来代替，因为非递归效率更高。
- 如果树全部往左边靠或者全部往右边靠的话，查找的效率就大大降低了
- 算法实例：第四讲->4.1第1小节
- 算法实例：第四讲->4.1第3小节
那灿若星辰的眼底，有惊喜，随即换上了气恼，有憎恨，但很快又被爱意淹没，最后竟是满眼的无奈
