数据结构——二叉树（下）

时间：2024-10-15 13:20:07

数据结构——二叉树（下）

文章目录

  • 数据结构——二叉树（下）
    • 一、引言：
        • 接上文使用顺序结构的数组存储堆（一种二叉树），在这篇文章我们来了解一下堆的应用。
      • 1、堆排序
      • 2、TOP-K问题
    • 二、实现链式结构存储二叉树
      • 1.定义二叉树的链式结构
      • 2.前中后序遍历
        • 遍历规则
          • 2.1前序遍历---根左右
          • 2.2中序遍历---左根右
          • 2.3后序遍历---左右根
      • 3.二叉树结点个数
      • 4.二叉树叶子结点个数
      • 5.二叉树第k层结点个数
      • 6.二叉树的深度/高度
      • 7.二叉树查找值为x的结点
      • 8.二叉树销毁
      • 9.层序遍历
      • 10.判断二叉树是否是完全⼆叉树---借助数据结构：队列
      • 11.完整代码
        • 11.1Tree.h
        • 11.2Tree.c
        • 11.3Queue.h
        • 11.4Queue.c
        • 11.5test.c

一、引言：

接上文使用顺序结构的数组存储堆（一种二叉树），在这篇文章我们来了解一下堆的应用。

1、堆排序

第1种. 基于已有数组建堆、取堆顶元素 完成排序版本

  • 需要堆的数据结构
  • 空间复杂度为O(N)
void HeapSort(int*arr,int n)
{
	HP hp;
	HPInit(&hp);
	for (int i = 0; i < n; i++)
	{
		HPPush(&hp, arr[i]);//建堆
	}

	int i = 0;
	while (!HPEmpty(&hp))
	{
		arr[i++] = HPTop(&hp);//取堆顶数据
		HPPop(&hp);//出堆
	}
	for (int i = 0; i < 6; i++)
	{
		printf("%d ", arr[i]);//打印
	}
	printf("\n");

	HPDestroy(&hp);//销毁
}

第2种.有⼀个前提，必须提供有现成的数据结构堆。（推荐）

数组建堆，首尾交换，交换后的堆尾数据从堆中删掉，将堆顶数据向下调整选出较小的数据

  • 升序，建大堆
  • 降序，建小堆
  • 堆排序时间复杂度为： O(N*log N)
void HeapSort(int* arr, int n)
{
	// a数组直接建堆 O(N)
    for (int i = (n-1-1)/2; i >= 0; --i)
    {
        AdjustDown(arr, n, i);//从最后一个结点的父结点开始建小堆
    }
    
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);//第一个元素和最后一个元素交换位置
		AdjustDown(arr, 0, end);//把交换后的数据排除在外，进行向下调整算法
		end--;//去掉交换后的数据
	}
}

2、TOP-K问题

TOP-K问题即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。如：专业前10名、世界100强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，我们可能就会想到直接去排序不就好了吗？但是当数据量非常大，排序就不太可取了（可能数据都不能一下子全部加载到内存中）。

最佳的方式就是用堆来解决，基本思路如下：

  • 前K个最大的元素，则建小堆

    取前k个数据假设建小堆，取N-K中的数据一个个和堆顶进比较，比堆顶数据要大，则跟堆顶交换（堆要向下调整），当遍历完剩下的数据，我们就会发现建的这个小堆的K个数据就是N个数据中最大的前K个数据。

  • 前K个最小的元素，则建大堆

    取前k个数据建大堆，取N-K中的数据一个个和堆顶数据进行比较，比堆顶数据要小，则跟堆顶交换（堆要向下调整），当遍历完剩下的数据，我们就会发现建的这个大堆的K个数据就是N个数据中最小的前K个数据。

void CreateNDate()
{
	// 造数据
	int n = 100000;
	srand(time(0));//随机生成十万个数据
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");//创建一个文件，以写的形式
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
	for (int i = 0; i < n; ++i)
	{
		int x = (rand() + i) % 1000000;//生成随机数字
		fprintf(fin, "%d\n", x);//把x往文件里面去写
	}
	fclose(fin);//关闭文件
}
void TOPK()
{
	int k = 0;
	printf("请输入k:");
	scanf("%d", &k);
	//从文件中读取前k个数据，建堆
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");//以只读的方式打开文件
	if (fout == NULL)
	{
		perror("fopen fail!");
		exit(1);
	}
	int* minHeap = (int*)malloc(k * sizeof(int));//就前k个数据进行建堆
	if (minHeap == NULL)//如果动态申请的空间失败了
	{
		perror("malloc fail!");//报错
		exit(2);//直接退出
	}
	
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minHeap[i]);//从文件中读取前k个数据
	}
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(minHeap, i, k);//建K个数据的小堆
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", minHeap[i]);//打印
	}
	return;
	int x = 0;
	while (fscanf(fout, "%d") != EOF)
	{
		//读取的数据跟堆顶的数据进行比较
		//比较堆顶值大，交换入堆
		if (x > minHeap[0])
		{
			minHeap[0] = x;//与堆顶交换数据
			AdjustDown(minHeap, 0, k);//向下调整
		}
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", minHeap[i]);
	}
	fclose(fout);//关闭文件
}

二、实现链式结构存储二叉树

1.定义二叉树的链式结构

//二叉树结点的结构
typedef int BTDataType;
typedef struct BinaryTreeNode
{
	int data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

为了更好的理解二叉树，我们先来手动的创建一个链式二叉树

BTNode* buyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->left = newnode->right = NULL;

	return newnode;
}
void CreateTree()
{
    BTNode* node1 = buyNode(1);
	BTNode* node2 = buyNode(2);
	BTNode* node3 = buyNode(3);
	BTNode* node4 = buyNode(4);

	node1->left = node2;
	node1->right = node3;
	node2->left = node4;
} 
int main()
{
    CreateTree();
    return 0;
}

⼆叉树分为空树和⾮空⼆叉树，⾮空⼆叉树由根结点、根结点的左⼦树、根结点的右⼦树组成的。

根结点的左⼦树和右⼦树分别⼜是由⼦树结点、⼦树结点的左⼦树、⼦树结点的右⼦树组成的，因此⼆叉树定义是 递归式的,后序链式二叉树的操作中基本都是按照该概念实现的。

在这里插入图片描述

2.前中后序遍历

⼆叉树的操作离不开树的遍历，我们先来看看⼆叉树的遍历有哪些⽅式

在这里插入图片描述

遍历规则

按照规则，⼆叉树的遍历有：前序/中序/后序的递归结构遍历：

1）前序遍历(Preorder Traversal 亦称先序遍历)：访问根结点的操作发⽣在遍历其左右⼦树之前

访问顺序为：根结点、左⼦树、右⼦树

2）中序遍历(Inorder Traversal)：访问根结点的操作发⽣在遍历其左右⼦树之中（间）

访问顺序为：左⼦树、根结点、右⼦树

3）后序遍历(Postorder Traversal)：访问根结点的操作发⽣在遍历其左右⼦树之后

访问顺序为：左⼦树、右⼦树、根结点

2.1前序遍历—根左右
//前序遍历---根左右
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);

}
2.2中序遍历—左根右
// 中序遍历---左根右
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}
2.3后序遍历—左右根
//后序遍历---左右根
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

3.二叉树结点个数

// 二叉树结点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

4.二叉树叶子结点个数

// 二叉树叶⼦结点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

5.二叉树第k层结点个数

// 二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->left, k - 1) 
		+ BinaryTreeLevelKSize(root->right, k - 1);
}

6.二叉树的深度/高度

//二叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftDep = BinaryTreeDepth(root->left);
	int rightDep = BinaryTreeDepth(root->right);

	return leftDep > rightDep ? leftDep + 1 : rightDep + 1;
}

7.二叉树查找值为x的结点

// 二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* leftFind = BinaryTreeFind(root->left, x);
	if (leftFind)
	{
		return leftFind;
	}
	BTNode* rightFind = BinaryTreeFind(root->left, x);
	if (rightFind)
	{
		return rightFind;
	}
	return NULL;
}

8.二叉树销毁

销毁左子树+销毁右子树+销毁根结点

// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&((*root)->left));
	BinaryTreeDestory(&((*root)->right));

	free(*root);
	*root = NULL;
}

9.层序遍历

设二叉树的根结点所在层数为1，层序遍历就是从所在二叉树的根结点出发，⾸先访问第⼀层的树根结点，然后从左到右访问第2层上的结点，接着是第三层的结点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

实现层序遍历需要额外借助数据结构：队列。

//层序遍历---借助数据结构：队列
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头，打印
		BTNode*front= QueueFront(&q);
		printf("%d ", front->data);
		QueuePop(&q);
		//队头结点的左右孩子入队列
		if (front->left)
			QueuePush(&q, front->left);
		if (front->right)
			QueuePush(&q, front->right);
	}
	QueueDestroy(&q);
}

10.判断二叉树是否是完全⼆叉树—借助数据结构：队列

// 判断⼆叉树是否是完全⼆叉树---借助数据结构：队列
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	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 != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

11.完整代码

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

//定义二叉树的链式结构
//二叉树结点的结构
typedef int BTDataType;
typedef struct BinaryTreeNode
{
	int data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

//前序遍历
void PreOrder(BTNode* root);
// 中序遍历
void InOrder(BTNode* root);
//后序遍历
void PostOrder(BTNode* root);

// ⼆叉树结点个数
int BinaryTreeSize(BTNode* root);
// ⼆叉树结点个数
//void BinaryTreeSize(BTNode* root,int* psize);错的解法
// ⼆叉树叶⼦结点个数
int BinaryTreeLeafSize(BTNode* root);
// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root);
// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root);
//层序遍历
void LevelOrder(BTNode* root);
// 判断⼆叉树是否是完全⼆叉树
bool BinaryTreeComplete(BTNode* root);
11.2Tree.c
#include"Tree.h"
#include"Queue.h"
//前序遍历---根左右
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);

}
// 中序遍历---左根右
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}
//后序遍历---左右根
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);

}

// ⼆叉树结点个数
//int size = 0;
//int BinaryTreeSize(BTNode* root)
//{
//	if (root == NULL)
//	{
//		return 0;
//	}
//	++size;
//	BinaryTreeSize(root->left);
//	BinaryTreeSize(root->right);
//	return size;
//}
//void BinaryTreeSize(BTNode* root,int* psize)
//{
//	if (root == NULL)
//	{
//		return 0;
//	}
//	++(*psize);
//	BinaryTreeSize(root->left,psize);
//	BinaryTreeSize(root->right,psize);
//}
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
// ⼆叉树叶⼦结点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->left, k - 1) 
		+ BinaryTreeLevelKSize(root->right, k - 1);
}

//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftDep = BinaryTreeDepth(root->left);
	int rightDep = BinaryTreeDepth(root->right);

	return leftDep > rightDep ? leftDep + 1 : rightDep + 1;
}

// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* leftFind = BinaryTreeFind(root->left, x);
	if (leftFind)
	{
		return leftFind;
	}
	BTNode* rightFind = BinaryTreeFind(root->left, x);
	if (rightFind)
	{
		return rightFind;
	}
	return NULL;
}

// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&((*root)->left));
	BinaryTreeDestory(&((*root)->right));

	free(*root);
	*root = NULL;
}

//层序遍历---借助数据结构：队列
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头，打印
		BTNode*front= QueueFront(&q);
		printf("%d ", front->data);
		QueuePop(&q);
		//队头结点的左右孩子入队列
		if (front->left)
			QueuePush(&q, front->left);
		if (front->right)
			QueuePush(&q, front->right);
	}
	QueueDestroy(&q);
}

// 判断⼆叉树是否是完全⼆叉树---借助数据结构：队列
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	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 != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}
11.3Queue.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

//定义队列结构
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue
{
	QueueNode* phead;
	QueueNode* ptail;
	int size;//保存队列有效数据个数
}Queue;

void QueueInit(Queue* pq);

// ⼊队列，队尾
void QueuePush(Queue* pq, QDataType x);
// 出队列，队头
void QueuePop(Queue* pq);
//队列判空
bool QueueEmpty(Queue* pq);

//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);
11.4Queue.c
#include"Queue.h"
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//申请新的结点
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		//队列不为空
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL && pq->ptail == NULL;
}
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//只有一个结点的情况，避免ptail变成野指针
	if (pq->ptail == pq->phead)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		//删除对头结点
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	--pq->size;
}
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->ptail->data;
}
//队列有效元素个数
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

void QueueDestroy(Queue* pq)
{
	assert(pq);
	//assert(!QueueEmpty(pq));

	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		Queue* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
11.5test.c
#include"Tree.h"

BTNode* buyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->left = newnode->right = NULL;

	return newnode;
}

void test01()
{
	BTNode* node1 = buyNode(1);
	BTNode* node2 = buyNode(2);
	BTNode* node3 = buyNode(3);
	BTNode* node4 = buyNode(4);

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

	/*PreOrder(node1);
	printf("\n");
	InOrder(node1);
	printf("\n");
	PostOrder(node1);*/

	//int size = 0;
	//printf("size:%d\n", BinaryTreeSize(node1,&size));
	//printf("size:%d\n", BinaryTreeSize(node1,&size));
	//BinaryTreeSize(node1, &size);
	//printf("size:%d\n", size);
	
	//printf("size:%d\n", BinaryTreeSize(node1));
	//printf("size:%d\n", BinaryTreeSize(node1));
	/*printf("size:%d\n", BinaryTreeSize(node1));
	printf("leaf size:%d\n", BinaryTreeLeafSize(node1));
	printf("第K层size:%d\n", BinaryTreeLevelKSize(node1,3));
	printf("第K层size:%d\n", BinaryTreeLevelKSize(node1,2));

	printf("depth/height:%d\n", BinaryTreeDepth(node1));

	BTNode* find = BinaryTreeFind(node1, 4);
	printf("%s\n", find == NULL ? "未找到！" : "找到了！");*/

	//LevelOrder(node1);
	bool ret = BinaryTreeComplete(node1);
	printf("%s\n", ret == false ? "不是完全二叉树" : "是完全二叉树");


	BinaryTreeDestory(&node1);

}

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

P.S.目前，我们在最开始学习二叉树的时候对二叉树的限制较少，在这里实现插入、删除之类的操作没有意义，后续给大家更新到的平衡树或红黑树，二叉树会有限制，笔者会细细写到此类知识，敬请期待！

希望本篇文章对你有所帮助，有任何问题欢迎在评论区留言哦~

相关文章