一、线性表：分类：
1）线性表顺序存储：
2）线性表线性存储：
1）单向链表
2）单向链表（企业链表）
3）循环链表（企业链表单向）
4）解决约瑟夫问题（用单项循环链表）
5）双向链表
6）受限的线性表
1）栈的顺序存储（ stack ）
2）栈的链式存储（ stack ）
3）队列的顺序存储（ queue ）
4）队列的链式存储（ queue ）
5）栈的应用（1.就近匹配，用来测试编码的括号使用规范）
6）栈的应用（2.中缀表达式转后缀表达式）
7）（计算机）基于后缀表达式的计算；
二、树的特点：
1）非线性结构，有 1 个直接前驱，但可能有多个直接后继（1 ：n);
2)树的定义具有递归性，树中还有树。
3）树可以为空，即节点为0。
4.树的一些专业名称
1）节点的度：节点挂接的子树数（即一个节点有几个直接后继就有几度）。
2）节点的层次：即根到该节点的层数（根节点算一层）
3）树的度：所有 节点的度 中的最大值
4）树的深度(或高度）:指所有节点中的最大层数。
5）节点数：一棵树中的所有节点个数（包括根节点）。
6）叶子节点：即终端节点，没有后继。
5 二叉树
1）二叉树的基本特征：（1 ：2）
每个节点最多只有两个子树
左子树和右子树的位置不能颠倒
2）二叉树的性质：
1）在二叉树的第 i 层上，最多只有2^(i-1)个节点。（i > 0）
2）深度为 k 的二叉树，最多只有 2^k -1 个节点。（k>0）
3)对于任何一个二叉树，若度为2 的节点有n2个，则它的叶子数必为 n2+1个。
4）满二叉树：深度为K,有 2^K-1 个节点。特点是：每层都充满了节点。
6.完全二叉树：
1）除最后一层外，每层的节点数都达到了最大值，且最后一层的节点尽力靠左。
2）对于完全二叉树：若从上至下，从左至右编号，则编号为i的节点，其左孩子编号为 2i， 右孩子编号为 2i+1， 双亲的编号为 i/2；（i等于1时，为根除外）。
1）左孩子右兄弟：可以将一颗多叉树转变为二叉树
2）递归遍历（周游）二叉树
3）非递归遍历二叉树（用栈的方法）
4）遍历的三种方法：
1）先序：先根再左再右
2）中序：先左再根再右
3）后序：先左再右再根
5）
1)已知二叉树的"先序"遍历和"后序"遍历序列"不能"唯一地确定这这棵树。
2)已知二叉树的"先序"遍历和"中序"遍历"可以"唯一地确定这这棵树。
1)先根据先序找到根节点，在根据中序确定根节点左右两边的节点
2）再根据先序找到下一个根节点，再根据中序找到根节点左右两边的节点。
3）"中序"、"后序"可以确定一棵树
4)总体结论为：带"中序"的都可以确定一棵树，反之则确定不了
6）三种遍历的特点：
1）先序遍历：可以确定每棵树的根节点。（特点： 它的输出序列中：第一个数为树的总根节点；剩下的子根节点，和中序遍历可以确定）
2）中序遍历：可以确定根节点的左右子树。（它的特点为：输出序列中，根节点两边的为它的左右子树，和先序遍历配合可以确定一棵树）
閱讀更多 技匠志 的文章
