数据结构知识点总结 下载本文

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且非∞的元素个数。 图的深度优先和广度优先都要弄清楚。深度优先为相连访问(注意退回到还有连接结点没有访问过的那个结点上,广度优先为层次访问,先访问的结点其子树也先访问(子树访问无次序,仅对下层访问有影响)

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

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

折半查找算法。