二叉树详解(深度优先遍历、前序，中序，后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数)

人参与 | 时间：2025-06-24 12:46:55

一、树概念及结构(了解)

1.1树的概念

1.2树的表示

二、二叉树概念及结构

2.1概念

2.2现实中的二叉树：

2.3数据结构中的二叉树：

2.4特殊的二叉树：

2.5 二叉树的存储结构

2.51 顺序存储：

2.5.2 链式存储：

三、二叉树性质相关选择题练习

四、二叉树的实现

4.1头文件：

4.2Test.c

4.3前序，中序，后序(深度优先遍历)

4.4二叉树所有节点的个数

编辑

4.5叶节点的个数

4.6层序遍历(广度优先遍历，使用队列)

一、树概念及结构(了解)

1.1树的概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它
叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
有一个特殊的结点，称为根结点，根节点没有前驱结点除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继，因此，树是递归定义的。

节点的度：一个节点含有的子树的个数称为该节点的度；如下图：A的为6
叶节点或终端节点：度为0的节点称为叶节点；如上图：B、C、H、I...等节点为叶节点
非终端节点或分支节点：度不为0的节点；如上图：D、E、F、G...等节点为分支节点
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A是B 的父节点
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；如上图：B是A的孩子节点
兄弟节点：具有相同父节点的节点互称为兄弟节点；如上图：B、C是兄弟节点
树的度：一棵树中，最大的节点的度称为树的度；如上图：树的度为6
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次；如上图：树的高度为4

关于树的高度，还有一种看法，就是把高度从0开始看，此时树的高度为3。

节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
森林：由m（m>0）棵互不相交的多颗树的集合称为森林；（数据结构中的学习并查集本质就是一个森林）

1.2树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：双亲表示法，孩子表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

typedef int DataType;
struct Node
{
    struct Node* _firstChild1;    // 第一个孩子结点
    struct Node* _pNextBrother;   // 指向其下一个兄弟结点
    DataType _data;               // 结点中的数据域
};

另一种方式：顺序表存孩子的指针（不推荐使用）

struct TreeNode
{
int data;
vector<struct TreeNode*> childs;
}

还有一种表示方式，双亲表示法:

双亲表示法采用顺序表（数组）存储普通树，其实现的核心思想是：顺序存储各个节点的同时，给各节点附加一个记录其父节点位置的变量。

#define MAX_SIZE 100 // 宏定义树中结点的最大数量

typedef struct Snode{
char data;
int parent;
} PTNode;

typedef struct{
PTNode tnode[MAX_SIZE]; // 存放树中所有结点
int n; // 结点数
} PTree;

1.3树在实际中的运用（表示文件系统的目录树结构）

二、二叉树概念及结构

2.1概念

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子
树和右子树的二叉树组成。

二叉树的特点：
1. 每个结点最多有两棵子树，即二叉树不存在度大于2的结点。
2. 二叉树的子树有左右之分，其子树的次序不能颠倒。

2.2现实中的二叉树：

2.3数据结构中的二叉树：

2.4特殊的二叉树：

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

2.5 二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。
二叉树的性质

若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.
若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h- 1.
对任何一棵二叉树，如果度为0其叶结点个数为 n0，度为2的分支结点个数为 n2，则有n0＝n2＋1
若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=logN + 1

2.51 顺序存储：

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树
会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲
解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

2.5.2 链式存储：

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的
方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩
子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链，当前我们学习中一般都
是二叉链，后面课程学到高阶数据结构如红黑树等会用到三叉链。

2.53 父子存储：

父子存储的下标位置规律：

如果要用数组存储二叉树，那么必须要符合顺序存储中父子存储的规律

2.6大小堆概念

注意：

堆并非是一定有序的：左孩子与右孩子之间没有大小关系

最大堆：在最大堆中，父节点的值总是大于或等于其子节点的值。但是，左孩子和右孩子之间并没有固定的大小关系。也就是说，左孩子可以大于、小于或等于右孩子，这都不会违反最大堆的定义。
最小堆：在最小堆中，父节点的值总是小于或等于其子节点的值。同样地，左孩子和右孩子之间的大小关系是不确定的。

这种特性使得堆成为一种非常有效的数据结构，特别是在实现优先队列等应用中。堆可以在对数时间内完成插入和删除最大（或最小）元素的操作，这是因为它不需要保持整个结构的完全排序。

举个例子：

10     /   \    5     8   / \   / \  2   3 6   7

在这个堆中，父节点的值总是大于或等于其子节点的值。但是，你可以看到左孩子和右孩子之间的大小关系是不一致的。例如，5的左孩子是2，右孩子是3，而8的左孩子是6，右孩子是7。这里并没有规定左孩子必须大于或小于右孩子。

三、二叉树性质相关选择题练习

1.某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为（
）
A ABDHECFG
B ABCDEFGH
C HDBEAFCG
D HDEBFGCA
2.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则二叉树根结点为
（）
A E
B F
C G
D H
3.设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为____。
A adbce
B decab
C debac
D abcde

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（）
A 不存在这样的二叉树
B 200
C 198
D 199
2.在具有 2n 个结点的完全二叉树中，叶子结点个数为（）
A n
B n+1
C n-1
D n/2
3.一棵完全二叉树的节点数位为531个，那么这棵树的高度为（）
A 11
B 10
C 8
D 12

四、二叉树的实现

4.1头文件：

#pragma once#include <stdio.h>#include <stdbool.h>#include <assert.h>#include <stdlib.h>typedef int BTDataType;typedef struct BinaryTreeNode{ 	struct BinaryTreeNode* left;	struct BinaryTreeNode* right;	BTDataType data;}BTNode;

4.2Test.c

int main(){ 	char str[100]; // 存储节点值的字符串  	scanf("%s", str); // 读取输入字符串，注意应该直接传入数组名	int i = 0; // 索引初始化为0  	BTNode* root = CreatTree(str, &i); // 创建二叉树，并将根节点赋值给root  	PrevOrder(root); // 前序遍历二叉树并输出结果  	printf("\n");	InOrder(root);//  中序遍历二叉树并输出结果	printf("\n");	PostOrder(root);//  后序遍历二叉树并输出结果	printf("\n");}

4.3创建一个二叉树

// 创建一个二叉树的函数，a是包含节点值的字符串，pi是指向当前要处理的字符的索引的指针  BTNode* CreatTree(char* a, int* pi){ 	// 如果当前字符是'#'，表示这是一个空节点  	if (a[*pi] == '#')	{ 		++(*pi); // 增加索引  		return NULL; // 返回空指针表示这是一个空节点  	}	// 为新节点分配内存  	BTNode* root = (BTNode*)malloc(sizeof(BTNode));	if (root == NULL)	{ 		printf("malloc fail\n"); // 如果分配失败，输出错误信息  		exit(-1); // 退出程序  	}	// 设置节点的值，并增加索引  	root->data = a[*pi];	++(*pi);	// 递归地创建左子树和右子树  	root->left = CreatTree(a, pi);	root->right = CreatTree(a, pi);	return root; // 返回新创建的节点}

4.4前序，中序，后序(深度优先遍历)

// 先序遍历二叉树  void PrevOrder(BTNode* root){ 	// 如果当前节点为空，则打印"NULL"并返回  	if (root == NULL)	{ 		printf("NULL ");		return;	}	// 访问当前节点的数据  	printf("%c ", root->data);	// 递归遍历左子树  	PrevOrder(root->left);	// 递归遍历右子树  	PrevOrder(root->right);}// 中序遍历二叉树  void InOrder(BTNode* root){ 	// 如果当前节点为空，则打印"NULL"并返回  	if (root == NULL)	{ 		printf("NULL ");		return;	}	// 递归遍历左子树  	InOrder(root->left);	// 访问当前节点的数据  	printf("%c ", root->data);	// 递归遍历右子树  	InOrder(root->right);}// 后序遍历二叉树  void PostOrder(BTNode* root){ 	// 如果当前节点为空，则打印"NULL"并返回  	if (root == NULL)	{ 		printf("NULL ");		return;	}	// 递归遍历左子树  	PostOrder(root->left);	// 递归遍历右子树  	PostOrder(root->right);	// 访问当前节点的数据  	printf("%c ", root->data);}

4.4二叉树所有节点的个数

//方法一:定义全局变量(不推荐)// 全局变量，用于记录树的大小（节点数）  // 注意：使用全局变量通常不是好的做法，应该尽量避免  int size = 0;    // 计算二叉树的大小（节点数）void TreeSize(BTNode* root)  {   	// 如果节点为空，则不计算大小，直接返回  	if (root == NULL)  	{   		return; // 在 void 函数中这样写是可以的，但如果是 int 类型函数则需要返回一个整数值  	}  	else {   		// 节点非空，增加 size 的计数  		++size;  	}    	// 递归计算左子树的大小  	TreeSize(root->left);  	// 递归计算右子树的大小  	TreeSize(root->right);  	}

方法二:传址调用

// 定义TreeSize函数，用于计算二叉树的大小（节点数）  // 参数：root - 指向二叉树根节点的指针；psize - 指向一个整数的指针，用于存储节点数  void TreeSize(BTNode* root, int* psize)  {   	// 如果根节点为空（即树为空），则直接返回，不执行任何操作  	if (root == NULL)  	{   		return;  	}  	else // 如果根节点不为空（即树非空）  	{   		// 通过解引用psize指针来递增其指向的整数值，表示当前节点被计数  		++(*psize);  	}    	// 递归调用TreeSize函数来计算左子树的大小  	TreeSize(root->left, psize);  	// 递归调用TreeSize函数来计算右子树的大小  	TreeSize(root->right, psize);  }

方法三:递归、分治思想:
否则，返回左子树节点数 + 右子树节点数 + 1（当前节点）

int TreeSize(BTNode* root){     // 如果树为空（即根节点为NULL），则返回0      // 否则，返回左子树节点数 + 右子树节点数 + 1（当前节点）    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;}

4.6叶节点的个数

int LeafSize(BTNode* root){ 	if (root == NULL)		return 0;	if (root->left == NULL && root->right == NULL)		return 1;	return TreeSize(root->left) + TreeSize(root->right);}// 计算二叉树中叶子节点的数量（但存在错误）  int LeafSize(BTNode* root)  {       // 如果当前节点为空，说明不是叶子节点，返回0      if (root == NULL)          return 0;        // 如果当前节点既没有左子树也没有右子树，那么它是一个叶子节点，返回1      if (root->left == NULL && root->right == NULL)          return 1;        // 递归计算左子树和右子树中的叶子节点数量，并返回它们的和    return TreeSize(root->left) + TreeSize(root->right); }

4.7层序遍历(广度优先遍历，使用队列)

这是使用的队列的代码

//队列初始化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;		//tail的后面加上新节点		pq->tail = newnode;		//再让tail指向newnode	}}// 队头出void QueuePop(Queue* pq){ 		assert(pq);	assert(pq->head);	// 1、一个	// 2、多个	if (pq->head->next == NULL)	{ 		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;}

// 层序遍历二叉树  void LevelOrder(BTNode* root)  {       // 定义一个队列q  	Queue q;      // 初始化队列  	QueueInit(&q);      // 如果根节点不为空  	if (root)  	{           // 将根节点入队  		QueuePush(&q, root);  	}      // 当队列不为空时循环  	while (!QueueEmpty(&q))  	{           // 取出队列的队首元素，但不从队列中移除  		BTNode* front = QueueFront(&q);              // 从队列中移除队首元素  		QueuePop(&q);          // 访问队首元素的数据  		printf("%c ", front->data);            // 如果队首元素有左子节点，将左子节点入队  		if (front->left)  		{   			QueuePush(&q, front->left);  		}          // 如果队首元素有右子节点，将右子节点入队  		if (front->right)  		{   			QueuePush(&q, front->right);  		}  	}      // 销毁队列，释放其占用的资源  	QueueDestory(&q); }

新年第一篇！！！

祝大家新年快乐

看到这里了还不给博主扣个：
⛳️ 点赞☀️收藏 ⭐️ 关注！

你们的点赞就是博主更新最大的动力！
有问题可以评论或者私信呢秒回哦。

顶: 33踩: 9151

德薄能鲜网

二叉树详解(深度优先遍历、前序，中序，后序、广度优先遍历、二叉树所有节点的个数、叶节点的个数)

人参与 | 时间：2025-06-24 12:46:55

一、树概念及结构(了解)

1.1树的概念

1.2树的表示

1.3树在实际中的运用（表示文件系统的目录树结构）

二、二叉树概念及结构

2.1概念

2.2现实中的二叉树：

2.3数据结构中的二叉树：

2.4特殊的二叉树：

2.5 二叉树的存储结构

2.51 顺序存储：

2.5.2 链式存储：

2.53 父子存储：

2.6大小堆概念

三、二叉树性质相关选择题练习

四、二叉树的实现

4.1头文件：

4.2Test.c

4.3创建一个二叉树

4.4前序，中序，后序(深度优先遍历)

4.4二叉树所有节点的个数

4.6叶节点的个数

4.7层序遍历(广度优先遍历，使用队列)

评论专区

相关文章