数据结构与算法（三）软件设计(十九)

二叉树、队列、栈、广义表（二）数据结构与算法（十八）

一、线索二叉树

以前序线索二叉树为例：

他遍历的流程是根、左子树、右子树，A BDEH CFGI

D的前一个结点是B，所以绿线标记。

D的下一个结点时E，所以红线标记。

二、平衡二叉树

1、任意结点的左右子树深度想差不超过1。

2、每个结点的平衡度只能为-1,0,1

三、图

左图为无向图，线没有箭头，可以从1到2也可从2到1。

右图为有向图，箭头指向哪代表只能到哪。

每个顶点之间都有一条边相联就叫，有向完全图 和 无向完全图。

图的存储 可以用 邻接矩阵 和 邻接表。

邻接矩阵如何画，则是看顶点，顶点有五个，所以矩阵是5*5。

横向看：

第一个数是1-1 因为自己指向自己，所以是0。

第二个数是1-1 因为1指向2有一条线，所以是1。

第三个数同理是1。

第四个数是1-4,因为如图1到4没有线，所以是0。

第六个数（也就是第二排第一个数）是2-1，因为2指向1有一个线，所以是1。

...

从图可以看到，他们是有对称性，所以可以只存上三角或者下三角。

图的遍历：

深度优化遍历：首先从顶点出发V，依次搜索任意一个邻接点，继续从邻接点出发。

广度优化遍历：首先从顶点出发V，依次搜索任意一个邻接点，继续找V的邻接点，这样遍历。

邻接表：

V1与v2隔着6个，所以有个2、6

与v4隔着1个，所以有个4、1

与v6隔着50个，所以有个6、50

普里姆算法：选一个顶点，每次找到顶点最小的边，直到所有的点都包含，这就是生成的最小树。（注意一定不能形成环）

克鲁斯卡算法：不选择顶点，每次选择最小的边，一直到所有顶点连接起来。（注意一定不能形成环）

四、算法复杂度

时间复杂度 和 空间复杂度

O（1）<O(log2n) <O(n)<O(nlog2n)<O(n的2次方)<O(n的3次方)<O(2的n次方)

I=0，时间复杂度就是O（1）。

当有一个循环，循环的大小是n，这时候时间复杂度就是O（n）。

当有嵌套循环，第一层循环是n，第二层循环还是到n，第三层循环还是到n，这时候复杂度分别就是O(n),O(n的2次方),O(n的3次方)

平衡树很高的排序二叉树，这时候复杂度就是O（log2n）

空间复杂度 指整个处理过程中所消耗临时的内存是多少。

五、顺序查找

顺序查找的复杂度就是算他的平均值：(n+1)/2

所以顺序查找的时间复杂度是O（n）

因为效率不高，所以出现了二分查找法。

首先必须是有序排列。

1、3、9、12、13、20、31、42

我们从上面数字找到31

1、先找到中间值mid = (max+1)/2。（max表示最大下标），所以(1+8)/2 = 4,找到12

2、因为12<20，所以这时候(4+max)/2 = 6，找到了下标对应的20。

3、这时候20<31，再(6+max)/2 = 7，这时候就找到了31。

所以二分查找就算比较次数最多也是（log2n）+1次找到值。

所以二分查找时间复杂度为O（log2n）

散列表冲突解决办法？

散列表会设计一个函数hash，它以关键字为变量，关键字的存储地址为因变量，将关键字映射到一个有限的，地址连续的T[0...n-1](n<<m)中，这个区间就是散列表。散列表用到的转换函数，叫做散列函数。

当hash函数通过key值算的出现相同值怎么解决冲突呢？

通过 线性探测法 和 伪随机数法。

为了效率高，必须让冲突尽可能的小，整体空间取大，冲突几率也可以变小。