当前位置：首页 > ds >正文

数据结构（8）——二叉树（2）

ds 2025/7/14 9:55:24

前言

本篇文章分别对二叉树的结构进行了解和学习，同时对三种遍历的方法（前序，中序，后序）进行模拟和学习。

一、二叉树的概念

我们首先重新对二叉树的概念进行简要的了解，方便后续的理解和使用。

二叉树是一种树形数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树常用于搜索、排序和递归算法中。

二叉树只有两种情况：

1、空树

2、非空：根节点，根节点的左子树以及根节点的右子树构成的。

如下图所示：

小tip:

这里对于二叉树有一个误区，那就是看的时候不要去看节点，要看一个整体，这个整体就是一棵简单的二叉树，什么简单的二叉树呢，其实就是一个根节点带左右子树的一棵二叉树，如果这样去看的话，会非常容易理解。

二、二叉树的遍历

2.1二叉树遍历定义

二叉树中，其实简单的二叉树在实际中用不到，但是后来的复杂二叉树例如红黑树、B树等用处非常的广泛，它们都是在简单二叉树理解的基础上进行学习的，所以理解简单二叉树也非常的重要。

这里我们要理解并掌握二叉树的遍历，二叉树的遍历（Traversal）是按照某种特定的规则，依次对二叉树中的节点进行相应的的操作，并且每一个节点只操作一次。遍历是二叉树上的重要的运算之一，也是二叉树上进行其它操作的基础。

按照规则，遍历分为三个，分别是先序遍历、中序遍历、后序遍历、层序遍历。

我在记忆的时候，是根据根节点的位置进行区分这三种遍历的。定义简化之后也就是下面：

1、前序遍历(Preorder Traversal 亦称先序遍历）：跟节点、左节点、右节点
2、中序遍历(Inorder Traversal)：左节点、根节点、右节点
3、后序遍历(Postorder Traversal)：左节点、右节点、根节点

4、层序遍历：从第一层开始，从左到右，从上到下依次进行访问

这里就是在一颗简单的二叉树中节点先后访问的顺序。

所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。层序遍历需要用到队列。

2.2二叉树遍历的实现

2.2.1创建二叉树

首先我们先模拟一个二叉树，方便后续的遍历，这里我们使用简单的方法进行创建二叉树，不使用递归，后续会对二叉树的创建进行深入了解。创建的二叉树就是之前给出的样板。

typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;//跟节点struct BinaryTreeNode* left;//左节点struct BinaryTreeNode* right;//右节点
}BTNode;BTNode* BuyNode(BTDataType x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("BTNode malloc fail");return	NULL;}node->data = x;node->left = NULL;node->right = NULL;return node;
}BTNode* CreatTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node5->right = node6;return node1;
}

这里通过一个节点的结构体，使用链表的节点相互连接，即可模拟一个二叉树。这里我们把二叉树用图画出来，包括叶子节点的左右子树（NULL）。

2.2.2前序遍历

前序遍历的顺序是显示根节点，然后是左节点和右节点，这里我们可以根据图来自己先写一下。

我们来分析一下这里的前序遍历，首先根节点位于1，访问左子树，然后看左子树，这里根节点就为2了，然后再访问左子树，根节点就变成了3，再访问左子树时，此时左节点为NULL，也就到头了，所以开始访问右节点，此时位于根节点为3的子树，访问右节点也就是NULL，然后回到根节点为2的子树，此时右节点也是BULL，最后回到了根节点1，访问右子树，此时在右子树里同样是按照跟左右的访问方式进行访问，最后的结果就是：

1 2 3 NULL NULL NULL 4 5 NULL 6 NULL NULL NULL

我们就可以用代码来实现这一访问顺序：

/前序遍历
void PreOrde(BTNode* root)
{if (root == NULL){printf("NULL ");//如果为NULL，就输出NULL，方便对比return;}printf("%d ", root->data);PreOrde(root->left);PreOrde(root->right);
}

因为这里一直在做重复的事，都是先访问根节点然后访问左右节点，所以就可以用递归来搞定。

运行之后的结果如图所示：

可以看出跟我们分析的一模一样，所以这就是前序遍历。

创建栈帧也就是在函数参数为左节点的时候，当到null的时候，返回，也就是回到子问题入口，接着运行下一个子问题，也就是函数参数右节点。

2.2.3中序遍历

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

根据前序遍历即可推出中序遍历，也就是换一下顺序而已。也就是先走左子树，然后根节点，然后右子树，按照这样的走法不断的进行挑选，最后即为最终的正确结果和走法。

2.2.4后序遍历

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

根据前序遍历依旧可以得到后续遍历。

统一运行结果之后最后的是：

这里通过不断创建栈帧实现递归，实际就是解决一个个重复的子问题。

不同的实际问题使用不同的遍历方法。

2.3二叉树节点个数

方法一（全局变量）

我们可以用一个全局的静态变量size来代表元素的个数，通过对二叉树的遍历不断对size进行递增（加加），最后返回即可是元素的个数。

//全局
int size = 0;
//节点个数
int TreeSize(BTNode* root)
{if (root == NULL){return 0;}size++;//中左右进行遍历TreeSize(root->left);TreeSize(root->right);
}

如果使用的是局部的静态变量的话，那么最后就无法进行初始化，如果我们有多个数的情况下，就会出现问题，访问第二个树的时候，此时size是第一个树的元素个数。

方法二（参数传递）

还有一种写法，与上面类似：

就是通过传入参数，参数是对应的一个变量的地址，因为形参的改变不能改变实参，所以要通过地址访问才可以进行修改，此时更加的清晰明了。

int TreeSize(BTNode* root, int* size)
{if (root == NULL){return 0;}++(*size);//中左右进行遍历TreeSize(root->left,size);TreeSize(root->right,size);
}

int main()
{int size1 = 0;TreeSize(tree, &size1);printf("treesize:%d\n", size1);int size2 = 0;TreeSize(tree, &size2);printf("treesize:%d\n", size2);return 0;
}

这样看起来是否更加的整洁呢。

方法三（分治法）

分治法（Divide and Conquer）是一种算法设计策略，将问题分解为多个规模较小的子问题，递归求解子问题后合并结果，最终得到原问题的解。其核心思想是“分而治之”，适用于具有重复子问题性质的任务。

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

先判断根，然后找左子树，再找右子树，最后返回，当然为什么要加一个1呢，因为这里元素要加入自己，最后返回的即就是树的元素个数。

2.4二叉树的高度或者深度

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

该代码实现了一个递归函数TreeHeight，用于计算二叉树的高度（或最大深度）。二叉树的高度定义为从根节点到最远叶子节点的最长路径上的节点数。

算法需要访问二叉树的所有节点一次，时间复杂度为O(n)，其中n为节点数量。空间复杂度取决于递归深度，最坏情况下（树退化为链表）为O(n)。

2.5二叉树第k层节点数

要想解决这个问题，其实使用递归方式实现，核心是通过递归遍历左右子树来累积节点数。

//求第k层的元素个数
int TreeLevel(BTNode* root, int k)
{if (root == NULL)return 0;if (k == 1)return 1;int leftK = TreeLevel(root->left, k - 1);int rightk = TreeLevel(root->right, k - 1);return leftK + rightk;
}