二叉树可支持 频繁加入/删除项 和 频繁查找项。
查找时基本相当于二分法查找！
二叉树
直接定义排在父节点前的放在左子节点，排在父节点后的放在右子节点。
查找的时候，不是可以直接根据父节点就能排除一半不用查询了嘛。这就利于查找了！
（图片均来自C Primer Plus）
二叉树定义
最好的办法是采用和链表一样的方法定义。通过指针动态分配链式节点。
typedef SOMETHING Item; //something 表示要存储的结构体类型
typedef struct trnode //每个节点包含数据和指向两个子节点的指针
{
Item item;
struct trnode * left;
struct trnode * right;
}Trn;
typedef struct tree //存储二叉树根节点的地址和树的项数
{
trnode * root;
int size;
}Tree;
实现
添加项
先检查二叉树中有没有相同项，项不能重复。检查是否有空间放下此添加项。
- 分配内存空间，写入数据
- 确定新节点的位置
这一部分就比较简单了，判断左右值。类似二分法查找。
删除项删除尾项比较简单，考虑的是删除中间项。
删除一个叶节点：
删除有一个子节点的节点：
删除有两个子节点的节点：
一直沿着子树往下找，直到找到空位再接上。
遍历树可想而知遍历树很复杂，可用递归来遍历左右。
- 处理节点中的项
- 处理左子树(递归)
- 处理右子树(递归)
清空树和遍历树做法相类似。
二叉树只有在平衡时效率才高对不平衡的二叉树，查找来说基本没有优势，还不如链表！
不平衡时调整根节点
对于二叉树来说，原理比较简单，剩下的顶多就是编程的问题，比较好解决。
到此，我的 C Primer Plus 这本书就看完了。第二遍看书，确实扫了一下平时没有注意到的问题，尤其对于我这种知识差、浅学皮毛的人来说。以后差 C Primer Plus 就不再这样系统的看了，就当做工具字典来使用了。
OK，下一步就看看C语言三剑客！
学习啦各位！
