算法|数据结构与算法-补充知识（2）算法

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

二叉树的公式：度0结点=度2结点+1
2.满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
3.满二叉树和完全二叉树，可以顺序存储，但仍为非线性。
4..度1结点，即只有一个叶子的结点。
度1结点为0 ，即叶子为双数。
度1结点为1 ，即叶子为单数。
5.两个指针域的链表，可以是二叉链表，或者双向链表。
6.二叉树遍历
前序=中序，二叉树只有右子树，左子树为空，深度=结点数。
中序=后序，二叉树只有左子树，右子树为空，深度=结点数。
7.前序左子树和中序左子树相反，说明根=左，左子树结点依次位于前一结点的左子树上。
前序右子树和中序右子树相同，说明根=右，右子树结点依次位于前一结点的右子树上。
8.有序线性表，元素按非递减排列，从小到大，相邻元素可以相等。
9.平均情况比较次数
顺序查找（1+n）/2
【算法|数据结构与算法-补充知识（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.选择类排序
简单选择排序：依次选最小
堆排序：根结点与左右子树比较。