堆与二叉树——C语言

一、顺序表底层

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int data;
typedef struct Heap
{
	data* arr;
	int size;
	int capacity;
}Heap;

void HeapInit(Heap* php);
void HeapDestroy(Heap* php);
//把已有堆进行排序
void treesort(Heap* php);

void HeapPush(Heap* php, data x);
void HeapPop(Heap* php);
data HeapTop(Heap* php);
int HeapEmpty(Heap* php);
int HeapSize(Heap* php);

void AdjustUp(Heap* a, int child);
void AdjustDown(Heap* a, int n, int parent);

void print(Heap* php);

#include"heap.h"

void swap(data* x, data* y)
{
	data z = *x;
	*x = *y;
	*y = z;
}

//大堆
void AdjustUp(Heap* php, int i)
{
	int child = i;
	int parent = (i - 1) / 2;

	while (child > 0)
	{
		if (php->arr[child] > php->arr[parent])
		{
			swap(&(php->arr[child]), &(php->arr[parent]));
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

//大堆
void AdjustDown(Heap* php, int i, int n)
{
	int parent = i;
	int child = 2 * i + 1;
	while (child < n)
	{
		//选出大儿子
		if (((child + 1) < php->size) && (php->arr[child + 1] > php->arr[child]))
		{
			child++;
		}

		if (php->arr[parent] < php->arr[child])
		{
			swap(&(php->arr[child]), &(php->arr[parent]));
			parent = child;
			child = (parent + 1) * 2;
		}
		else
		{
			break;
		}
	}
}

void treesort(Heap* php)
{
	int n = php->size - 1;
	while (n)
	{
		swap(&(php->arr[n]), &(php->arr[0]));
		AdjustDown(php, 0, n - 1);
		n--;
	}
}


void HeapInit(Heap* php)
{
	assert(php);

	data* tmp = (data*)malloc(sizeof(data) * 4);
	if (tmp == NULL)
	{
		perror("malloc failure");
		return -1;
	}
	php->arr = tmp;
	php->size = 0;
	php->capacity = 4;
}

void HeapDestroy(Heap* php)
{
	php->size = php->capacity = 0;
	free(php->arr);
	php = NULL;
}

void HeapPush(Heap* php, data x)
{
	if (php->capacity == php->size)
	{
		data* tmp = (data*)realloc(php->arr, sizeof(data) * (php->capacity * 2));
		if (tmp == NULL)
		{
			perror("realloc failure");
			return -1;
		}
		php->arr = tmp;
		php->capacity = php->capacity * 2;
	}
	php->arr[php->size] = x;
	php->size++;

	AdjustUp(php, php->size - 1);
}

void HeapPop(Heap* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	swap(&(php->arr[0]), &(php->arr[php->size - 1]));
	
	php->size--;
	AdjustDown(php, 0, php->size);
}

int HeapSize(Heap* php)
{
	return php->arr+(php->size - 1) - php->arr;
}

data HeapTop(Heap* php)
{
	assert(php);
	return php->arr[0];
}

int HeapEmpty(Heap* php)
{
	if (php->size == 0)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}

void print(Heap* php)
{
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->arr[i]);
	}
	printf("\n");
}

#include"heap.h"

void test1()
{
	Heap tree;
	HeapInit(&tree);
	HeapPush(&tree, 4);
	HeapPush(&tree, 6);
	HeapPush(&tree, 2);
	HeapPush(&tree, 7);
	HeapPush(&tree, 12);
	HeapPush(&tree, 9);
	HeapPush(&tree, 8);
	HeapPush(&tree, 3);

	print(&tree);

	treesort(&tree);

	print(&tree);

	HeapDestroy(&tree);
}

int main()
{
	test1();
	return 0;
}

二、链表底层

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

typedef int data;
typedef struct node
{
	data a;
	struct node* left;
	struct node* right;
}node;

node* buynode(data x)
{
	node* tmp = malloc(sizeof(node));
	if (tmp == NULL)
	{
		perror("malloc failure");
		return -1;
	}

	tmp->a = x;
	tmp->left = NULL;
	tmp->right = NULL;

	return tmp;
}

node* treecreate()
{
	node* head = buynode(2);
	node* node1 = buynode(5);
	node* node2 = buynode(3);
	node* node3 = buynode(4);
	node* node4 = buynode(2);
	node* node5 = buynode(8);

	head->left = node1;
	head->right = node2;
	node1->left = node3;
	node1->right = node4;
	node2->left = node5;

	return head;
}

void preorder(node* head)
{
	if (head == NULL)
	{
		printf("NULL ");
		return 0;
	}
	printf("%d ", head->a);
	preorder(head->left);
	preorder(head->right);
}

void inorder(node* head)
{
	if (head == NULL)
	{
		printf("NULL ");
		return 0;
	}
	preorder(head->left);
	printf("%d ", head->a);
	preorder(head->right);
}

void postorder(node* head)
{
	if (head == NULL)
	{
		printf("NULL ");
		return 0;
	}
	preorder(head->left);
	preorder(head->right);
	printf("%d ", head->a);
}

int size(node* head)
{
	return head == NULL ? 0 : size(head->left) + size(head->right) + 1;
}

int height(node* head)
{
	int leftheight = 0;
	int rightheight = 0;
	if (head == NULL)
	{
		return 0;
	}
	else
	{
		leftheight = height(head->left);
		rightheight = height(head->right);

		return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
	}
}

int levelnode(node* head, int k)
{
	if (head == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	
	return levelnode(head->left, k - 1) + levelnode(head->right, k - 1);
}

int main()
{
	node* head = treecreate();
	preorder(head);
	printf("\n");
	inorder(head);
	printf("\n");
	postorder(head);
	printf("\n");
	printf("%d\n", size(head));
	printf("%d\n", height(head));
	printf("%d\n", levelnode(head, 3));
	return 0;
}