数据结构之链式二叉树

标签：NULL return BTNode 二叉树链式数据结构 root 节点

前言：前面我们学习了树相关的概念及堆的实现，今天来看看二叉树的实现。

正式实现二叉树前，我们先了解一些基础知识。

对于二叉树基础知识不清楚的可以观看数据结构------树这篇文章，回顾一下知识，有助于理解二叉树。

二叉树的遍历方式都有哪些呢？

. 前序遍历：按照根节点，左节点，右节点的顺序进行遍历

. 中序遍历：按照左节点，根节点，右节点的顺序进行遍历

. 后序遍历：按照左节点，右节点，根节点的顺序进行遍历

. 层序遍历：顾名思义就是按照二叉树一层一层的顺序进行遍历

1. 二叉树的定义

typedef struct BinaryTreeNode
{
	BTDataType val;//存储当前节点的值
	struct BinaryTreeNode* left;//指向当前节点的左孩子
	struct BinaryTreeNode* right;//指向当前节点的右孩子
}BTNode;

2. 二叉树的接口

//前序遍历
void PreOreder(BTNode* root);

//中序遍历
void InOrder(BTNode* root);

//后序遍历
void PostOrder(BTNode* root);

//二叉树节点的个数
int BinaryTreeSize(BTNode* root);

//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root);

//二叉树的叶子节点个数
int BinaryTreeLeafSize(BTNode* root);

//二叉树第k层节点的个数
int BinaryTreeKSize(BTNode* root, int k);

//查找二叉树值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

//二叉树的销毁
void BinaryTreeDestroy(BTNode** root);

//层序遍历
void LevelOrder(BTNode* root);

//判断是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);

3. 二叉树的实现

3.1 前序遍历

//前序遍历
void PreOreder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->val);
	PreOreder(root->left);
	PreOreder(root->right);
}

如图所示：
在这里插入图片描述

在这里插入图片描述

3.2 中序遍历

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

在这里插入图片描述

3.3 后序遍历

//后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c ", root->val);
}

在这里插入图片描述

按照不同方式遍历的特点去递归调用就可以了，一定要加以画图才能更好的理解。

3.4 二叉树节点的个数

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

当前节点不为空就说明有节点，记为1，每一棵二叉树都可以由根节点+左子树+右子树构成，然后再分别去统计左子树和右子树的节点个数，最后求和。

3.5 二叉树的高度

//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftDepth = 1 + BinaryTreeDepth(root->left);
	int rightDepth = 1 + BinaryTreeDepth(root->right);
	return leftDepth > rightDepth ? leftDepth : rightDepth;
}

当前节点不为空，高度+1，再分别去求左子树和右子树的高度，进行比较，大的便是二叉树的高度(深度)。之所以进行比较，是因为左子树和右子树的高度有可能不同，所以要选取大的数据作为二叉树的高度。

3.6 二叉树的叶子节点个数

//二叉树的叶子节点个数
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);
}

叶子结点的特点是该节点的左右孩子都为空，该节点就为叶子结点。分别去统计左右子树的叶子结点进行求和。

3.7 二叉树第K层节点的个数

//二叉树第k层节点的个数
int BinaryTreeKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	//k控制递归的次数，当前节点不为空时，返回1，否则返回0
	return BinaryTreeKSize(root->left, k - 1) + BinaryTreeKSize(root->right, k - 1);
}

当K为1时，说明已经递归到了第K层，此时只需要统计第K-1层左右孩子的个数就可以了。

3.8 查找二叉树值为X的节点

//查找二叉树值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->val == x)
	{
		return root;
	}
	BTNode* leftfind = BinaryTreeFind(root->left, x);
	if (leftfind)
	{
		return leftfind;
	}
	BTNode* rightfind = BinaryTreeFind(root->right, x);
	if (rightfind)
	{
		return rightfind;
	}
	//未找到，返回NULL
	return NULL;
}

当前节点不为空就比较该节点的值是否为X，相等就返回该节点，否则就继续对左右子树进行遍历。

3.9 二叉树的销毁

if (*root == NULL)
{
	return;
}
BinaryTreeDestroy(&(*root)->left);
BinaryTreeDestroy(&(*root)->right);
free(*root);
*root = NULL;

3.10 层序遍历

//层序遍历
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front)
		{
			printf("%c ", front->val);
			if (front->left)
			{
				QueuePush(&q, front->left);
			}
			if (front->right)
			{
				QueuePush(&q, front->right);
			}
		}
	}
	QueueDestroy(&q);
}

在这里插入图片描述
层序遍历需要借助队列来实现。首先将二叉树的根节点入队列，判断队列是否为空，不为空就出队列，判断出队列的节点是否为空（空二叉树），再判断该节点左右孩子是否为空，不为空就将该节点左右孩子入队列。

3.11 判断是否是完全二叉树

//判断是否是完全二叉树
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;
}

判断是否是完全二叉树也需要队列来实现。先将根节点入队列，判断队列是否为空，不为空出队列，判断该节点是否为空，为空就跳出循环，否则，将该节点的左右孩子入队列。跳出循环之后继续判断队列剩下的节点是否全部为空，为空说明是完全二叉树，反之，不是完全二叉树。

4. 链式二叉树完整代码

. Tree.h

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType val;//存储当前节点的值
	struct BinaryTreeNode* left;//指向当前节点的左孩子
	struct BinaryTreeNode* right;//指向当前节点的右孩子
}BTNode;

//前序遍历
void PreOreder(BTNode* root);

//中序遍历
void InOrder(BTNode* root);

//后序遍历
void PostOrder(BTNode* root);

//二叉树节点的个数
int BinaryTreeSize(BTNode* root);

//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root);

//二叉树的叶子节点个数
int BinaryTreeLeafSize(BTNode* root);

//二叉树第k层节点的个数
int BinaryTreeKSize(BTNode* root, int k);

//查找二叉树值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

//二叉树的销毁
void BinaryTreeDestroy(BTNode** root);

//层序遍历
void LevelOrder(BTNode* root);

//判断是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);

. Tree.c

#define _CRT_SECURE_NO_WARNINGS

#include"Tree.h"
#include"Queue.h"
//前序遍历
void PreOreder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->val);
	PreOreder(root->left);
	PreOreder(root->right);
}

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

//后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c ", root->val);
}

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

//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftDepth = 1 + BinaryTreeDepth(root->left);
	int rightDepth = 1 + BinaryTreeDepth(root->right);
	return leftDepth > rightDepth ? leftDepth : rightDepth;

	//return 1 + (BinaryTreeDepth(root->left) > BinaryTreeDepth(root->right) ? 
		//BinaryTreeDepth(root->left) : BinaryTreeDepth(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 BinaryTreeKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	//k控制递归的次数，当前节点不为空时，返回1，否则返回0
	return BinaryTreeKSize(root->left, k - 1) + BinaryTreeKSize(root->right, k - 1);
}

//查找二叉树值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->val == x)
	{
		return root;
	}
	BTNode* leftfind = BinaryTreeFind(root->left, x);
	if (leftfind)
	{
		return leftfind;
	}
	BTNode* rightfind = BinaryTreeFind(root->right, x);
	if (rightfind)
	{
		return rightfind;
	}
	//未找到，返回NULL
	return NULL;
}

//二叉树的销毁
void BinaryTreeDestroy(BTNode** root)
{
	删除的是叶子结点
	///*if (*root == NULL)
	//{
	//	return;
	//}
	//if ((*root)->left == NULL && (*root)->right == NULL)
	//{
	//	free(*root);
	//	*root = NULL;
	//	return;
	//}
	//BinaryTreeDestroy(&(*root)->left);
	//BinaryTreeDestroy(&(*root)->right);*/


	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestroy(&(*root)->left);
	BinaryTreeDestroy(&(*root)->right);
	free(*root);
	*root = NULL;
}

//层序遍历
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front)
		{
			printf("%c ", front->val);
			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;
}

. test.c

#define _CRT_SECURE_NO_WARNINGS

#include"Tree.h"

BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("BuyNode():malloc fail");
		exit(-1);
	}
	newnode->val = x;
	newnode->left = newnode->right = NULL;
	return newnode;
}

BTNode* CreateTree()
{
	//手动创建一棵二叉树
	BTNode* n1 = BuyNode('A');
	BTNode* n2 = BuyNode('B');
	BTNode* n3 = BuyNode('C');
	BTNode* n4 = BuyNode('D');
	BTNode* n5 = BuyNode('E');
	BTNode* n6 = BuyNode('F');
	n1->left = n2;
	n1->right = n3;
	n2->left = n4;
	n3->left = n5;
	n3->right = n6;
	return n1;
}
void Test()
{
	BTNode* root = CreateTree();
	//PreOreder(root);
	//InOrder(root);
	//PostOrder(root);
	int size = BinaryTreeSize(root);
	printf("%d\n", size);
	int depth = BinaryTreeDepth(root);
	printf("%d\n", depth);
	int leafsize = BinaryTreeLeafSize(root);
	printf("%d\n", leafsize);
	int ksize = BinaryTreeKSize(root, 3);
	printf("%d\n", ksize);
	if (BinaryTreeFind(root, 'E'))
	{
		printf("找到了\n");
	}
	else
	{
		printf("未找到\n");
	}
	LevelOrder(root);
	LevelOrder(NULL);
	if (BinaryTreeComplete(root))
	{
		printf("完全二叉树\n");
	}
	else
	{
		printf("非完全二叉树\n");
	}
	BinaryTreeDestroy(&root);

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

这里并没有写队列的代码实现，看不懂的小伙伴请移步初阶数据结构之队列的实现。

标签：NULL,return,BTNode,二叉树,链式,数据结构,root,节点
From： https://blog.csdn.net/2402_84532723/article/details/144791934

数据结构之链式二叉树

1. 二叉树的定义

2. 二叉树的接口

3. 二叉树的实现

3.1 前序遍历

3.2 中序遍历

3.3 后序遍历

3.4 二叉树节点的个数

3.5 二叉树的高度

3.6 二叉树的叶子节点个数

3.7 二叉树第K层节点的个数

3.8 查找二叉树值为X的节点

3.9 二叉树的销毁

3.10 层序遍历

3.11 判断是否是完全二叉树

4. 链式二叉树完整代码

相关文章

赞助商

阅读排行