文档介绍：-
. z.
数据构造与算法
第一节 数据构造及算法概述
一、数据构造
【要点】
。
。
右图前序遍历序列为ABCDEFIGJH。
后序遍历森林：
假设森林非空，则:
①后序遍历森林中第一棵树的根结点的各子树所构成的森林。
-
. z.
②访问第一棵树的根结点。
③后序遍历除第一棵树外其他树构成的森林。
右图后序遍历序列为BDCAIFJGHE。
二、二叉树
〔一〕根本概念
二叉树是n〔n≥0〕个结点的有限集，它可以是空集〔n=0〕，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。
二叉树的性质
-1个结点〔i≥1〕。
-1个结点〔k≥1〕。
，假设它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1。
深度为k〔k≥1〕且有2k-1个结点的二叉树称为满二叉树。
如果在一棵深度为k〔k≥1〕的满二叉树上删去第k层上最右边的连续j〔0≤j<2k-1〕个结点，就得到一棵深度为k的完全二叉树。满二叉树也是完全二叉树。
〔二〕二叉树的遍历
假设需遍历的二叉树为空，执行空操作；否则，依次执行以下操作：
〔1〕访问根结点。
〔2〕先根遍历左子树。
〔3〕先根遍历右子树。
右图的遍历序列为：ABDGCEF
假设需遍历的二叉树为空,执行空操作；否则，依次执行以下操作：
〔1〕中根遍历左子树。
〔2〕访问根结点。
〔3〕中根遍历右子树。
右图的遍历序列为：DGBAECF
-
. z.
假设需遍历的二叉树为空，执行空操作；否则，依次执行以下操作：
〔1〕后根遍历左子树。
〔2〕后根遍历右子树。
〔3〕访问根结点。
右图的遍历序列为：GDBEFCA
【要点】
树和二叉树的概念和他们的各种遍历方法。
第六节 图
一、图的根本概念
在树形构造中，节点间具有分支层次关系，每一层上的节点只能和上一层中的至多一个节点相关，但可能和下一层的多个节点相关。
在图状构造中，任意两个节点之间都可能相关。
有序偶对用尖括号括起来；无序偶对用圆括号括起来。〔*,y〕与〔y,*〕被认为是同一条边，但<*,y>与<y,*>则是不同的两条弧。
图的边或弧附带数值，这种数值叫权。
【要点】
一个具有n个顶点的无向完全图的边数为n〔n-1〕/2。一个具有n个顶点的有向完全图的弧数为n〔n-1〕。
二、图的存储构造
图的两种存储构造：邻接矩阵表示法和邻接表表示法。
图的遍历包括深度优先遍历和广度优先遍历两种方法。
第七节 查找
一、查找的根本概念
查