数据结构系列-二叉树之前序遍历

🌈个人主页：羽晨同学

💫个人格言:“成为自己未来的主人~”

这篇文章，我们主要的内容是对二叉树当中的前历的算法进行讲解，二叉树中的算法所要求实现的是从根到左子树再到右子树的遍历顺序，可能这样不太好理解，我们拿一张图片进行解释，

假设在这个二叉树当中，我们要实现二叉树遍历当中的前历，我们应该怎么做呢。

我们先来分析一下这个的实现逻辑是什么，按照根节点，左子树，右子树的顺序，我们先来判断一下这个应该实现的结果是什么。

很明显，应该是1 2 3 N N N 4 5 N N 6 N N

在这里，我们将空也表现了出来，那下面，我们就讲解一下怎么用代码实现这个过程

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

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

void HPInit(HP* php);
void HPInitArray(HP* php, HPDataType* a, int n);

void HPDestroy(HP* php);
//插入后保持数据是堆
void HPPush(HP* php, HPDataType x);
HPDataType HPTop(HP* php);
//删除堆顶的数据
void HPPop(HP* php);

bool HPEmpty(HP* php);

void AdjustUp(HPDataType* a, int child);
void AdjustDowm(HPDataType* a, int n, int parent);
void Swap(HPDataType* px, HPDataType* py);

#define _CRT_SECURE_NO_WARNINGS
#include"code.4.26.HeapSort.h"
void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = php->size = 0;
}
void HPInitArray(HP* php, HPDataType* a, int n)
{
	assert(php);
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		perror("malloc fail");
	}
	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->capacity = php->size = n;
	//开始进行数据的调整
	//向上调整，时间复杂度是NlogN
	for (int i = 1; i < php->size; i++)
	{
		AdjustUp(php->a, i);
	}
	//向下调整，时间复杂度是N
	for (int i = (php->size - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDowm(php->a, php->size, i);
	}
}

void HPDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}
Swap(HPDataType* px, HPDataType* py)
{
	HPDataType tmp = *px;
	*px = *py;
	*py = tmp;
}
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void AdjustDowm(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		//假设法，假设左孩子比较大
		if (child + 1 < n && a[child] < a[child + 1])
		{
			//右孩子比较大
			++child;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}


//插入后保持数据是堆
void HPPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->capacity == php->size)
	{
		size_t newcapacity = php->capacity == 0 ? 4 : php->size * 2;
		HPDataType* tmp = 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);
}
HPDataType HPTop(HP* php)
{
	assert(php);
	return php->a[0];
}
//删除堆顶的数据
void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	Swap(&php->a[0], &php->a[php->size--]);
	php->size--;

	AdjustDowm(php->a, php->size, 0);
}

bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

这些代码我们在前面就详细的进行了展开，在这里我们就不进行详细的讲解

#define _CRT_SECURE_NO_WARNINGS
#include"code.4.26.HeapSort.h"
//升序，建大堆
void HeapSort(int* a, int n)
{
	//a数组直接建堆O（N）
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDowm(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDowm(a, end, 0);
		--end;
	}
}

typedef struct BinTreeNode
{
	struct BinTreeNode* left;
	struct BinTreeNode* right;
	int val;
}BTNode;
BTNode* BuyBTNode(int val)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->val = val;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;
}

//手搓一棵树
BTNode* CreatTree()
{
	BTNode* n1 = BuyBTNode(1);
	BTNode* n2 = BuyBTNode(2);
	BTNode* n3 = BuyBTNode(3);
	BTNode* n4 = BuyBTNode(4);
	BTNode* n5 = BuyBTNode(5);
	BTNode* n6 = BuyBTNode(6);
	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n4->right = n5;
	n4->right = n6;
	return n1;
}
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	printf("%d ", root->val);
	PreOrder(root->left);
	PreOrder(root->right);
}