二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。为了统计Apache日志中的访问IP信息，我们采用二叉排序树，主要原因是二叉排序树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树。

一、二叉排序树插入

void insert_data_into_tree(struct tree_node **p, int data)
{
	if(*p == NULL)
	{
		*p = malloc(sizeof(struct tree_node));

		if(*p != NULL)
		{
			(*p)->data = data;
			(*p)->lch = (*p)->rch = NULL;
		}
	}
	else if((*p)->data >= data)
	{
		insert_data_into_tree(&(*p)->lch, data);
	}
	else
	{
		insert_data_into_tree(&(*p)->rch, data);
	}
}

或者

struct tree_node *insert_data_into_tree(struct tree_node *p, int data)
{
	if(p == NULL)
	{
		p = malloc(sizeof(struct tree_node));

		if(p != NULL)
		{
			p->data = data;
			p->lch = p->rch = NULL;
		}
	}
	else if(p->data >= data)
	{
		p->lch = insert_data_into_tree(p->lch, data);
	}
	else
	{
		p->rch = insert_data_into_tree(p->rch, data);
	}

	return p;
}

二、统计代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_LINE_LEN 10240

// 二叉树结点定义
struct tree_node
{
	char *ip;
	int count;
	struct tree_node *lch;
	struct tree_node *rch;
};

// 插入IP数据到二叉排序树中
void insert_data_into_tree(struct tree_node **p, char *ip, int *ip_num)
{
	// 二叉排序树中没有该IP，插入。
	if(*p == NULL)
	{
		*p = malloc(sizeof(struct tree_node));

		if(*p != NULL)
		{
			(*p)->ip = malloc(sizeof(ip) + 1);
			strcpy((*p)->ip, ip);
			(*p)->count = 1;
			(*p)->lch = (*p)->rch = NULL;
			*ip_num = *ip_num + 1;
		}	
	}
	else
	{
		int ret = strcmp((*p)->ip, ip);

		// 二叉排序树中有该IP，将其count加1即可
		if(ret == 0)
		{
			(*p)->count++;
		}
		else if(ret > 0)
		{
			insert_data_into_tree(&(*p)->lch, ip, ip_num);
		}
		else
		{
			insert_data_into_tree(&(*p)->rch, ip, ip_num);
		}
	}
}

// 复制二叉树中的数据到数组中
void print_tree_to_array(struct tree_node *p, struct tree_node *ip_array, int *index)
{
	if(p == NULL) return;
	else
	{
		print_tree_to_array(p->lch, ip_array, index);
		print_tree_to_array(p->rch, ip_array, index);
		ip_array[*index] = *p;
		*index = *index + 1;
		free(p);
	}
}

// 比较函数
int is_greater(const void *p, const void *q)
{
	struct tree_node *a = (struct tree_node *)p;
	struct tree_node *b = (struct tree_node *)q;

	if(a->count < b->count) return 1;
	else if(a->count == b->count) return 0;
	else return -1;
}

int main(void)
{
	char buff[MAX_LINE_LEN];
	int line_num = 0;
	int ip_num = 0;
	struct tree_node *root = NULL;
	FILE *fp = fopen("access_2018-03-29.log", "r");

	while((fgets(buff, MAX_LINE_LEN, fp)) != NULL)
	{
		// 解析IP
		char *ip = strtok(buff, " ");
		// 将解析到的IP插入二叉排序树中
		insert_data_into_tree(&root, ip, &ip_num);
		line_num++;
	}
	fclose(fp);

	// 定义变长数组
	struct tree_node ip_array[ip_num];
	int index = 0;

	// 将二叉排序树中的数据复制到数组中，为排序做准备
	print_tree_to_array(root, ip_array, &index);

	// 快速排序，标准库函数
	qsort(ip_array, ip_num, sizeof(struct tree_node), is_greater);

	// 打印统计结果
	printf("IP统计\n");
	printf("-------------------------------\n");
	printf("访问次数\tIP\n");

	for(int i=0; i<20; i++)
	{
		printf("%d:\t\t%s\n", ip_array[i].count, ip_array[i].ip);
	}

	printf("-------------------------------\n");
	printf("IP总数：\t%d\n", ip_num);
	printf("访问次数：\t%d\n", line_num);

	return 0;
}

三、运行结果

[ycxie@fedora Workspace]$ gcc stat_log.c -o stat_log -Wall
[ycxie@fedora Workspace]$ ./stat_log
IP统计
-------------------------------
访问次数	IP
39580:		116.196.82.133
28216:		123.11.117.71
22028:		106.14.242.113
21915:		112.67.103.4
13640:		47.98.60.66
7929:		222.84.60.132
7341:		61.231.167.236
6326:		106.120.173.135
6281:		117.86.200.253
5804:		1.27.91.109
5157:		183.15.89.217
5093:		112.67.98.122
4927:		183.15.88.121
4606:		27.189.207.44
3369:		27.17.116.5
3308:		43.243.149.93
3108:		89.64.27.45
3058:		14.106.229.143
2823:		43.243.149.10
2791:		112.67.106.55
-------------------------------
IP总数：	36339
访问次数：	1569554