开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 《数据结构》（六）树的基本概念以及二叉树的实现与详解 -> 正文阅读

[数据结构与算法]《数据结构》（六）树的基本概念以及二叉树的实现与详解

今天的重点是二叉树和对树的了解。字数很多，很详细，大家收藏起来，慢慢回味😉😉😉

树的基本概念

🎤树型结构是一种非线性数据结构。 其中以树和二叉树最为常用，树是由n(n>0)个结点组成，并以分支关系定义的层次结构。 在现实生活中是很常见的，如人类社会的族谱，社会中各个组织机构都可以用树来形象的描述，直观来说，就像把一颗树倒过来一样。本篇就带大家了解一下树的基本概念，重点在于二叉树的概念和实现。

树的概念

🎤树（tree）是由n(n>0)个结点组成的一个具有层次关系的集合。
在任意一个非空树中：
（1）有且仅有一个特定的结点，被称为根（root）；
（2）当n>1时，其余结点可以分为m（m>0）个不可相交的有限集T₁，T₂，T₃，…T_m，其中每个集合本身又是一棵树，并且称为树的子树。
画个图，图中有空树，只有根结点的树，还有一般的树。

子树是不相交的；
除了根结点以外，每个结点有且仅有一个父结点

了解这些，大家对树就有了抽象的概念了

树的基本知识

树：树的结点包含一个数据元素及若干指向其子树的分支；
结点的度：结点拥有的子树的个数称为结点的度；
叶子或终端结点：度为0的结点被称为叶子或终端结点；
分支结点或非终端结点： 度不为0的结点称为非终端结点或分支结点；
内部结点： 除根结点之外，分支结点也被称为内部结点；
树的度： 树的度是树内各结点的度的最大值；
孩子结点和双亲结点： 结点的子树的根称为该结点的孩子，该结点称为孩子的双亲；
兄弟结点： 同一个双亲结点的孩子称为兄弟结点；
祖先： 从根到该节点所经分支上的所有节点被称为结点的祖先；
子孙： 以某节点为根的子树中任一节点都称为该节点的子孙；
森林： 由m（m>0）棵互不相交的多颗树的集合称为森林；

树的表示

🎤树结构相比于线性结构来说，是极为复杂的，存储起来也更加的麻烦，实际中树有很多种表示方式，如：双亲表示法，左右孩子表示法、左孩子右兄弟表示法等等。我们这里就简单的了解其中最常用的左孩子右兄弟表示法。
左孩子右兄弟表示法， 顾名思义，也就是说有两个指针，一个指针指向左边第一个孩子，另外一个指针指向右边第一个兄弟。
在这里插入图片描述

typedef int DataType;
typedef struct TreeNode
{
	struct TreeNode* FirstChild;//指向左边第一个孩子，也叫左孩子
	struct TreeNode* NextBrother;//指向右边第一个兄弟结点，也叫右结点
	DataType data;
}TNode;

这里只对树结构有一个简单的了解，重点在后面的二叉树。

二叉树的概念

概念

🎤二叉树是树结构的其中之一，它的特点是每个结点最多只有两颗子树（即二叉树中不存在度大于2的结点）

二叉树的模型

在这里插入图片描述

特殊的二叉树

🎤满二叉树： 一个二叉树，如果每一个层的结点数都达到2，则这个二叉树就是满二叉
树。那么满二叉树的结点个数就是2*K-1个（K为二叉树的层数）
🎤完全二叉树： 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对
于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号
从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉
树。

存储结构

🎤二叉树的存储结构分为两种：一种是顺序存储结构；另一种是链式存储结构。

二叉树的顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树
会有空间的浪费。
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的
方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩
子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链，当前我们学习中一般都
是二叉链，三叉链等后续会详细介绍。

二叉树链式结构的实现

🎤在下面，大家一定要自己动手去画递归图，这样能更加直观更加立体的了解二叉树是怎样递归的。

二叉链的表示

🎤二叉链也叫左右孩子表示法。 其中一个指针指向左孩子，另一个指针指向右孩子。
在这里插入图片描述

typedef char BTDataType;

typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;//左孩子
	struct BinaryTreeNode* right;//右孩子

	BTDataType data;
}BTNode;

二叉树的遍历（前中后序）

🎤遍历二叉树，即按照某条搜索路径巡防树中的每个结点，使每个结点有且仅被访问一次。 二叉树的链式结构一般都是用左右孩子表示法来实现，再由二叉树的定义可得，二叉树是由三个基本单元组成的，分别为根节点，左子树和右子树。
若限定先左和先右的话，就有三种情况：前序（先根）遍历；中序（中根）遍历；后序（后根）遍历。 由递归的思想可以，前中后序的操作定义也基本有了一定的思路：

前序遍历的思路：（1）先访问根结点；（2）前序遍历左子树；（3）前序遍历右子树。

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

中序遍历的思路：（1）先中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。

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

后序遍历的思路：（1）先后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。

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

树结点的个数

🎤分治思想，将大问题分成小问题解决，在二叉树里就是递归的思想


int TreeSize(BTNode* root)
{
	return	root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

叶子结点的个数

🎤度为0的结点被称为叶子或终端结点

int TreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

层序遍历

🎤这里需要用到队列，最后我会把所有代码放在下面
🎤层序遍历的核心思想就是上一层出队的时候带着下一层所有的结点进队
在这里插入图片描述

//层序遍历，核心思想：上一层出队的时候带下一层的结点进队
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%c ", front->data);
		if (root->left)
		{
			QueuePush(&q, front->left);
		}
		if (root->right)
		{
			QueuePush(&q, front->right);
		}
	}
	printf("\n");
	QueueDestory(&q);
}

二叉树的销毁

🎤如果我们用前序或者中序来遍历销毁的话，会发现，有的结点找不到了，而后续遍历销毁却避开这个问题。

void TreeDestory(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	TreeDestory(root->left);
	TreeDestory(root->right);

	free(root);
	root = NULL;
}

代码

因为我们层序遍历中，用到了队，我就直接把队列的定义和实现的代码放了进来。 到这里，我相信大家对二叉树已经掌握了🎉🎉🎉，有错误大家可以指出哦，有疑问也可以问我，大家共同进步，后续会持续更新《数据结构》的相关内容，大家喜欢的话可以关注一下，😚😚😚下面是项目代码，大家参考一下。

test.c

#include<stdio.h>
#include<stdlib.h>
#include"Queue.h"

typedef char BTDataType;

typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;//左孩子
	struct BinaryTreeNode* right;//右孩子

	BTDataType data;
}BTNode;


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

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

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

//分治思想--大问题分成小问题来解决，也就是递归
int TreeSize(BTNode* root)
{
	return	root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
//求叶子结点的个数
int TreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
//层序遍历，核心思想：上一层出队的时候带下一层的结点进队
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%c ", front->data);
		if (root->left)
		{
			QueuePush(&q, front->left);
		}
		if (root->right)
		{
			QueuePush(&q, front->right);
		}
	}
	printf("\n");
	QueueDestory(&q);
}


//树的销毁--用后序的思想，一步一步销毁就行了
void TreeDestory(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	TreeDestory(root->left);
	TreeDestory(root->right);

	free(root);
	root = NULL;
}
int main()
{
	BTNode* A = (BTNode*)malloc(sizeof(BTNode));
	A->data = 'A';
	A->left = NULL;
	A->right = NULL;

	BTNode* B = (BTNode*)malloc(sizeof(BTNode));
	B->data = 'B';
	B->left = NULL;
	B->right = NULL;

	BTNode* C = (BTNode*)malloc(sizeof(BTNode));
	C->data = 'C';
	C->left = NULL;
	C->right = NULL;

	BTNode* D = (BTNode*)malloc(sizeof(BTNode));
	D->data = 'D';
	D->left = NULL;
	D->right = NULL;

	BTNode* E = (BTNode*)malloc(sizeof(BTNode));
	E->data = 'E';
	E->left = NULL;
	E->right = NULL;

	//链接
	A->left = B;
	A->right = C;
	B->left = D;
	B->right = E;

	PrevOrder(A);
	printf("\n");
	InOrder(A);
	printf("\n");
	PostOrder(A);
	printf("\n");

	printf("TreeSizeA:%d\n", TreeSize(A));
	printf("TreeSizeB:%d\n", TreeSize(B));
	printf("TreeLeafSizeA:%d\n", TreeLeafSize(A));
	printf("TreeLeafSizeB:%d\n", TreeLeafSize(B));

	LevelOrder(A);

	TreeDestory(A);
	return 0;
}

Queue.h

#pragma once

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

//前置声明
struct BinaryTreeNode;
typedef struct BinaryTreeNode* QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;

}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestory(Queue* pq);
//入队---队尾入
void QueuePush(Queue* pq, QDataType x);
//出队---队头出
void QueuePop(Queue* pq);

//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);
//数据个数
int QueueSize(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);

Queue.c

#include"Queue.h"

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}

void QueueDestory(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

//入队---队尾入
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));//新结点的创建
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	//先把新申请的结点的数据域和指针域赋值
	newnode->data = x;
	newnode->next = NULL;
	//如果队列中没有一个结点的时候
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	//如果队列中有结点的时候
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;//链接之后让tail成为新的尾
	}
}
//出队---队头出
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->tail);//既然是出队列，那么就要判断队列是不为空的，空了还出个毛线

	if (pq->head->next == NULL)//当队列中只剩下一个结点的时候，防止tail成为野指针
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else//多个结点
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

//取队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);//先判断一下队头数据是不是空，如果为空就不能调用

	return pq->head->data;//很简单，直接返回队头的数据即可
}
//取队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);//同上

	return pq->tail->data;//直接返回队尾的数据即可
}
//数据个数
int QueueSize(Queue* pq)
{
	//这次就需要遍历链表，也是非常简单的
	assert(pq);

	int size = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		++size;
		cur = cur->next;
	}
	return size;
}
//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;//如果等于空就是真，不等于空就是假
}