[数据结构与算法] 数据结构4——linuxC(二叉树和排序算法)

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构4——linuxC(二叉树和排序算法) -> 正文阅读

[数据结构与算法]数据结构4——linuxC(二叉树和排序算法)

对于二叉树而言，有如下特性：
1.第i层上，最多有2^(i-1)个节点。
2.高度为k的二叉树，最多有2^k-1个节点。
3.假设叶子数目为n0，度为2的节点数目为n2，则有：n0= n2+1

在这里插入图片描述

1.二叉树的插入

#include <stdio.h>
#include <stdlib.h>
#include "drawtree.h"

// 二叉树数据节点
typedef struct node
{
	int data;	// 数据域
	struct node *lchild;	//左子树指针
	struct node *rchild;	//右子树指针
}node;

//二叉树插入
node *bst_insert(node *root, int new_data);
// 前序遍历: 根节点 - 左子树 - 右子树
void pre_traval(node *root);
// 中序遍历：左子树 - 根节点 - 右子树
void mid_traval(node *root);
// 后序遍历：左子树 - 右子树 - 根节点
void lst_traval(node *root);

int main()
{
	// 1.初始化空二叉树
	node *root = NULL;

	// 插入数据
	root = bst_insert(root, 10);
	root = bst_insert(root, 5);
	root = bst_insert(root, 15);
	root = bst_insert(root, 3);
	root = bst_insert(root, 8);
	root = bst_insert(root, 7);
	root = bst_insert(root, 9);
	root = bst_insert(root, 20);
	root = bst_insert(root, 18);

	// 2.数据操作
	int cmd;
	while(1)
	{
		printf("Pls Input: ");
		scanf("%d", &cmd); while(getchar()!='\n');
		if(cmd != 0)	//二叉树插入
			root = bst_insert(root, cmd);
		else if(cmd == 0)	// 遍历
		{
			printf("pre_traval: ");
			pre_traval(root);	// 前序遍历
			printf("\n");
			
			printf("mid_traval: ");
			mid_traval(root);	// 中序遍历
			printf("\n");
			
			printf("lst_traval: ");
			lst_traval(root);	// 后序遍历
			printf("\n");
		}
		
		draw((_treenode *)root);
	}

	return 0;
}

// 前序遍历: 根节点-左子树-右子树
void pre_traval(node *root)
{
	if(root == NULL)
		return;
	
	printf("%d ", root->data);
	pre_traval(root->lchild);
	pre_traval(root->rchild);
}

// 中序遍历：左子树 - 根节点 - 右子树
void mid_traval(node *root)
{
	if(root == NULL)
		return;
	
	mid_traval(root->lchild);
	printf("%d ", root->data);
	mid_traval(root->rchild);
}

// 后序遍历：左子树 - 右子树 - 根节点
void lst_traval(node *root)
{
	if(root == NULL)
		return;
	
	lst_traval(root->lchild);
	lst_traval(root->rchild);
	printf("%d ", root->data);
}

//二叉树插入
node *bst_insert(node *root, int new_data)
{
	if(root == NULL)
	{
		// 如果当前根节点为NULL，说明找到了插入位置
		node *new = malloc(sizeof(node));
		new->data = new_data;
		new->lchild = NULL;
		new->rchild = NULL;
		return new;
	}
	else if(root->data > new_data)	// 如果新数据更小,往左子树插入
		root->lchild = bst_insert(root->lchild, new_data);
	else if(root->data < new_data)	// 如果新数据更大,往右子树插入
		root->rchild = bst_insert(root->rchild, new_data);
	else	// 如果相等，已存在，不作处理
		printf("已存在\n");
	
	return root;
}

2.二叉树查找

#include <stdio.h>
#include <stdlib.h>
#include "drawtree.h"

// 二叉树数据节点
typedef struct node
{
	int data;	// 数据域
	struct node *lchild;	//左子树指针
	struct node *rchild;	//右子树指针
}node;

//二叉树插入
node *bst_insert(node *root, int new_data);
// 二叉树搜索
int bst_search(node *root, int find_data);
// 前序遍历: 根节点 - 左子树 - 右子树
void pre_traval(node *root);
// 中序遍历：左子树 - 根节点 - 右子树
void mid_traval(node *root);
// 后序遍历：左子树 - 右子树 - 根节点
void lst_traval(node *root);

int main()
{
	// 1.初始化空二叉树
	node *root = NULL;

	// 插入数据
	root = bst_insert(root, 10);
	root = bst_insert(root, 5);
	root = bst_insert(root, 15);
	root = bst_insert(root, 3);
	root = bst_insert(root, 8);
	root = bst_insert(root, 7);
	root = bst_insert(root, 9);
	root = bst_insert(root, 20);
	root = bst_insert(root, 18);

	// 2.数据操作
	int cmd;
	while(1)
	{
		printf("Pls Input find_data: ");
		scanf("%d", &cmd); while(getchar()!='\n');
		if(cmd != 0)	//二叉树搜索
		{
			if(bst_search(root, cmd) == 0)
				printf("找到了\n");
			else
				printf("无此数据\n");
		}
		else if(cmd == 0)	// 遍历
		{
			printf("pre_traval: ");
			pre_traval(root);	// 前序遍历
			printf("\n");
			
			printf("mid_traval: ");
			mid_traval(root);	// 中序遍历
			printf("\n");
			
			printf("lst_traval: ");
			lst_traval(root);	// 后序遍历
			printf("\n");
		}
		
		draw((_treenode *)root);
	}

	return 0;
}

// 二叉树搜索
int bst_search(node *root, int find_data)
{
	if(root == NULL)	// 无此数据
		return -1;
	
	printf("find\n");
	if(root->data == find_data)	// 找到指定数据
		return 0;
	else if(find_data < root->data)
		return bst_search(root->lchild, find_data);
	else if(find_data > root->data)
		return bst_search(root->rchild, find_data);
}

// 前序遍历: 根节点-左子树-右子树
void pre_traval(node *root)
{
	if(root == NULL)
		return;
	
	printf("%d ", root->data);
	pre_traval(root->lchild);
	pre_traval(root->rchild);
}

// 中序遍历：左子树 - 根节点 - 右子树
void mid_traval(node *root)
{
	if(root == NULL)
		return;
	
	mid_traval(root->lchild);
	printf("%d ", root->data);
	mid_traval(root->rchild);
}

// 后序遍历：左子树 - 右子树 - 根节点
void lst_traval(node *root)
{
	if(root == NULL)
		return;
	
	lst_traval(root->lchild);
	lst_traval(root->rchild);
	printf("%d ", root->data);
}

//二叉树插入
node *bst_insert(node *root, int new_data)
{
	if(root == NULL)
	{
		// 如果当前根节点为NULL，说明找到了插入位置
		node *new = malloc(sizeof(node));
		new->data = new_data;
		new->lchild = NULL;
		new->rchild = NULL;
		return new;
	}
	else if(root->data > new_data)	// 如果新数据更小,往左子树插入
		root->lchild = bst_insert(root->lchild, new_data);
	else if(root->data < new_data)	// 如果新数据更大,往右子树插入
		root->rchild = bst_insert(root->rchild, new_data);
	else	// 如果相等，已存在，不作处理
		printf("已存在\n");
	
	return root;
}

drawtree.h

///
//
//  Copyright(C), 2013-2017, GEC Tech. Co., Ltd.
//
//  文件: lab/tree/headers/drawtree.h
//  日期: 2017-9
//  描述: 使用C语言写一页webpage展示二叉树
//
//  作者: Vincent Lin (林世霖)   微信公众号：秘籍酷
//  技术微店: http://weidian.com/?userid=260920190
//  技术交流: 260492823（QQ群）
//
///

#ifndef _DRAWTREE_H_
#define _DRAWTREE_H_

/* ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ 公共头文件 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <unistd.h>
#include <string.h>
#include <strings.h>
#include <time.h>
#include <errno.h>

#include <sys/stat.h>
#include <sys/types.h>
#include <fcntl.h>

#include <sys/ipc.h>
#include <sys/sem.h>
#include <sys/shm.h>
#include <sys/msg.h>
#include <semaphore.h>
#include <fcntl.h>

#include <pthread.h>
/* ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑ 公共头文件 ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑ */

#define MAX(a, b) ({ \
		typeof(a) _a = a; \
		typeof(b) _b = b; \
		(void)(&_a == &_b);\
		_a > _b? _a : _b; \
		})


/* ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ 默认二叉树节点 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */
typedef struct _tree_node
{
	int data;
	struct _tree_node *lchild;
	struct _tree_node *rchild;

#ifdef AVL
	int height;
#endif

#ifdef RB
	struct _tree_node *parent;
	int color;
#endif
}_treenode, *_linktree;
/* ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑ 默认二叉树节点 ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑ */


/* ↓↓↓↓↓ 用户指定二叉树节点 ↓↓↓↓↓ */
#ifndef NODE
#define NODE _treenode
#endif
/* ↑↑↑↑↑ 用户指定二叉树节点 ↑↑↑↑↑ */



/* ↓↓↓↓↓↓↓↓↓↓↓↓↓ 画网页相关算法代码 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */

#ifndef QUEUE_NODE_DATATYPE
#define QUEUE_NODE_DATATYPE NODE *
#endif

typedef QUEUE_NODE_DATATYPE qn_datatype;

struct _queue_node
{
	qn_datatype data;
	struct _queue_node *next;

};

typedef struct
{
	struct _queue_node *front;
	struct _queue_node *rear;
#ifdef QUEUE_SIZE
	int size;
#endif
}_queuenode, *_linkqueue;


static _linkqueue init_queue(void)
{
    _linkqueue q = (_linkqueue)malloc(sizeof(_queuenode));
	q->front = q->rear =
		(struct _queue_node *)malloc(sizeof(struct _queue_node));
	q->rear->next = NULL;

	return q;
}

static bool is_empty_q(_linkqueue q)
{
	return (q->front == q->rear);
}

/* ↓↓↓↓↓↓↓↓↓↓↓↓↓ 画网页相关算法代码 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */
static bool out_queue(_linkqueue q, qn_datatype *pdata)
{
	if(is_empty_q(q))
		return false;

	struct _queue_node *p = q->front;

	q->front = q->front->next;
	free(p);
	*pdata = q->front->data;

	return true;
}

static bool en_queue(_linkqueue q, qn_datatype data)
{
	struct _queue_node *pnew;
	pnew = (struct _queue_node *)malloc(sizeof(struct _queue_node));
	if(pnew == NULL)
		return false;

	pnew->data = data;
	pnew->next = NULL;

	q->rear->next = pnew;
	q->rear = pnew;

	return true;
}

#ifdef QUEUE_SIZE
int queue_size(_linkqueue *q)
{
	return q->size;
}
#endif
/* ↓↓↓↓↓↓↓↓↓↓↓↓↓ 画网页相关算法代码 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */


static inline void pre_travel(NODE *root, void (*handler)(NODE *))
{
	if(root == NULL)
		return;
	
	handler(root);
	pre_travel(root->lchild, handler);
	pre_travel(root->rchild, handler);
}

static inline void mid_travel(NODE *root, void (*handler)(NODE *))
{
	if(root == NULL)
		return;
	
	mid_travel(root->lchild, handler);
	handler(root);
	mid_travel(root->rchild, handler);
}

static inline void post_travel(NODE *root, void (*handler)(NODE *))
{
	if(root == NULL)
		return;

	post_travel(root->lchild, handler);
	post_travel(root->rchild, handler);
	handler(root);
}

/* ↓↓↓↓↓↓↓↓↓↓↓↓↓ 画网页相关算法代码 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */
static inline void level_travel(NODE *root, void (*handler)(NODE *))
{
	if(root == NULL)
		return;

    _linkqueue q;
	q = init_queue();

	en_queue(q, root);

    NODE *tmp;
	while(1)
	{
		if(!out_queue(q, &tmp))
			break;

		handler(tmp);

		if(tmp->lchild != NULL)
			en_queue(q, tmp->lchild);
		if(tmp->rchild != NULL)
			en_queue(q, tmp->rchild);
	}
}
/* ↓↓↓↓↓↓↓↓↓↓↓↓↓ 画网页相关算法代码 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */
static char page_begin[] = "<html><head><title>tree map"
                           "</title></head><body>"
			   "<table border=0 cellspacing"
                           "=0 cellpadding=0>";
static char line_begin[] = "<tr>";
static char line_end  [] = "</tr>";
static char space     [] = "<td>&nbsp;</td>";
static char underline [] = "<td style=\"border-bottom:"
	 		   "1px solid #58CB64\">&nbsp;"
                           "</td>";

#ifdef RB
static char data_begin_red[] = "<td bgcolor=\"#FF0000\";style="
			       "\"border:1px sol"
                               "id #58CB64;background-colo"
                               "r:#DDF1D8;PADDING:2px;\" t"
                               "itle=\"level: 1\">";
static char data_begin_blk[] = "<td bgcolor=\"#000000\";style="
			       "\"border:1px sol"
                               "id #58CB64;background-colo"
                               "r:#DDF1D8;PADDING:2px;\" t"
                               "itle=\"level: 1\"><font color"
				"=\"#FFFFFF\">";
static char data_end_red[] = "</td>";
static char data_end_blk[] = "</font></td>";
#else
static char data_begin[] = "<td style=\"border:1px sol"
                           "id #58CB64;background-colo"
                           "r:#DDF1D8;PADDING:2px;\" t"
                           "itle=\"level: 1\">";
static char data_end  [] = "</td>";
#endif

static char page_end  [] = "</table></body></html>";

#define MAX_NODES_NUMBER 100
#define FILENAME 32

static int central_order[MAX_NODES_NUMBER];

static void putunderline(int fd, int num)
{
	int i;
	for(i=0; i<num; i++)
	{
		write(fd, underline, strlen(underline));
	}
}


static void putspace(int fd, int num)
{
	int i;
	for(i=0; i<num; i++)
	{
		write(fd, space, strlen(space));
	}
}
/* ↓↓↓↓↓↓↓↓↓↓↓↓↓ 画网页相关算法代码 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */
#ifdef RB
static void putdata(int fd, NODE * p)
{
	char s[50];
	bzero(s, 50);

	snprintf(s, 50, "%d", p->data);

	switch(p->color)
	{
	case RED:
		write(fd, data_begin_red, strlen(data_begin_red));
		write(fd, s, strlen(s));
		write(fd, data_end_red, strlen(data_end_red));
		break;
	case BLACK:
		write(fd, data_begin_blk, strlen(data_begin_blk));
		write(fd, s, strlen(s));
		write(fd, data_end_blk, strlen(data_end_blk));
	}
}
#else
static void putdata(int fd, int data)
{
	char s[50];
	bzero(s, 50);

	snprintf(s, 50, "%d", data);
	write(fd, data_begin, strlen(data_begin));
	write(fd, s, strlen(s));
	write(fd, data_end, strlen(data_end));
}
#endif

static int Index = 0;
static void create_index(NODE * root)
{
	if(Index >= MAX_NODES_NUMBER-1)
		return;

	central_order[Index++] = root->data;
}


static int get_index(int data)
{
	int i;
	for(i=0; i<100; i++)
	{
		if(central_order[i] == data)
			return i;
	}
	return -1;
}

/* ↓↓↓↓↓↓↓↓↓↓↓↓↓ 画网页相关算法代码 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */
static void data_leftside(int fd, NODE * root, int spaces)
{
	if(root == NULL)
		return;

	int s_line=0;

	if(root->lchild != NULL)
	{
		s_line = get_index(root->data)-
			 get_index(root->lchild->data)-1;
	}
	putspace(fd, spaces-s_line);
	putunderline(fd, s_line);
}


static int data_rightside(int fd, NODE * root)
{
	if(root == NULL)
		return 0;

	int s_line=0;

	if(root->rchild != NULL)
	{
		s_line = get_index(root->rchild->data)-
			 get_index(root->data)-1;
	}

	putunderline(fd, s_line);
	return s_line;
}


static void start_page(int fd)
{
	write(fd, page_begin, strlen(page_begin));
}

/* ↓↓↓↓↓↓↓↓↓↓↓↓↓ 画网页相关算法代码 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */
static void end_page(int fd)
{
	write(fd, page_end, strlen(page_end));
}


static void draw(NODE * root)
{
	if(root == NULL)
		return;

	time_t t;
	time(&t);
	static char filename[FILENAME];
	bzero(filename, FILENAME);
	snprintf(filename, FILENAME, "1.html");
	int fd = open(filename, O_CREAT | O_TRUNC | O_RDWR, 0644);
	if(fd == -1)
	{
		perror("open() failed");
		exit(1);
	}

	Index = 0;
	mid_travel(root, create_index);

    _linkqueue q = init_queue();

	NODE * tmp = root;
	int ndata = 1;

	start_page(fd);
	while(1)
	{
		write(fd, line_begin, strlen(line_begin));

		int i, n = 0;
		int nextline = 0;
		for(i=0; i<ndata; i++)
		{
			int index = get_index(tmp->data);

			data_leftside(fd, tmp, index-n);

			#ifdef RB
			putdata(fd, tmp);
			#else
			putdata(fd, tmp->data);
			#endif
			int rightline = data_rightside(fd, tmp);

			if(tmp->lchild != NULL)
			{
				nextline++;
				en_queue(q, tmp->lchild);
			}
			if(tmp->rchild != NULL)
			{
				nextline++;
				en_queue(q, tmp->rchild);
			}
			if(!out_queue(q, &tmp))
				return;

			n = index + rightline;
			n++;
		}
		write(fd, line_end, strlen(line_end));
		ndata = nextline;
	}
	end_page(fd);
	close(fd);
}
#endif

在这里插入图片描述
冒泡排序

#include <stdio.h>

void show_array(int len, int *a)
{
	int i;
	for(i=0; i<len; i++)
		printf("%d ", a[i]);
	printf("\n");
}

void bubble_sort(int len, int *a)
{
	// 遍历次数：len-1
	int i, j;
	int temp;
	int flag;
	for(i=0; i<len-1; i++)
	{
		flag=0;
		// 两两对比，左数大于右数则交换（次数: len-i-1）
		for(j=0; j<len-i-1; j++)
		{
			if(a[j] > a[j+1])
			{
				temp = a[j];
				a[j] = a[j+1];
				a[j+1] = temp;
				flag = 1;
			}
		}

		printf("%d: ", i+1);
		show_array(5, a);
		
		// 如果没有发生数据交换，则说明已经是有序列
		if(flag == 0)
			break;
	}
}

int main()
{
	int arr[5] = {5, 4, 3, 2, 1};
	show_array(5, arr);

	bubble_sort(5, arr);

	show_array(5, arr);

	return 0;
}

插入排序-额外空间

#include <stdio.h>

void show_array(int len, int *a)
{
	int i;
	for(i=0; i<len; i++)
		printf("%d ", a[i]);
	printf("\n");
}

void insertion_sort(int len, int *a)
{
	// 1.定义有序列数组，将第1个数据放入
	int b[len];
	b[0] = a[0];

	// 2.将原始数据的每个数据与有序列中数据对比，找到插入位置pos
	int i;		// 原始数据操作下标
	int j;		// 向后移动变量
	int pos;	// 有序列对比下标
	for(i=1; i<len; i++)
	{
		// 2.1 在有序列中循环找到插入位置pos后，break结束
		for(pos=0; pos<i; pos++)	
		{
			if(a[i] < b[pos])
				break;
		}
		// 2.2 将pos后续数据向后移动（从最后开始）
		for(j=i; j>pos; j--)
			b[j] = b[j-1];
		// 2.3 数据放入有序列中pos位置
		b[pos] = a[i];

		// 把中间过程的数据打印出来
		printf("%d: ", i);
		show_array(5, b);
	}

	// 3.将有序列数据覆盖无序列
	for(i=0; i<len; i++)
		a[i] = b[i];
}

int main()
{
	int arr[5] = {2, 5, 3, 1, 4};
	show_array(5, arr);

	insertion_sort(5, arr);

	show_array(5, arr);

	return 0;
}

插入排序

#include <stdio.h>

void show_array(int len, int *a)
{
	int i;
	for(i=0; i<len; i++)
		printf("%d ", a[i]);
	printf("\n");
}

void insertion_sort(int len, int *a)
{
	int swap;	//无序列数下标
	int pos;
	int i;
	// 逐个循环取得无序数
	for(swap=1; swap<len; swap++)
	{
		// 1.暂存当前无序数
		int temp = a[swap];

		// 2.该无序数与有序列每个数据对比，找到插入位置pos
		for(pos=0; pos<swap; pos++)
		{
			if(temp < a[pos])
				break;
		}

		// 3.将pos后续数据逐个向后移动（从后开始）
		int i;
		for(i=swap; i>pos; i--)
			a[i] = a[i-1];
		
		// 4.将该无序数写入有序列
		a[pos] = temp;
	}
}

int main()
{
	int arr[5] = {2, 5, 3, 1, 4};
	show_array(5, arr);

	// 不使用额外内存
	insertion_sort(5, arr);

	show_array(5, arr);

	return 0;
}

数据结构与算法最新文章

【力扣106】从中序与后续遍历序列构造二叉

leetcode 322 零钱兑换

哈希的应用：海量数据处理

动态规划|最短Hamilton路径

华为机试_HJ41 称砝码【中等】【menset】【

【C与数据结构】——寒假提高每日练习Day1

基础算法——堆排序

2023王道数据结构线性表--单链表课后习题部

LeetCode 之反转链表的一部分

【题解】lintcode必刷50题＜有效的括号序列

加:2022-03-03 16:39:43 更:2022-03-03 16:40:34

360图书馆购物三丰科技阅读网日历万年历 2024年11日历

-2024/11/26 15:42:09-

图片自动播放器
↓图片自动播放器↓

TxT小说阅读器
↓语音阅读,小说下载,古典文学↓

一键清除垃圾
↓轻轻一点,清除系统垃圾↓

图片批量下载器
↓批量下载图片,美女图库↓

网站联系: qq:121756557 email:121756557@qq.com IT数码