5、 循环队列
typedef struct {
DataType elem[MAXSIZE]; int front, rear; // 队头、队尾位置 } SqQueue;
·循环队列判断队空的条件为 front=rear
循环队列判断队满的条件为 （rear+1）%m=front
在一个循环队列中删除元素时，首先需要后移队首指针。
6、栈与队列比较：都是线形结构，栈的操作LIFO（后进先出），队列操
作FIFO（先进先出）。
四、 树和二叉树
1. 树的定义
树（Tree）：是 n（n≥0）个有限数据元素的集合。 在任意一棵非空树T中：
（1）有且仅有一个特定的称为树根（Root）的结点，根结点无前趋结点； （2）当n>1时，除根结点之外的其余结点被分成m(m>0)个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤ i ≤m）本身又是一棵树，并且称为根的子树。
2. 基本术语：
结点的度数：结点的非空子树（即后缀）个数叫作结点的度数
树叶、分支结点：左（右）子树均为空二叉树的结点称作树叶否则称作分支结点。
结点的层数：规定根的层数是0，其余结点的层数等于其父结点的层数加1 孩子和双亲： 树的深度：
树的度数：树中度数最大的结点度数叫作树的度数 树林：是由零个或多个不相交的树所组成的集合。
3. 二叉树性质：
1) 二叉树的第i层上至多有2i-1个结点。 2) 深度为k的二叉树至多有2k-1个结点。 满二叉树：深度为k，有2k-1个结点。
完全二叉树：给满二叉树的结点编号，从上至下，从左至右，n个结点的完全二叉树中结点在对应满二叉树中的编号正好是从1到n。
3) 叶子结点n0，度为2的结点为n2，则n0 = n2+1。 考虑结点个数：n = n0 + n1 + n2 考虑分支个数：n-1 = 2n2 + n1 可得n0 = n2+1
4) n个结点的完全二叉树深度为?logn??1。
5) n个结点的完全二叉树，结点按层次编号
有： i的双亲是?n/2?，如果i = 1时为根（无双亲）； i的左孩子是2i，如果2i>n，则无左孩子；
i的右孩子是2i + 1，如果2i + 1>n则无右孩子。
4. 二叉树的存储结构
·顺序存储结构
用数组、编号i的结点存放在[i-1]处。适合于存储完全二叉树。 ·链式存储结构 二叉链表：
typedef struct BTNode { DataType data;
struct BTNode *lchild, *rchild; } BTNode, *BinTree; 三叉链表：
typedef struct BTNode { DataType data;
struct BTNode *lchild, *rchild, *parent; } BTNode, *BinTree;
lchild data parent rchild lchild data rchild 在链式存储结构中，含有n个结点的二叉链表有n+1个空链域。
5. 遍历二叉树（先序DLR、中序LDR、后序LRD）方法与C语言描述
由二叉树的递归定义可知，一棵二叉树由根结点（D）、根结点的左子树（L）和根结点的右子树（R）三部分组成。因此，只要依次遍历这三部分，就可以遍历整个二叉树。一般有三种方法：先序(前序)遍历DLR（根左右）、中序遍历LDR（左根右）、 后序遍历LRD（左右根）。
1．先序遍历（DLR）的递归过程void Preorder(BT*T) // 先序遍历二叉树BT{ if (T= =NULL) return; // 递归调用的结束条件{ printf(T->data); // 输出结点的数据域Preorder(T->lchild); // 先序递归遍历左子树Preorder(T->rchild); // 先序递归遍历右子树}}2．中序遍历（LDR）的递归过程void Inorder(BT*T)// 中序遍历二叉树BT{ if (T= =NULL) return; // 递归调用的结束条件{ Inorder(T->lchild); // 中序递归遍历左子树printf(T->data); // 输出结点的数据域Inorder(T->rchild); // 中序递归遍历右子树}3．后序遍历（LRD）的递归过程}void Postorder(BT*T) // 后序遍历二叉树BT{ if (T= =NULL) return; // 递归调用的结束条件{ Postorder(T->lchild); // 后序递归遍历左子树Postorder(T->rchild); // 后序递归遍历右子树printf(T->data); // 输出结点的数据域}}
6. 线索二叉树
n个结点的二叉链表中有n+1个空指针，可以利用其指向前驱或后继结点，叫线索，同时需附加一个标志，区分是子树还是线索。 lchild ltag data rtag rchild 0/1 0/1 lchild 有左子树，则指向左子树，标志ltag == 0； 没有左子树，可作为前驱线索，标志ltag == 1。 rchild 有右子树，则指向右子树，标志rtag == 0； 没有右子树，可作为后继线索，标志rtag == 1。
7. 树和森林
树的存储结构
双亲表示法，孩子表示法，孩子兄弟表示法。 特点：双亲表示法容易求得双亲，但不容易求得孩子；孩子表示法容易求得孩子，但求双亲麻烦；两者可以结合起来使用。孩子兄弟表示法，容易求得孩子和兄弟，求双亲麻烦，也可以增加指向双亲的指针来解决。
树与二叉树的转换
表 错误！文档中没有指定样式的文字。.1 树和二叉树的对应关系
树 根 第一个孩子 下一个兄弟 树的遍历
对应的二叉树 根 左孩子 右孩子 树的结构：①根，②根的子树。
先根遍历：①②。例：ABCDEFGHIJK。 后根遍历：②①。例：CEDFBHGJKIA。 遍历森林
森林的结构：①第一棵树的根，②第一棵树的根的子树森林，③ 其余树(除第一棵外)组成的森林。
先序遍历：①②③。例：ABCDEFGHIJ。 中序遍历：②①③。例：BDCEAGFIJH。 注：先序遍历森林，相当于依次先根遍历每一棵树；中根遍历森林相当于后根遍历每一棵树。
A B C D E 树的结构划
森林的结构划分
F G H J ① I ② K ② ① B A C D E F G I H J ③ 遍历树、森林与遍历二叉树的关系
遍历树、森林和二叉树的关系 树 先根遍历 后根遍历
森林 先序遍历 中序遍历
二叉树 先序遍历 中序遍历
8. 哈夫曼树：叶子结点带有权值的最小带权路径长度的最优二叉树
构造赫夫曼树
每次取两个最小的树组成二叉树