二叉树（链表实现）

二叉树链式结构的实现

二叉树的遍历

1. 前序、中序以及后序遍历

  学习二叉树结构，最简单的方式就是遍历。

  所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：
  1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
  2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
  3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

2. 层序遍历

  层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

代码实现：

Tree.h

#pragma once

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

typedef char BTDataType;

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


// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);

// 二叉树销毁
void BinaryTreeDestory(BTNode** pproot);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
//二叉树的深度
int maxDepth(BTNode* root);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
 层序遍历
//void BinaryTreeLevelOrder(BTNode* root);

Tree.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"
#include"Queue.h"



// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	while (*pi < n )
	{
		if (a[*pi] == '#')
		{
			(*pi)++;
			return NULL;
		}
		BTNode* root = (BTNode*)malloc(sizeof(BTNode));
		if (root == NULL)
		{
			perror("malloc fail\n");
			exit(-1);
		}
		root->val = a[(*pi)++];
		root->left = BinaryTreeCreate(a, n, pi);
		root->right = BinaryTreeCreate(a, n, pi);
		return root;
	}

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

}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	else
	{
		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 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);
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)//根 == NULL 
		return NULL;

	if (root->val == x)//根
		return root;

	BTNode* ret1 = BinaryTreeFind(root->left, x);//左子树
	BTNode* ret2 = BinaryTreeFind(root->right, x);// 右子树
	if (ret1 != NULL)
		return ret1;

	if (ret2 != NULL)
		return ret2;

	return NULL;
}
//二叉树的深度
int maxDepth(BTNode* root) {
	if (root == NULL)
		return 0;

	int ret1 = maxDepth(root->left);
	int ret2 = maxDepth(root->right);

	if (ret1 >= ret2)
		return ret1 + 1;
	else
	{
		return ret2 + 1;
	}
}
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{

	if (root == NULL)
	{
		printf("N ");
		return;
	}
	printf("%c ", root->val);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	BinaryTreeInOrder(root->left);
	printf("%c ", root->val);
	BinaryTreeInOrder(root->right);

}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	BinaryTreeInOrder(root->left);
	BinaryTreeInOrder(root->right);
	printf("%c ", root->val);
}
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%c ", front->val);
		if(front->left)
			QueuePush(&q, front->left);
		if(front->right)
			QueuePush(&q, front->right);
	}
	printf("\n");
	QueueDestroy(&q);
}

Test.c

#include"Tree.h"
int main()
{
	char a[] = "ABD##E#H##CF##G##";
	int length = sizeof(a) / sizeof(char);
	int i = 0;
	BTNode* pt = BinaryTreeCreate(a,length,&i);
	BinaryTreePrevOrder(pt);
	printf("\n");
	BinaryTreeInOrder(pt);
	//Inorder(pt);
	printf("\n");
	BinaryTreePostOrder(pt);
	printf("\n%d ", BinaryTreeSize(pt));
	printf("\n%d ", BinaryTreeSize(pt));
	printf("\nmaxDepth:%d ", maxDepth(pt));
	printf("\nTree4LevelSize:%d ", BinaryTreeLevelKSize(pt,4));
	printf("\n");
	BTNode* ret= BinaryTreeFind(pt,'A');
	ret->val ='W';
	BinaryTreePrevOrder(pt);
	printf("\n");
	BinaryTreeLevelOrder(pt);
	BinaryTreeDestory(&pt);
	return 0;
}

这个博客如果对你有帮助，给博主一个免费的点赞就是最大的帮助❤

欢迎各位点赞，收藏和关注哦❤

如果有疑问或有不同见解，欢迎在评论区留言哦❤

后续我会一直分享双一流211西北大学软件（C，数据结构，C++，Linux，MySQL）的学习干货以及重要代码的分享