数据结构与算法(上)(300分钟搞定数据结构与算法)

导语：数据结构与算法-补充知识（2）

1.树的公式：总结点=总度+1

二叉树的公式：度0结点=度2结点+1

2.满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

3.满二叉树和完全二叉树，可以顺序存储，但仍为非线性。

4..度1结点，即只有一个叶子的结点。

度1结点为0，即叶子为双数。

度1结点为1，即叶子为单数。

5.两个指针域的链表，可以是二叉链表，或者双向链表。

6.二叉树遍历

前序=中序，二叉树只有右子树，左子树为空，深度=结点数。

中序=后序，二叉树只有左子树，右子树为空，深度=结点数。

7.前序左子树和中序左子树相反，说明根=左，左子树结点依次位于前一结点的左子树上。

前序右子树和中序右子树相同，说明根=右，右子树结点依次位于前一结点的右子树上。

8.有序线性表，元素按非递减排列，从小到大，相邻元素可以相等。

9.平均情况比较次数

顺序查找（1+n）/2

10.平均情况可能找到、可能找不到比较次数

顺序查找(1+n)/2+n/2=3n/4

11.最坏情况比较次数

顺序查找：n

查找最大（小）项：n-1

二分法查找：log2^n

堆排序：nlog2^n

冒泡排序法：n(n-1)/2

快速排序法：n(n-1)/2

简单插入排序法：n(n-1)/2

简单选择排序法：n(n-1)/2

希尔排序法：n^r (1＜r＜2)

12.堆定义

同时大

hi≥h2i

hi≥h(2i+1)；

同时小

hi≤h2i

hi≤h(2i+1)。

13.查找

顺序查找：依次查找（无序、链式有序）

二分法查找：对分查找（顺序有序）

14.交换类排序

冒泡排序法：大数下沉，消除一个逆序

快速排序法：线性分割，消除多个逆序

15.插入类排序

简单插入排序：依次插入

希尔排序：子序列插入，消除多个逆序

16.选择类排序

简单选择排序：依次选最小

堆排序：根结点与左右子树比较。

本文内容由小快整理编辑！