C语言二叉树和堆(个人笔记)

二叉树和堆

- 二叉树
- - 1二叉树的概念和结构
  - - 1.1特殊的二叉树
    - 1.2二叉树的性质（规定根节点的层数为1）
    - 1.3二叉树的存储结构
  - 2.二叉树的顺序结构和实现
  - - 2.1二叉树的顺序结构
    - 2.2堆的概念和结构
    - 2.3堆的实现
    - 2.4堆的应用
    - - 2.4.1堆排序
    - 2.5TOP-K问题
  - 3.二叉树的遍历
  - 4.二叉树的节点个数以及高度等
  - 5.笔试题

二叉树

1二叉树的概念和结构

一颗二叉树是节点的一个有限集合：

为空
由一个根节点加上两颗别称为左子树和右子树的二叉树组成

在这里插入图片描述

1.1特殊的二叉树

满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。节点总数：2^k-1
完全二叉树：就是满二叉树的最后一层节点是不完全的，但视觉上看从左到右是不间断的。

1.2二叉树的性质（规定根节点的层数为1）

一颗非空二叉树的第i层上最多有2^(i-1)个节点
深度为h的二叉树最大节点数是2^h-1
对于任何一颗树，如果度为0其叶子节点的个数为n0，度为2的分支节点个数为n2，则有n0=n2+1
具有n个节点的满二叉树的深度，h=log2（n+1）
有n个节点的完全二叉树，按照从上至下从左到右的数组顺序对所有节点从0开始编号，则对于序号为i的节点有：
1.若i>0,i位置节点的双亲序号：（i-1)/2;i=0,i为根节点，则无双亲节点
2.若2i+1<n，左孩子序号：2i+1，2i+1>=n则无左孩子
3.若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

1.3二叉树的存储结构

1.顺序存储
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费（如果说不是完全二叉树，但数组上要留空间给那些截断的地方）。而现实中使用中只有堆才会使用数组来存储。
二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

2.链式存储
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。

2.二叉树的顺序结构和实现

2.1二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

2.2堆的概念和结构

根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆的性质：
1.堆中某个节点的值总是不大于或不小于其父节点的值（不大于就是小堆，不小于就是大堆）
2.堆总是一棵完全二叉树。

2.3堆的实现

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

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = 0;
	php->size = 0;
}

void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[parent] > a[child])
		{
			Swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void AdjustDown(HPDataType* a,int n, int parent)
{
	int child = parent * 2 + 1;
	
	while (child < n)
	{
		if (child + 1 < n && a[child] > a[child + 1])
	    {
		    child = child + 1;
	    }
		if (a[parent] > a[child])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

bool HeapEmpty(HP* php)
{
	assert(php);
	if (php->size == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		int newCapacity = php->capacity = 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}
	php->a[php->size] = x;
	php->size++;
	AdjustUp(php->a, php->size - 1);
}

void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	AdjustDown(php->a, php->size, 0);
}

HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	return php->a[0];
}



int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

2.4堆的应用

2.4.1堆排序

利用堆的思想进行排序,就两步:

建堆
升序:建大堆
降序:建小堆
2.利用堆删除思想来进行排序
建堆和堆删除中都用到了向下调整

void HeapSort(int* a, int n)
{
	// 升序 -- 建大堆
	// 降序 -- 建小堆


	// 建堆--向上调整建堆
	for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}

	// 建堆--向下调整建堆 --O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}

	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);

		// 再调整，选出次小的数
		AdjustDown(a, end, 0);

		--end;
	}
}

int main()
{
	int a[] = { 7,8,3,5,1,9,5,4 };
	HeapSort(a, sizeof(a) / sizeof(int));

	return 0;
}

2.5TOP-K问题

即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
解决思路:

用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆
用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

void CreateNDate()
{
	//造数据
	int n = 1000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}

	for (size_t i = 0;i < n;i++)
	{
		int x = rand() % 1000000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}

void PrintTopK(int k)
{
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fout fail");
		return;
	}
	int* kminheap = (int*)malloc(sizeof(int) * k);
	if (kminheap == NULL)
	{
		perror("malloc fail");
		return;
	}
	for (int i = 0;i < k;i++)
	{
		fscanf(fout, "%d", &kminheap[i]);
	}

	//建小堆
	for (int i = (k - 1 - 1) / 2;i >= 0;i--)
	{
		AdjustDown(kminheap, k, i);
	}

	int val = 0;
	while (!feof(fout))
	{
		fscanf(fout, "%d", &val);
		if (val > kminheap[0])
		{
			kminheap[0] = val;
			AdjustDown(kminheap, k, 0);
		}
	}
	for (int i = 0;i < k;i++)
	{
		printf("%d ", kminheap[i]);
	}
	printf("\n");
}

3.二叉树的遍历

二叉树遍历是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。

前序遍历（根左子树右子树）
中序遍历（左子树根右子树）
后序遍历（左子树右子树根）
层序遍历（从根节点开始从左往右，从上到下，依次访问）

// 二叉树前序遍历
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}
// 二叉树中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	PreOrder(root->left);
	printf("%d ", root->data);
	PreOrder(root->right);
}
// 二叉树后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	
	PreOrder(root->left);
	PreOrder(root->right);
	printf("%d ", root->data);
}

//二叉树层序遍历（上一层出时带下一层进队列）
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->data);
		if (root->left)
		{
			QueuePush(&q, root->left);
		}
		if (root->right)
		{
			QueuePush(&q, root->right);
		}
	}
	printf("\n");
	QueueDestroy(&q);
}

4.二叉树的节点个数以及高度等

// 二叉树节点个数(左子树的节点个数加右子树的节点个数)
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
// 二叉树叶子节点个数(左子树的叶子节点个数加右子树叶子节点个数)
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right = NULL)
	{
		return 1;
	}
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
//二叉树的高度（左子树的高度跟右子树高度比较）
int BTreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int LeftHeight = BTreeHeight(root->left);
	int RightHeight = BTreeHeight(root->right);
	return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1;
}

// 二叉树第k层节点个数（左子树第k减一层的节点个数+右子树第k减一层的节点个数，返回条件k=1）
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	assert(k > 0);
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->left,k-1) + BinaryTreeLeafSize(root->right,k-1);
}
// 二叉树查找值为x的节点（左子树找x，找到返回，右子树找x，找到返回，切记层层往回返）
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->val == x)
	{
		return root;
	}
	BTNode* ret1=BinaryTreeFind(root->left, x);
	if (ret1)
	{
		return ret1;
	}
	BTNode* ret2=BinaryTreeFind(root->right, x);
	if (ret2)
	{
		return ret2;
	}
	return NULL;
}

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* root = BuyNode(a[*pi]);
	(*pi)++;
	root->left = BinaryTreeCreate(a, n, pi);
	root->right= BinaryTreeCreate(a, n, pi);
	return root;
}
// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
}
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			break;
		}
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

5.笔试题

单值二叉树
在这里插入图片描述

//返回条件：遇到NULL返回true，根的左子树与根不同返回false，根的右子树与根不同返回false，相同什么都决定不了。
//左子树和右子树都相同才为真
bool isUnivalTree(struct TreeNode* root)
{
    if(root==NULL)
    {
        return true;
    }
    if(root->left && root->left->val!=root->val)
    {
        return false;
    }
    if(root->right && root->right->val!=root->val)
    {
        return false;
    }
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

相同的树
在这里插入图片描述

//结束条件：两边都为空则true，一边为空一边不为空则false，值不同返回false
//左子树右子树都相等才行
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    if(p==NULL&&q==NULL)
    {
        return true;
    }
    if(p==NULL||q==NULL)
    {
        return false;
    }
    if(p->val!=q->val)
    {
        return false;
    }
    return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}

对称二叉树
在这里插入图片描述

//相同的树小进阶题
bool _isSymmetric(struct TreeNode* l,struct TreeNode* r)
{
    if(l==NULL&&r==NULL)
    {
        return true;
    }
    if(l==NULL||r==NULL)
    {
        return false;
    }
    if(l->val!=r->val)
    {
        return false;
    }
    return _isSymmetric(l->left,r->right)&&_isSymmetric(l->right,r->left);
}

bool isSymmetric(struct TreeNode* root)
{
    return _isSymmetric(root->left,root->right);
}

二叉树的前序遍历
在这里插入图片描述

//这道题的意思是让你返回一个前序遍历塞进去的数组，*returnSize是输出型参数，是让你自己去计算值，然后再赋给它，下标i一定要传地址，如果不这样每一层递归都是一个新i，++就没有了意义
int _returnSize(struct TreeNode* root)
{
    if(root==NULL)
    {
        return 0;
    }
    return _returnSize(root->left)+_returnSize(root->right)+1;
}

void _preorderTraversal(struct TreeNode* root,int* a,int* pi)
{
    if(root==NULL)
    {
        return;
    }
    a[(*pi)++]=root->val;
    _preorderTraversal(root->left,a,pi);
    _preorderTraversal(root->right,a,pi);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    *returnSize=_returnSize(root);
    int* a=(int*)malloc(*returnSize*sizeof(int));
    int i=0;
    _preorderTraversal(root,a,&i);
    return a;
}

二叉树中序遍历

在这里插入图片描述

//代码与上题基本一致
int _returnSize(struct TreeNode* root)
{
    if(root==NULL)
    {
        return 0;
    }
    return _returnSize(root->left)+_returnSize(root->right)+1;
}

void _inorderTraversal(struct TreeNode*root,int* a,int* pi)
{
    if(root==NULL)
    {
        return;
    }
    _inorderTraversal(root->left,a,pi);
    a[(*pi)++]=root->val;
    _inorderTraversal(root->right,a,pi);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
    *returnSize=_returnSize(root);
    int* a=(int*)malloc(sizeof(int)*(*returnSize));
    int i=0;
    _inorderTraversal(root,a,&i);
    return a;
}

二叉树后序遍历
在这里插入图片描述

//与上题基本一致
int _returnSize(struct TreeNode* root)
{
    if(root==NULL)
    {
        return 0;
    }
    return _returnSize(root->left)+_returnSize(root->right)+1;
}

void _postorderTraversal(struct TreeNode*root,int* a,int* pi)
{
    if(root==NULL)
    {
        return;
    }
    _postorderTraversal(root->left,a,pi);
    _postorderTraversal(root->right,a,pi);
    a[(*pi)++]=root->val;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize)
{
    *returnSize=_returnSize(root);
    int* a=(int*)malloc(sizeof(int)*(*returnSize));
    int i=0;
    _postorderTraversal(root,a,&i);
    return a;
}

另一颗树的子树
在这里插入图片描述

//对比相同的树的变型题，思路：每一颗不为空的节点都可以认为子树的根，返回false
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    if(p==NULL&&q==NULL)
    {
        return true;
    }
    if(p==NULL||q==NULL)
    {
        return false;
    }
    if(p->val!=q->val)
    {
        return false;
    }
    return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
    if(root==NULL)
    {
        return false;
    }
    if(isSameTree(root,subRoot))
    {
        return true;
    }
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

二叉树的遍历
在这里插入图片描述

//除了创建树这个函数之外，其他的就是基操，创建树可以递归创建！！！
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

typedef char BTDataType;

typedef struct BinaryTreeNode
{
    BTDataType data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
} BTNode;

BTNode* BuyNode(BTDataType x)
{
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    if (node == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    node->data = x;
    node->left = NULL;
    node->right = NULL;
    return node;
}

BTNode* CreateTree(char* a, int* pi)
{
    if(a[*pi]=='#')
    {
        (*pi)++;
        return NULL;
    }
    BTNode* root=BuyNode(a[*pi]);
    (*pi)++;
    root->left=CreateTree(a,pi);
    root->right=CreateTree(a,pi);
    return root;
}

void InOrder(BTNode* root)
{
    if (root == NULL)
    {
        return;
    }
    InOrder(root->left);
    printf("%c ", root->data);
    InOrder(root->right);
}

int main()
{
    char arr[100] = { 0 };
    scanf("%s", arr);
    int i = 0;
    BTNode* root = CreateTree(arr, &i);
    InOrder(root);
    printf("\n");
    return 0;
}