【数据结构】二叉树（binary tree）

摘要：本文系统介绍了二叉树的基本概念、特性和实现方法。阐述了二叉树的定义，性质实现及其证明，然后讲解了三种特殊二叉树的结构特征。此外，详细说明了前序、中序、后序和层序四种遍历算法实现。提供了二叉树创建与销毁的实现。同时还介绍了结点、叶子结点个数、第k层结点的计数，查找值为x的结点等基本操作的递归算法。全文通过图文并茂的方式，全面展示了二叉树这一重要数据结构的关键知识点。

QJXX

1705人浏览 · 2025-08-04 03:02:08

QJXX · 2025-08-04 03:02:08 发布

一、二叉树的定义

二叉树（binary tree）是n（n ≥ 0）个结点的有限集合，该集合由一个根结点和两棵互不相交、分别称为根结点的左子树（left tree）和右子树（right tree）的二叉树组成；如果为空集，称为空二叉树。如图为二叉树的基本结构：

二叉树具有的特点：

每个结点最多有两棵子树，所以二叉树不存在度大于2的结点。

二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。

二、特殊的二叉树

1. 斜树

所有结点都只有左子树的二叉树称为左斜树（left oblique tree）。所有结点都只有右子树的二叉树称为右斜树（right oblique tree）。左斜树和右斜树统称为斜树（oblique tree）。

斜树的示例，如图：

斜树的特点：

每一层只有一个结点；

斜树的结点个数与其深度相同。

2. 满二叉树

在一棵二叉树中，如果分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树称为满二叉树（full binary tree）。换言之，一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。

满二叉树的特点：

叶子结点只能出现在最下一层；

整棵树中只有度为0和度为2的结点。

如果一个二叉树的层数为k，且结点总数是 2^(k-1)，则它就是满二叉树。

3. 完全二叉树

完全二叉树（complete binary tree）是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。

完全二叉树的特点：

深度为k的完全二叉树在k-1层是满二叉树；

叶子结点只能出现在最下两层，且最下层的叶子结点都集中在左侧连续的位置；

如果有度为1的结点，只可能有一个，且该结点只有左孩子。

完全二叉树和非完全二叉树的示例：

三、二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 $2^{n-1}$ 个结点。

2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 $2^h-1$

3. 对任何一棵二叉树, 如果度为0其叶结点个数为 $n_{1}$ , 度为2的分支结点个数为 $n_{2}$ ,则有 $n_{0}=n_{2}+1$
证明：

设n为二叉树的结点总数， $n_{1}$ 为二叉树中度为1的结点个数,因为二叉树中所有结点的度均小于或等于2，则有：

$n=n_{0}+n_{1}+n_{2}$

对于二叉树的分枝。除了根结点外，其余结点都有唯一的分枝进入，因此，对于有n个结点的二叉树，其分支数为 $n-1$ ，这些分支是由度为1和度为2的结点射出的，一个度为1的结点射出一个分枝，一个度为2的结点射出两个分枝。所以有：

$n-1=n_{1}+2n_{2}$

由上述两个式子可以得出： $n_{0}=n_{2}+1$ ，得证。

4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度为：

$h=\log _{2}(n+1)$

，具有n个结点的完全二叉树的深度为：

$h=\lfloor \log_2 n \rfloor+1$

证明：

设具有n个结点的完全二叉树的深度为k，如图：

则有： $2_{k-1}\leqslant n< 2_{k}$

取对数： $k-1\leqslant \log _2 n < k$

得： $\log _2 n< k \leqslant \log _2 n +1$

由于k是整数，则必有： $k=\lfloor \log_2 n \rfloor+1$

5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为 $i( 1 \leqslant i \leqslant n )$ 的结点有：

若 $i>0$ ， $i$ 位置节点的双亲序号： $(i-1)/2$ ；当 $i=0$ ， $i$ 为根结点编号，无双亲结点

若 $2i+1<n$ ，左孩子序号： $2i+1$ ，若 $2i+1 \geqslant n$ 否则无左孩子

若 $2i+2<n$ ，右孩子序号： $2i+2$ ，若 $2i+2 \geqslant n$ 否则无右孩子

四、二叉树的实现

实现二叉树最常用的方法就是递归。

1. 二叉树的顺序存储

二叉树的顺序存储是用一维数组存储二叉树的结点，用下标表示结点之间的逻辑关系---父子关系。

如图：

可以发现，普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。但完全二叉树更适合使用顺序结构存储，如图所示：

这样才可以将数组空间更加充分的利用。通常要实现这种顺序存储是用堆来实现的。

需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

实现链接：

【数据结构】堆（heap）-CSDN博客https://blog.csdn.net/jx29929Q9Q9/article/details/149654106?spm=1001.2014.3001.5502

2. 二叉树的链接存储

二叉树的链接存储一般采用二叉链表（binary linked list）来实现。其基本思路是令二叉树的每个结点对应一个链表结点，链表结点中除了存放二叉树结点的数据信息外，还要设置指向它左右孩子结点的指针。如图：

结点结构：

二叉链表的存储结构定义：

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

3. 二叉树的遍历

（1）前序遍历

前序遍历的顺序是：根-->左子树-->右子树。

如图是前序遍历递归访问一个树的结点的示意图：

C语言代码实现：

// 二叉树前序遍历 
void PreOrder(BTNode* root)
{
	if (root == NULL)
		return;
	printf("%c ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

运行结果：

代码实现的递归展开图如下：

（2）中序遍历

中序遍历的顺序是：左子树-->根-->右子树。

如图是中序遍历递归访问一个树的结点的示意图：

C语言代码实现：

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

运行结果：

代码实现的递归展开图如下：

（3）后序遍历

后序遍历的顺序是：左子树-->右子树-->根。

如图是后序遍历递归访问一个树的结点的示意图：

C语言代码实现：

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

运行结果：

代码实现的递归展开图如下：

（4）层序遍历

层序遍历就是：从第一层开始一层一层依次向下，每一层从左到右依次访问。

二叉树的层序遍历是通过队列来实现的。如图是利用队列实现层序遍历的过程：

C语言代码实现：

// 二叉树层序遍历
void LevelOrder(BTNode* root)
{
	BTNode* cur, * Q[100];
	int front = -1, rear = -1;
	if (root != NULL)
	{
		Q[++rear] = root;
	}
	while (front != rear)
	{
		//出队
		cur = Q[++front];
		printf("%c ", cur->data);
		//入队孩子结点
		if (cur->left)
		{
			Q[++rear] = cur->left;
		}
		if (cur->right)
		{
			Q[++rear] = cur->right;
		}
	}
	printf("\n");
}

运行结果：

4. 二叉树的创建

二叉树可以通过前序遍历的数组如"ABD##E#H##CF##G##"构建二叉树。它的C语言实现如下：

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	if (a[*pi] == '#')
	{
		(*pi)++;
		root = NULL;
	}
	else
	{
		root->data = a[*pi];
		(*pi)++;
		root->left = BinaryTreeCreate(a, n, pi);
		root->right = BinaryTreeCreate(a, n, pi);
	}	
	return root;
}

5. 二叉树销毁

二叉树的销毁和中序差不多，先销毁左子树，再销毁右子树，最后销毁结点。则C语言实现如下：

void BinaryTreeDestory(BTNode** proot)
{
	if (*proot == NULL)
		return;
	BinaryTreeDestory(&(*proot)->left);
	BinaryTreeDestory(&(*proot)->right);
	free(*proot);
	*proot = NULL;
}

五、二叉树其他算法

1. 二叉树结点个数

统计二叉树的结点个数算法是通过递归实现的。

这个算法要返回的是总的结点个数。如果一棵树只有一个根结点，那么就返回1；如果不止有一个根结点，那么结点数就是：根结点左子树的结点数+根结点右子树的结点数+根结点本身。二根结点的左子树又可以看成一棵树，右子树也一样。

所以：二叉树的结点总数 = 左子树结点总数 + 右子树结点总数 + 1（根节点）。可以按照这种方法一直递归下去求结果，直到遇到了空树（即结点为NULL）时，就返回0（因为空树的结点个数为0）。

递归终止条件：

如果当前结点是空树，返回 0（没有结点了）。

递归情况：

递归计算 左子树结点总数 + 右子树结点总数 + 1（根节点）之和，并返回。

则C语言实现：

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

2. 二叉树叶子结点的个数

叶子结点是指在一棵树中左右孩子均为空的结点。

我们知道二叉树中所有叶子结点的个数 = 左子树的叶子结点数 + 右子树的叶子结点数，这也是使用递归来解决的。

递归终止条件：

如果当前结点是空树，返回 0（没有叶子结点）。

如果当前结点的左孩子结点和右孩子结点均为空，说明它是叶子结点，返回 1。

递归情况：

如果当前结点不是叶子结点，则递归计算其左子树和右子树的叶子结点数之和，并返回。

则C语言实现：

int BinaryTreeLeafSize(BTNode* root)
{
	//当前结点是空树,无叶子结点
	if (root == NULL)
	{
		return 0;
	}
	//当前结点的左孩子结点和右孩子结点均为空
	if (root->left == NULL && root->right==NULL)
	{
		return 1;
	}
	//有一个孩子为空的情况
	if (root->left == NULL)
	{
		return BinaryTreeLeafSize(root->right);
	}
	if (root->right == NULL)
	{
		return BinaryTreeLeafSize(root->left);
	}
	//返回左子树和右子树的叶子结点数之和
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

3. 二叉树第k层结点个数

方法：二叉树第 k 层的结点个数 = 左子树的第 k-1 层结点个数 + 右子树的第 k-1 层结点个数。--- 递归

递归终止条件：

如果当前结点是空树：返回 0（没有结点）。

如果 k = 1，该层是目标层：返回 1（当前结点就是第 k 层的一个结点）。

递归情况：

计算其左子树和右子树的的 k - 1 层的结点数之和，并返回。

则C语言实现：

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	//当前结点是空树
	if (root == NULL)
	{
		return 0;
	}
	//该结点处于目标层
	if (k == 1)
	{
		return 1;
	}
	//返回结点的左右子树第k-1层结点数目之和
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

4. 二叉树查找值为x的结点

使用递归算法。基本思路如下：

递归终止条件：

如果当前节点为NULL，返回 NULL（表示未找到）。

如果当前节点的值等于 x，返回该节点。

递归查找情况：

先在左子树中查找 x。

如果左子树没找到（左子树中查找返回空），再在右子树中查找 x。

则C语言实现：

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	//遇到空结点，没找到
	if (root == NULL)
	{
		return NULL;
	}
	//找到了
	if (root->data == x)
	{
		return root;
	}
	//先查找左子树
	BTNode* ret = BinaryTreeFind(root->left, x);
	if (ret)
	{
		return ret;
	}
	//再查找右子树
	ret = BinaryTreeFind(root->left, x);
	if (ret)
	{
		return ret;
	}
	//没找到
	return NULL;
}

感谢各位观看！希望能多多支持！