今天杂事较多，学习时间比较分散，所以效率不是很高，看的内容也较少，总体来看，这四天把数据结构的内容看了过半，还剩图、查找和排序三章，争取接下来三天内把数据结构的内容结束掉。下面是今天的学习内容。

树（tree）

    1.前序遍历算法：与二叉树的定义一样采用递归形式。

    2.中序和后序遍历与前序类似用递归实现；前、中、后是指单次递归算法中访问根节点的顺序

    3.已知（前+中）or（后+中）序遍历序列可以唯一确定一颗二叉树；单已知 前+后 则不能。

   4.扩展二叉树：将每个结点的空孩子指针引出一个虚结点；扩展二叉树只需一个遍历序列就可确定一棵二叉树。

    5.线索：指向前驱和后继的指针；线索链表：加上线索的二叉链表；相应的二叉树称为线索二叉树；标志域：ltag和rtag：表lchild和rchild指针是否指向前驱和后继的布尔标志域

    6.结点结构： lchild+ltag+data+rtag+rchild 。

    7.中序遍历线索化的递归函数的实现：若某结点的左指针为空，则令p->lchild = pre；若p的前驱pre没有右孩子，则令pre->rchild = p。

    8.线索化之后对二叉树进行遍历，相当于操作一个双向链表结构。要在根之前添加一个头结点，与根节点和遍历的最后一个节点通过头结点的左右孩子指针相连。

    9.树、森林和二叉树的转换：通过加线去线处理；转化后，树和森林的遍历完全可以套用二叉树的遍历方法实现。

    10.赫夫曼树和赫夫曼编码

      树的路径长度就是从树根到每一节点的路径长度之和；带权路径长度WPL最小的二叉树叫做赫夫曼树（最优二叉树）。

      赫夫曼编码在本科“信息论与编码”课程中学过，因此不缀述。核心思想是符号的使用频率越大，对其编码的长度越短。

图（graph）

    1.定义：由顶点的有穷非空集合V 和 边的集合E构成，表示为 G(V,E)。

    2.各种数据结构内数据元素之间的关系：线性表的元素是线性关系；树的结点是层次关系；图的顶点（Vertex）是边的（网络状的）关系。

    3.各种图的相关术语

      无向边（小括号）和有向边（尖括号）（弧arc）；无向图和有向图；若A指向B，则A为弧尾，B为弧头；简单图；无向完全图：任意两个顶点之间都有边，n个顶点对应n*（n-1）/2条边；有向完全图：n个顶点对应n*（n-1）条边，稀疏图和稠密图；

      网：带权的图；无向图顶点的度：与顶点相连的边的条数，实际的边数是各顶点度数和的一半；有向图顶点的度：入度+出度，实际的弧数=顶点入度数=顶点出度和；路径长度：路径上边或弧的数目；简单路径。

      连通图：任意两个顶点都是连通的；连通分量：无向图中极大连通子图；强连通图：有向图中任意的顶点对都存在双向的路径；强连通分量：有向图中的极大强连通子图；连通图的生成树：连通子图，且含全部的n个顶点，恰含n-1条边；有向树：恰有一个顶点入度为0的有向图；其余顶点入度为1；有向图的有向森林：由若干棵有向树构成的有向。