总结的一些数据结构小公式

文章目录

• 完全无向图和完全有向图公式
• 结点计算公式
• 最小生成树
• 矩阵:

完全无向图和完全有向图公式

将一个具有 n 个顶点 e 条边的无向图存储在邻接矩阵中，则非零元素的个数是 2e。

对于一个具有 n 个顶点 e 条边的有向图存储在邻接矩阵中，则非零元素的个数是 e。

1.完全无向图：n个顶点的完全无向图的边数= n(n-1)/2 2.完全有向图： 完全有向图的边数=n(n-1) 3. 举例1：有10个顶点的无向连通图边的数量最少是（ 9 ）个，最多是（ 45 ）个 4. 举例2：有10个顶点的有向连通图边的数量最少是（ 10 ）个，最多是（ 90 ） 个

1二叉树的第i层，最多有2^i个结点；

2高度为h的二叉树上最多有2^h -1 个结点

3二叉树的叶子结点n0 = 度为2的结点n2+1

4

若对含n个结点的完全二叉树从上到下且从左至右进行0至n-1的编号,则 对完全二叉树中任意一个编号为i的结点,有 1)若i=0,则该结点是二叉树的根,无双亲,否则,编号为l(i-1)/2的结点为 其双亲结点; (2)若2i+1≥n,则该结点无左孩子,否则,编号为2i+1的结点为其左孩子结点 (3)若2i+2≥n,则该结点无右孩子结点,否则,编号为2i+2的结点为其右孩子结

结点计算公式

设只有 1 个结点的二叉树的深度为 1，则深度为 k 的完全二叉树至少有** 2k-1** 个结点,至多有 2k-1 个结点

设 n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有** 2n0-1 **个结点

一棵满二叉树的结点个数为 n，高度为 h，则 n= ** 2^h -1**

有 n 个顶点的无向完全图具有** n(n-1)/2** 条边

完全有向图的边数=n(n-1)

设有一个长度为 n 的顺序表，要删除第 i(0<=i<=n-1)个元素，需移动元素的个数 为 n-i-1。

叶节点 节点的关系:2i+1 2i-1

从 0 开始，自顶向下、自左向右对一棵二叉树进行顺序编号，则编号为 i 的结点，若它存在左、右孩子，则左、右孩子编号分别为____2i+1、2i+2____

默认从1开始则 左右孩子编号分别为:2i,2i+1;

在包含 n 个元素的顺序表中删除一个元素，需要平均移动** (n-1)/2 **个元素

最小生成树

已知一个网的形式如下：

请利用克鲁斯卡尔算法构造该网的最小生成树，绘制每一步构造过程情况。

记忆技巧：一个人玩井口游戏

请利用普里姆(Prim)算法从a点出发构造该网的最小生成树，绘制每一步构造过程情况。

记忆技巧：多个人玩井口游戏

克鲁斯卡尔算法，生成图的最小生成树，步骤：

普里姆(Prim)算法从a点出发构造该网的最小生成树，步骤：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eQygB3u0-1639977657618)(439aaa7b9201942aa0e105216e384caa.png)]

矩阵:

题目：有一个10阶矩阵，他的基地址是GDP，每个元素占用6个空间大小，那么 A（8，9）的起始地址是（GDP+534）,这个10阶共占用的空间大小是（600） 解析：10阶：10m*10n

特殊矩阵-对称矩阵、上三角、下三角:

A(2,3) 对应下标index是多少

2树的遍历 层次遍历(记忆诀窍:想象成一个人爬山) 先跟遍历：先根再左最后右

中根遍历：先左再根最后右

后根遍历：先左再右最后根

4.结点的度：结点的子树的数目 5.树的度：树中最大的结点的度 6.层次：根结点的层是0 7.深度：层次+1 8.高度：叶子结点的高度是0 9.二叉树：树中的度最大值是2 10.满二叉树：除了叶子结点，每个结点都有左右两个孩子