本文是浙江大学mooc课程数据结构的相关整理与笔记。
课程原地址如下：https://www.icourse163.org/learn/ZJU-93001?tid=1459700443#/learn/content?type=detail&id=1235254042
分层次组织在管理上具有更高的效率。
顺序查找算法的时间复杂度为O(n)。
二分查找（Binary Search）
ASL：平均成功查找次数。
树的定义
一棵N个结点的树有N-1条边：除根节点外每个结点都有一条向上的边。
树是保证结点连通的最小的连接方式。
k条边是因为除根节点之外的每个点都有一条向上的边，加上无向上的边的根结点数（m）就是森林的结点总数。
若树有n个结点，若采用A结点的表示与定义方法，则每个结点会有3个指针域，那整棵树就会有3n个指针域。但实际上，树的边只有（n-1）条，这样会造成空间的浪费。
度为2的树的子树没有左右顺序之分。（二叉树与二度树）
边的总数：n0+n2+n1-1=0*n0+1*n1+2*n2
该等式得到：n0=n2+1
树的深度为d，且二叉树只有度为0和2的结点，即若一个结点有子结点，则它一定只有两个子结点。每层的结点数至少为2。第一层只有1个结点，所以结点总数为2d-1。
递归的实现使用了堆栈。
直接使用堆栈如何实现？
中序遍历是第二次遇到某结点的时候将其print，先序是第一次遇到就将其print，后序遍历是第三次遇到某结点就将其print。
层序遍历二叉树遍历的核心问题：二维结构的线性化。
队列实现：遍历从根结点开始，首先将根结点入队，然后开始执行循环：结点出队、访问该结点、其左右儿子入队。
二叉树的表示：用链表，也可以用数组
最方便的用数组表示二叉树，将二叉树按照完全二叉树给结点编号：
判断根结点，在数组中看哪个位置编号未使用。如上图中，B的Left为4，Right为3，A的Right为0，其余值都为-1，则只有位置编号1未使用，则1号对应的结点A为根结点。可以这么理解，0，3，4均有指向其的结点（即父结点），只有1没有，即为根结点。
为了处理方便，将数据以字符的方式读入。
