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

数据结构-链式二叉树-四种遍历

news 2025/8/4 13:10:39

博客主页：【夜泉_ly】
本文专栏：【数据结构】
欢迎点赞👍收藏⭐关注❤️

数据结构-链式二叉树-四种遍历

1.前言
2.前、中、后序遍历
- 2.1前序遍历
- 2.1中、后序遍历
3.层序遍历
- 3.1递归实现
- 3.2队列实现
- - 关于在`Pop`之后为什么还能用`tmp`访问节点？
  - 关于都已经把队列`Pop`为空了为什么还要`QueueDestroy`？
4.浅谈DFS与BFS

1.前言

在我之前的文章数据结构-堆-详解中，我对堆这种特殊的完全二叉树做了详细介绍。
完全二叉树非常适合用数组存储，但一般的二叉树呢？如下图所示：
在这里插入图片描述
可以发现，普通二叉树若使用数组存储，会浪费大量空间，这时，链式存储结构成为更好的选择。
在这种结构中，每个节点应包含自身所存储的数据，以及指向左右子树的指针。
可以通过以下结构体定义二叉树节点：

typedef char BTDataType;typedef struct TreeNode
{BTDataType val;struct TreeNode* left;struct TreeNode* right;
}TreeNode;

为了便于理解，我手搓了一个简单的二叉树：
在这里插入图片描述
代码如下：

TreeNode* BuyTreeNode(BTDataType x)
{TreeNode* tmp = (TreeNode*)malloc(sizeof(TreeNode));if (!tmp){perror("BuyTreeNode::malloc");return NULL;}tmp->val = x;tmp->left = NULL;tmp->right = NULL;return tmp;
}
TreeNode* CreatBinaryTree()
{TreeNode* root = BuyTreeNode('a');TreeNode* n1 = BuyTreeNode('b');TreeNode* n2 = BuyTreeNode('c');TreeNode* n3 = BuyTreeNode('d');TreeNode* n4 = BuyTreeNode('e');TreeNode* n5 = BuyTreeNode('f');TreeNode* n6 = BuyTreeNode('g');root->left = n1;root->right = n2;n1->left = n3;n1->right = n4;n2->left = n5;n2->right = n6;return root;
}

注意：这并不是二叉树真正的创建方法，等对于二叉树的结构有更深入的了解后，再讲创建。

在对二叉树进行各项操作时，应对其结构有明确的认识：
在这里插入图片描述
对任意一个二叉树，都由 根、左子树、右子树 组成。
而左右子树，也是二叉树，也有对应的 根、左子树、右子树。
因此，二叉树的定义是递归的，在对二叉树进行处理时也常常使用递归。
而对二叉树的递归操作也应以 根、左子树、右子树 为基础展开。

2.前、中、后序遍历

2.1前序遍历

二叉树的前序遍历：先访问根，再遍历左子树，最后遍历右子树。

void BinaryTreePrevOrder(TreeNode* root)
{if (!root){printf("NULL ");return;}printf("%c ", root->val);BinaryTreePrevOrder(root->left);BinaryTreePrevOrder(root->right);
}

先判断根，如果为空，就打印NULL并返回；
若不为空，则先打印根的值，再遍历左子树，最后遍历右子树。

在二叉树这块，可以先画画逻辑结构图：
在这里插入图片描述
虽然画的不全，但大概就是这么个意思。
如果难以理解时可以再画画递归展开图：把代码是怎么一行行执行的给画出来。
经过分析，可知打印结果应该是：a b d NULL NULL e NULL NULL c f NULL NULL g NULL NULL。
在这里插入图片描述

也可以选择不打印空，结果是：a b d e c f g。
在这里插入图片描述

在画过图后，应对二叉树的遍历有更清楚的认识：
在打印d后为什么直接打印e?
并非是从d的节点直接到e的节点，
而是先访问d的两个空的左右子树，d结束了左右子树的遍历，返回到b。
此时b结束了它的左子树的遍历，于是开始遍历右子树，然后才到了e处。

2.1中、后序遍历

二叉树的中序遍历：先遍历左子树，再访问根，最后遍历右子树。

void BinaryTreeInOrder(TreeNode* root)
{if (!root){printf("NULL ");return;}BinaryTreeInOrder(root->left);printf("%c ", root->val);BinaryTreeInOrder(root->right);
}

二叉树的后序遍历：先遍历左子树，再遍历右子树，最后访问根。

void BinaryTreePostOrder(TreeNode* root)
{if (!root){printf("NULL ");return;}BinaryTreePostOrder(root->left);BinaryTreePostOrder(root->right);printf("%c ", root->val);
}

此时，可以写个代码测试一下：

int main()
{TreeNode* root = CreatBinaryTree();printf("BinaryTreePrevOrder:");BinaryTreePrevOrder(root);printf("\nBinaryTreeInOrder:");BinaryTreeInOrder(root);printf("\nBinaryTreePostOrder:");BinaryTreePostOrder(root);return 0;
}

运行结果：
在这里插入图片描述
也可以不打印NULL：

3.层序遍历

就是从上至下从左至右的遍历：
在这里插入图片描述

3.1递归实现

此实现方法并不重要，所以略讲。
先求个高度：

int TreeHeight(TreeNode* root)
{if (!root)return 0;int leftheight = TreeHeight(root->left);int rightheight = TreeHeight(root->right);return leftheight > rightheight ? 1 + leftheight : 1 + rightheight;
}

再写个打印第k层元素的函数：

void BinaryTreeLevelPrint(TreeNode* root, int level)
{if (!root)return;if (level == 1)printf("%c ", root->val);else{BinaryTreeLevelPrint(root->left, level - 1);BinaryTreeLevelPrint(root->right, level - 1);}
}

最后组合起来，即一层一层的打印：

void BinaryTreeLevelOrder(TreeNode* root)
{int level = TreeHeight(root);for (int i = 1; i < level; i++){BinaryTreeLevelPrint(root, i);}
}

测试一下：

int main()
{TreeNode* root = CreatBinaryTree();printf("BinaryTreeLevelOrder:");BinaryTreeLevelOrder(root);return 0;
}

结果：
在这里插入图片描述

3.2队列实现

二叉树层序遍历使用递归比较麻烦，且不太直观，因此，通常使用另一种方法，即队列：

先将根节点入队列
将队首的节点出队列，并带入当前节点的两个非空子节点
重复
再重复
队列为空，停止

其中，有关队列的函数可直接CV --> 数据结构-栈、队列-详解。

需注意的是，存入队列的是指向节点的指针，因此，需改变一下队列存储的数据类型：

//typedef int QDatatype;
typedef TreeNode* QDatatype;

代码实现：

void BinaryTreeLevelOrder(TreeNode* root)
{Queue q;QueueInit(&q);if (!root);QueuePush(&q, root);while (!QueueEmpty(&q)){TreeNode* tmp = QueueFront(&q);QueuePop(&q);printf("%c ", tmp->val);if (tmp->left)QueuePush(&q, tmp->left);if (tmp->right)QueuePush(&q, tmp->right);}printf("\n");QueueDestroy(&q);
}