数据结构知识点总结

if (tree) {

counter++;

Numbers(tree->Lsubtree); Numbers(tree->Rsubtree); } }

设二叉树的根节点的指针为tree，每个节点的结构为：

Lsubtree data Rsubtree 试写一算法，用于输出该二叉树中最大的节点值。

算法如下：

max <= 0;

void MaxNode(NODE *tree) {

if (tree) {

if (tree->data > max) max <= tree->data; MaxNode(tree->Lsubtree); MaxNode(tree->Rsubtree); } }

或者：

max <= 0;

void MaxNode(NODE *tree) {

if (tree) {

x <= tree->data;

y <= MaxNode(tree->Lsubtree); z <= MaxNode(tree->Rsubtree); reyurn (max(x，y，z)); } else

return (-∞); }

--------------------------------------------------------------------- 图

设有向图G有n个顶点，m条弧，则其邻接表中链上的节点个数为m 若一无向图是连通的，且其中有n个顶点和e条边，则必满足e≥n-1 有向图强连通分量在有向图G中，如果两个顶点vi,vj间（vi<>vj）有一条从

vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量(strongly connected components)。记主要特征：强联通分量图中两两都可达，也可见下图实例。按照这个定义，得到图G 中的强联通分量共3个： <1,2>,<3,5,6>,<4>

在一个有n（n≥1）个顶点的有向图中，边数最多为n(n-1)

带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中第i列非∞且非O的元素个数有向图中，结点i的入度就是指向 i结点的弧的条数,而邻接矩阵是行数据中非0非无穷元素个数为i的出度，列才为入度

有向图用邻接矩阵表示后，顶点i的出度等于第i行中非0且非∞的元素个数。 图的深度优先和广度优先都要弄清楚。深度优先为相连访问（注意退回到还有连接结点没有访问过的那个结点上，广度优先为层次访问,先访问的结点其子树也先访问（子树访问无次序，仅对下层访问有影响）

广度优先和深度优先遍历序列均可能是不唯一的。

--------------------------------------------------------------------- 查找

折半查找算法。