第九章 树
第十章 堆和优先队列
第十一章 图
第九章 树
树的基本概念与前几本书都没有什么差别，所以基本术语就不再记录了
该书有好多易懂的图，看图一眼就懂了
最常用表示图的方法是采用邻接表表示有向图。
#ifndef bitree_h
#define bitree_h
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct BiTreeNode_{
void *data;
struct BiTreeNode_ *left;
struct BiTreeNode_ *right;
}BiTreeNode;
typedef struct BiTree_{
//结点个数
int size;
//预留的
int (*compare)(const void *key1,const void *key2);
//析构函数
void (*destroy)(void *data);
//指向根结点的指针
BiTreeNode *root;
}BiTree;
void bitree_init(BiTree *tree,void(*destroy)(void *data));
void bitree_destroy(BiTree *tree);
int bitree_ins_left(BiTree *tree,BiTreeNode *node,const void *data);
int bitree_ins_right(BiTree *tree,BiTreeNode *node,const void *data);
void bitree_rem_left(BiTree *tree,BiTreeNode *node);
void bitree_rem_right(BiTree *tree,BiTreeNode *node);
//将两棵二叉树合并为单棵二叉树
int bitree_merge(BiTree *merge,BiTree *left,BiTree *right,const void *data);
#define bitree_size(tree) ((tree)->size)
#define bitree_root(tree) ((tree)->root)
#define bitree_is_eob(node) ((node)==NULL)
#define bitree_is_leaf(node) ((node)->left==NULL && (node)->right==NULL)
#define bitree_data(node) ((node)->data)
#define bitree_left(node) ((node)->left)
#define bitree_rihgt(node) ((node)->rihgt)
#endif /* bitree_h */
#include "bitree.h"
void bitree_init(BiTree *tree,void(*destroy)(void *data))
{
tree->size=0;
tree->destroy = destroy;
tree->root = NULL;
return;
}
void bitree_destroy(BiTree *tree)
{
bitree_rem_left(tree, NULL);
memset(tree,0,sizeof(BiTree));
return;
}
int bitree_ins_left(BiTree *tree,BiTreeNode *node,const void *data)
{
BiTreeNode *new_node,**position;
//插入根结点
if (node==NULL)
{
if (bitree_size(tree) > 0) {
return -1;
}
position = &tree->root;
}else{
if (bitree_left(node) != NULL) {
return -1;
}
position = &node->left;
}
if ((new_node = (BiTreeNode *)malloc(sizeof(BiTreeNode))) == NULL){
return -1;
}
new_node->data = (void *)data;
new_node->left = NULL;
new_node->right = NULL;
*position = new_node;
tree->size++;
return 0;
}
//实现与上面基本相同
int bitree_ins_right(BiTree *tree,BiTreeNode *node,const void *data)
{
BiTreeNode *new_node,**position;
//插入根结点
if (node==NULL)
{
if (bitree_size(tree) > 0) {
return -1;
}
position = &tree->root;
}else{
if (bitree_left(node) != NULL) {
return -1;
}
position = &node->right;
}
if ((new_node = (BiTreeNode *)malloc(sizeof(BiTreeNode))) == NULL){
return -1;
}
new_node->data = (void *)data;
new_node->left = NULL;
new_node->right = NULL;
*position = new_node;
tree->size++;
return 0;
}
void bitree_rem_left(BiTree *tree,BiTreeNode *node)
{
BiTreeNode **position;
if (bitree_size(tree) == 0){
return;
}
if (node==NULL) {
position = &tree->root;
}else{
position = &node->left;
}
if (*position != NULL)
{
bitree_rem_left(tree, *position);
bitree_rem_right(tree, *position);
if (tree->destroy != NULL)
{
tree->destroy((*position)->data);
}
free(*position);
*position = NULL;
tree->size--;
}
return;
}
//实现与上面基本相同，就是把左换成右
void bitree_rem_right(BiTree *tree,BiTreeNode *node)
{
BiTreeNode **position;
if (bitree_size(tree) == 0){
return;
}
if (node==NULL) {
position = &tree->root;
}else{
position = &node->right;
}
if (*position != NULL)
{
bitree_rem_left(tree, *position);
bitree_rem_right(tree, *position);
if (tree->destroy != NULL)
{
tree->destroy((*position)->data);
}
free(*position);
*position = NULL;
tree->size--;
}
return;
}
//将两棵二叉树合并为单棵二叉树
int bitree_merge(BiTree *merge,BiTree *left,BiTree *right,const void *data)
{
bitree_init(merge, left->destroy);
if (bitree_ins_left(merge, NULL, data) != 0)
{
bitree_destroy(merge);
return -1;
}
bitree_root(merge)->left = bitree_root(left);
bitree_root(merge)->right = bitree_root(right);
merge->size = merge->size + bitree_size(left) + bitree_size(right);
left->root = NULL;
left->size = 0;
right->root = NULL;
right->size = 0;
return 0;
}
树的周游算法
先序遍历,中序遍历,后序遍历,层序遍历
#include "traverse.h"
#include "list.h"
#include "bitree.h"
//前序
int preorderTraverse(const BiTreeNode *node,List *list)
{
if (!bitree_is_eob(node))
{
if (list_ins_next(list, list_tail(list), bitree_data(node)) != 0)
{
return -1;
}
if (!bitree_is_eob(bitree_left(node)))
{
if (preorderTraverse(bitree_left(node), list) != 0)
{
return -1;
}
if (!bitree_is_eob(bitree_right(node)))
{
if (preorderTraverse(bitree_right(node), list) != 0)
{
return -1;
}
}
}
}
return 0;
}
//中序
int inorderTraverse(const BiTreeNode *node,List *list)
{
if (!bitree_is_eob(node))
{
if (!bitree_is_eob(bitree_left(node)))
{
if (inorderTraverse(bitree_left(node), list) != 0)
{
return -1;
}
}
if (list_ins_next(list, list_tail(list), bitree_data(node)) != 0)
{
return -1;
}
if (!bitree_is_eob(bitree_right(node)))
{
if (inorderTraverse(bitree_right(node), list) != 0)
{
return -1;
}
}
}
return 0;
}
//后序
int postorderTraverse(const BiTreeNode *node,List *list)
{
if (!bitree_is_eob(node))
{
if (!bitree_is_eob(bitree_left(node)))
{
if (postorderTraverse(bitree_left(node), list) != 0)
{
return -1;
}
}
if (!bitree_is_eob(bitree_right(node)))
{
if (postorderTraverse(bitree_right(node), list) != 0)
{
return -1;
}
}
if (list_ins_next(list, list_tail(list), bitree_data(node)) != 0)
{
return -1;
}
}
return 0;
}
树的平衡
在结点加入下一层之前必须保证本层结点满额，保证树的高度尽可能短
如果一棵平衡树最后一层的所有叶子结点都在最靠左边的位置上，则称树为左平衡的。
这本书也用表达式的处理来�讲解二叉树
二叉搜索树
由二叉树组成的专用于查找和搜索目的的一种数据结构。
从根结点开始一层一层往下查找，当遇到一个比目标结点值大的结点时，顺着该结点的左子树继续查找；如果遇到的结点值小于目标结点，则顺着该结点的右子树继续查找。
但是，只有当二叉搜索树保持平衡时查找效率才会高，所以出现了AVL树和红黑树。
AVL树
一种特殊类型的二叉树，每个结点都保存一份额外的信息：结点的平衡因子（右子树高度减去左子树高度的结果）
一棵子树的根结点的平衡因子就代表该子树的平衡性
如果任何平衡因子变为了+-2，就必须重新平衡这棵树，称为旋转。
AVL树的旋转
旋转用来重新平衡AVL树的某个部分，旋转过后，旋转子树中的所有结点的平衡因子都为+1，-1，0
有四种：LL、LR、RR、RL（right，left）
这四种分别表示当插入的元素x在A树的左子树的左子树上；在A树的左子树的右子树上；在A树的右子树的右子树上；在A树的右子树的左子树上，平衡这棵树要进行的操作。
问与答：
1、一些树除了有从父结点指向子结点的正常指针外，还有从子结点指向父结点的指针，有的兄弟结点之间也有相互关联的指针。为什么？
维护附加的指针为遍历树时提供了更加灵活的方式。子结点指向父结点的指针可以自下而上遍历，兄弟结点之间的指针可以不必访问父结点。
2、在bitree_rem_left与bitree_rem_right中，为什么要采用后序遍历的方式来移除子树？
因为子树必须在其父结点之前就被全部移除
3、在二叉搜索树中我们如何找到最小的结点？在最坏的情况下，在非平衡和平衡二叉搜索树中该操作的时间复杂度是多少？如何在二叉搜索树中找到最大的结点？时间复杂度？
二叉搜索树中最小结点是最左边的那个叶子结点。从根结点开始通过左指针逐层下降，直到边缘。最坏情况为当只有一个单独的左分支时，O(n)。平均为O(lgn)。
最大结点是最右边的那个叶子结点。时间复杂度一样。
4、何时应该选择使用分支因子相对较大的树而不是二叉树呢？
对于给定的结点个数，分支因子大能够保持这棵树的高度较低，也就能使树能够保持相对的平衡性。
在对树的高度敏感的应用中，采用分支因子较大的树。在内存中的性能并没有显著提升，但在速度相对较慢的辅助存储空间（闪存）内执行查找操作时，在性能上有明显的区别。
二叉树通常用于内存中查找操作。
5、在一棵二叉搜索树中，某结点的后继结点是指x之后的下一个最大结点。
如24、39、41、55、87、92中，41的后继是55。如何在二叉搜索树中找到某个结点的后继结点？时间复杂度？
首先要定位到x。然后移动到x的右子结点，从这个结点开始不断通过左指针访问下层的左子结点，直到到达分支的边缘。这条分支边缘位置上的结点即后继结点。为O(lgn)。
6、在二叉搜索树中插入一个结点，按照一条特定的路径找到一个合适的位置作为插入点。随着越来越多的结点插入树中，最终，某个值将不再适合插入某区域中了。所以树会失去平衡然后必须进行旋转操作。
总之一个原则：左子树结点必须小于该结点，右子树结点必须大于该结点。
第十章 堆和优先队列
堆：一棵二叉树，分为大顶堆和小顶堆。左平衡的，从左至右增长。
大顶堆根结点是树中最大的结点，每个子结点存储的值比父结点的值小。
小顶堆根结点是树中最小的结点，每个子结点存储的值比父结点的值大。
#ifndef heap_h
#define heap_h
typedef struct Heap_{
int size;
int (*compare)(const void *key1,const void *key2);
void (*destroy)(void *data);
void **tree;
}Heap;
#include <stdio.h>
void heap_init(Heap *heap,int(*compare)(const void *key1,const void *key2),void(*destroy)(void *data));
void heap_destroy(Heap *heap);
//插入新结点
//注意要重新排序
int heap_insert(Heap *heap,const void *data);
//释放堆顶部结点
//删除顶结点后，把最后一个结点放到顶部然后重新排序
int heap_extract(Heap *heap,void **data);
#define heap_size(heap) ((heap)->size)
#endif /* heap_h */
#include "heap.h"
#include <stdlib.h>
#include <string.h>
#define heap_parent(npos) ((int)(((npos)-1)/2))
#define heap_left(npos) (((npos)*2)+1)
#define heap_right(npos) (((npos)*2)+2)
void heap_init(Heap *heap,int(*compare)(const void *key1,const void *key2),void(*destroy)(void *data))
{
heap->size = 0;
heap->compare = compare;
heap->destroy = destroy;
heap->tree = NULL;
return;
}
void heap_destroy(Heap *heap)
{
if (heap->destroy != NULL)
{
for (int i=0; i<heap_size(heap); i++)
{
heap_destroy(heap->tree[i]);
}
}
free(heap->tree);//释放内存
memset(heap, 0, sizeof(Heap));//清空heap
return;
}
int heap_insert(Heap *heap,const void *data)
{
void *temp;
int ipos,ppos;
if ((temp = (void **)realloc(heap->tree, (heap_size(heap)+1)*sizeof(void *))) == NULL)
{
return -1;
}
else
{
heap->tree = temp;
}
heap->tree[heap_size(heap)] = (void *)data;
ipos = heap_size(heap);
ppos = heap_parent(ipos);
while (ipos>0 && heap->compare(heap->tree[ppos],heap->tree[ipos]) < 0)
{
//子结点与父结点交换
temp = heap->tree[ppos];
heap->tree[ppos] = heap->tree[ipos];
heap->tree[ipos] = temp;
//向上移动
ipos = ppos;
ppos = heap_parent(ipos);
}
heap->size++;
return 0;
}
int heap_extract(Heap *heap,void **data)
{
void *save,*temp;
int ipos,lpos,rpos,mpos;
if (heap_size(heap) == 0)
{
return -1;
}
*data = heap->tree[0];
save = heap->tree[heap_size(heap)-1];
if (heap_size(heap)-1 > 0)
{
if ((temp = (void **)realloc(heap->tree, (heap_size(heap)-1)*sizeof(void *))) == NULL)
{
return -1;
}
else
{
heap->tree = temp;
}
heap->size--;
}
else
{
free(heap->tree);
heap->tree = NULL;
heap->size = 0;
return 0;
}
//把最后一个元素挪到顶部
heap->tree[0] = save;
//重新堆化树
ipos = 0;
lpos = heap_left(ipos);
rpos = heap_right(ipos);
while (1)
{
lpos = heap_left(ipos);
rpos = heap_right(ipos);
if (lpos < heap_size(heap) && heap->compare(heap->tree[lpos],heap->tree[ipos]) > 0)
{
mpos = lpos;
}
else
{
mpos = ipos;
}
if (rpos < heap_size(heap) && heap->compare(heap->tree[rpos],heap->tree[mpos]) > 0)
{
mpos = rpos;
}
if (mpos == ipos)
{
break;
}
else
{
//交换当前结点与选择的子结点
temp = heap->tree[mpos];
heap->tree[mpos] = heap->tree[ipos];
heap->tree[ipos] = temp;
ipos = mpos;
}
}
return 0;
}
优先队列：将数据按照优先级顺序排列。
作者是用一个局部有序的堆来实现的。
#ifndef pqueue_h
#define pqueue_h
#include <stdio.h>
#include "heap.h"
typedef Heap PQueue;
#define pqueue_init heap_init
#define pqueue_insert heap_insert
//从优先队列中提取优先队列顶部的元素
#define pqueue_extract heap_extract
//获取优先队列中优先级最高元素
#define pqueue_peek(pqueue) ((pqueue)->tree == NULL ? NULL : (pqueue)->tree[0])
#define pqueue_size heap_size
#endif /* pqueue_h */
优先队列的例子：包裹分拣
快递公司根据包裹的紧急程度、服务类型，将快递按照优先级排序。
问与答：
1、每次向一个堆中插入元素都要重新排序，时间复杂度有点高，是否有其他办法构建一个堆，降低复杂度？
避免重复调用insert函数，不断调整一个结点数组，将结点往树的根部递推。首先调整(n/2)-1的树，再调整(n/2)-2的树，直到调整根结点处于0的树
2、左平衡二叉树�特别适合存储于数组中，为什么不是对所有的二叉树都成立？
对于n是树中结点的个数，因为在位置0和n-1之间肯定会用到结点，空间利用率高，如果出现个右结点，数组中位置会出现空
3、如果用优先队列来存放已经设定好顺序的任务，如果系统不断处理大量高优先级的任务，可能会产生什么问题？
低优先级的元素可能永远都没机会排到队列的顶部，导致“饿死”。
采取机制提高任务等级，比如随着任务在队列中待的时间变得越来越长增加。
第十一章 图
图由顶点和边组成，顶点代表对象，边建立起对象之间的关系ADG
G=(V,E)，V代表顶点的集合，E代表关系的集合
#ifndef graph_h
#define graph_h
#include <stdio.h>
#include "list.h"
#include "set.h"
//结点
typedef struct AdjList_{
void *vertex;
Set adjacent;
}AdjList;
typedef struct Graph_{
int vcount;
int ecount;
int (*match)(const void *key1,const void *key2);
void (*destroy)(void *data);
List adjlists;
}Graph;
typedef enum VertexColor_ {
white,gray,black
}VertexColor;
void graph_init(Graph *graph,int (*match)(const void *key1,const void *key2),void (*destroy)(void *data));
void graph_destroy(Graph *graph);
//将一个顶点插入图中
int graph_ins_vertex(Graph *graph,const void *data);
//将一条边插入图中
int graph_ins_edge(Graph *graph,const void *data1,const void *data2);
int graph_rem_vertex(Graph *graph,void **data);
int graph_rem_edge(Graph *graph,void *data1,void **data2);
//取出graph中由data指定的顶点的邻接表
int graph_adjlist(const Graph *graph,const void *data,AdjList **adjlist);
//判断由data2所指定的顶点是否与graph中由data1所指定的顶点邻接
int graph_is_adjacent(const Graph *graph,const void *data1,const void *data2);
#define graph_adjlists(graph) ((graph)->adjlists)
#define graph_vcount(graph) ((graph)->vcount)
#define graph_ecount(graph) ((graph)->ecount)
#endif /* graph_h */
#include "graph.h"
#include <stdlib.h>
#include <string.h>
void graph_init(Graph *graph,int (*match)(const void *key1,const void *key2),void (*destroy)(void *data))
{
graph->vcount = 0;
graph->ecount = 0;
graph->match = match;
graph->destroy = destroy;
list_init(&graph->adjlists, NULL);
return;
}
void graph_destroy(Graph *graph)
{
AdjList *adjlist;
//删除每个邻接表结构并摧毁它的邻接表
while (list_size(&graph->adjlists) > 0)
{
if (list_rem_next(&graph->adjlists, NULL, (void **)&adjlist) == 0)
{
set_destroy(&adjlist->adjacent);
if (graph->destroy != NULL)
{
graph->destroy(adjlist->vertex);
}
free(adjlist);
}
}
list_destroy(&graph->adjlists);
memset(graph, 0, sizeof(Graph));
return;
}
int graph_ins_vertex(Graph *graph,const void *data)
{
ListElmt *element;
AdjList *adjlist;
int retval;
//不允许插入重复的顶点
for (element = list_head(&graph->adjlists); element != NULL; element = list_next(element))
{
if (graph->match(data,((AdjList*)list_data(element))->vertex))
{
return 1;
}
}
//插入
if ((adjlist = (AdjList *)malloc(sizeof(AdjList))) == NULL)
{
return -1;
}
adjlist->vertex = (void *)data;
set_init(&adjlist->adjacent, graph->match, NULL);
if ((retval = list_ins_next(&graph->adjlists, list_tail(&graph->adjlists), adjlist)) != 0)
{
return retval;
}
graph->vcount++;
return 0;
}
int graph_ins_edge(Graph *graph,const void *data1,const void *data2)
{
ListElmt *element;
int retval;
//不允许插入两个顶点都不在图上的边
for (element = list_head(&graph->adjlists); element != NULL; element = list_next(element))
{
if (graph->match(data2,((AdjList *)list_data(element))->vertex))
{
break;
}
}
if (element == NULL)
{
return -1;
}
for (element = list_head(&graph->adjlists); element != NULL; element = list_next(element))
{
if (graph->match(data1,((AdjList *)list_data(element)) -> vertex))
{
break;
}
}
if (element == NULL)
{
return -1;
}
//在邻接表第一个顶点后插入第二个顶点
if ((retval = set_insert(&((AdjList *)list_data(element))->adjacent, data2)) != 0)
{
return retval;
}
graph -> ecount++;
return 0;
}
int graph_rem_vertex(Graph *graph,void **data)
{
ListElmt *element,*temp = NULL,*prev;
AdjList *adjlist;
int found;
//遍历每个邻接表和包含的顶点
prev = NULL;
found = 0;
for (element = list_head(&graph->adjlists); element != NULL; element = list_next(element))
{
//不允许删除这个顶点，如果在邻接表中
if (set_is_member(&((AdjList *)list_data(element))->adjacent, *data))
{
return -1;
}
if (graph->match(*data,((AdjList *)list_data(element))->vertex))
{
temp = element;
found = 1;
}
if (!found)
{
prev = element;
}
}
//若果顶点没有找到就返回
if (!found)
{
return -1;
}
//如果邻接表不是空的，不允许删除顶点
if (set_size(&((AdjList *)list_data(temp)) -> adjacent) > 0)
{
return -1;
}
//删除顶点
if (list_rem_next(&graph->adjlists, prev, (void **)&adjlist)!= 0)
{
return -1;
}
*data = adjlist->vertex;
free(adjlist);
graph->vcount--;
return 0;
}
int graph_rem_edge(Graph *graph,void *data1,void **data2)
{
ListElmt *element;
//找到第一个顶点的邻接表
for (element = list_head(&graph->adjlists); element != NULL; element = list_next(element))
{
if (graph->match(data1,((AdjList *)list_data(element))->vertex))
{
break;
}
}
if (element == NULL)
{
return -1;
}
//删除第一个顶点邻接表的第二个顶点
if (set_remove(&((AdjList *)list_data(element))->adjacent, data2) != 0)
{
return -1;
}
graph->ecount--;
return 0;
}
int graph_adjlist(const Graph *graph,const void *data,AdjList **adjlist)
{
ListElmt *element,*prev;
//定位顶点的邻接表
prev = NULL;
for (element = list_head(&graph->adjlists); element != NULL; element = list_next(element))
{
if (graph->match(data,((AdjList *)list_data(element))->vertex))
{
break;
}
prev = element;
}
if (element == NULL)
{
return -1;
}
*adjlist = list_data(element);
return 0;
}
int graph_is_adjacent(const Graph *graph,const void *data1,const void *data2)
{
ListElmt *element,*prev;
prev = NULL;
//定位第一个顶点的邻接表
for (element = list_head(&graph->adjlists); element != NULL; element = list_next(element))
{
if (graph->match(data1,((AdjList *)list_data(element))->vertex))
{
break;
}
prev = element;
}
if (element == NULL)
{
return 0;
}
return set_is_member(&((AdjList *)list_data(element))->adjacent, data2);
}
广度优先搜索，广度优先树。
深度优先搜索，深度优先树。
图的例子
1、计算网络跳数
确定在互联网中从一个结点到另一个结点的最佳路径。采用广度优先搜索来帮助确定结点间的最小跳数。
2、拓扑排序
根据各种事件间的依赖关系来确定一种可接受的执行顺序。
比如执行完a才能执行b，执行完b才能执行c
通过对事件进行深度优先搜索，确定出一种可接受的顺序。
问与答：
1、本章的图中，为什么采用链表来实现邻接表结构链表，而邻接表本身却采用集合的方式来实现？
用链表，能够动态的扩展和收缩。用集合，因为邻接表包含的顶点是无序的，针对邻接表的主要操作非常适合。
这里邻接表结构链表的主要操作时找出特定顶点的邻接表，链表比集合更适合。
先说数据类型的优点，然后是否适合当前问题即可。
2、假设用图对互联网建模，我们确定图包含一个关结点，会有什么影响？
关结点代表一个单点故障源，如果位于关结点的系统失效，其他结点上的系统就无法互相通信了。因此在设计时就要保证没有关结点，通过放置冗余结点来解决。
3、用图对航线结构进行建模...？
广度优先搜索
4、模拟十字路口的交通灯系统？
有向图
网友评论