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

树的4种遍历

news 来源：原创 2024/9/22 21:17:46

树的四种遍历方式的总结

树的四种遍历方式（前序遍历、中序遍历、后序遍历和层序遍历）是理解和操作二叉树的基础。以下是这四种遍历方式的总结：

1. 前序遍历（Pre-order Traversal）

访问顺序：根节点 -> 左子树 -> 右子树
递归实现简单直观，先访问根节点，然后递归遍历左子树，最后递归遍历右子树。
非递归实现通常使用栈来辅助遍历，先将根节点压栈，然后在循环中出栈并访问当前节点，接着将右子节点和左子节点依次压栈（注意顺序）。

2. 中序遍历（In-order Traversal）

访问顺序：左子树 -> 根节点 -> 右子树
在二叉搜索树中，中序遍历的结果是一个有序序列。
递归实现时，先递归遍历左子树，然后访问根节点，最后递归遍历右子树。
非递归实现同样使用栈，但需要标记节点来源（是否来自左子树）来确保先遍历左子树。

3. 后序遍历（Post-order Traversal）

访问顺序：左子树 -> 右子树 -> 根节点
递归实现简单，但非递归实现相对复杂。
非递归实现通常使用两个栈或结合栈和指针来追踪节点和它们的子节点，确保在访问根节点之前已经遍历了左右子树。

4. 层序遍历（Level-order Traversal 或广度优先遍历，Breadth-First Traversal）

访问顺序：从上到下，从左到右（即按层次顺序）
使用队列来辅助实现，先将根节点入队，然后在循环中每次出队一个节点并访问，接着将其非空子节点依次入队（通常先左后右）。
层序遍历在二叉树的层次结构分析、图的广度优先搜索等场景中非常有用。
注意事项
递归实现简洁明了，但可能导致栈溢出，特别是在处理深度很大的树时。
非递归实现通常使用栈或队列等数据结构来辅助遍历，需要注意数据结构的正确操作和管理。
在遍历过程中，要时刻注意空指针的情况，避免访问空指针导致的程序崩溃。
根据不同的应用场景选择合适的遍历方式，例如在二叉搜索树中，中序遍历的结果是有序的，而在分析树的层次结构时，层序遍历更为直观。

以下是这四种遍历方式的C语言实现示例：

1. 定义二叉树节点


#include <stdio.h>
#include <stdlib.h>typedef struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
} TreeNode;

2. 前序遍历（根-左-右）

void preOrderTraversal(TreeNode* root) {if (root == NULL) return;printf("%d ", root->val);preOrderTraversal(root->left);preOrderTraversal(root->right);
}

3. 中序遍历（左-根-右）

void inOrderTraversal(TreeNode* root) {if (root == NULL) return;inOrderTraversal(root->left);printf("%d ", root->val);inOrderTraversal(root->right);
}

4. 后序遍历（左-右-根）

void postOrderTraversal(TreeNode* root) {if (root == NULL) return;postOrderTraversal(root->left);postOrderTraversal(root->right);printf("%d ", root->val);
}

5. 层序遍历（广度优先遍历）

在C语言中实现二叉树的层序遍历（广度优先遍历）需要借助队列数据结构。由于C标准库没有直接提供队列，我们可以使用数组或链表配合指针来模拟队列的行为。以下是一个使用数组模拟队列实现层序遍历的示例：

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

// 定义二叉树节点

typedef struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
} TreeNode;

// 创建一个新节点

TreeNode* createNode(int val) {TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));if (!newNode) {exit(EXIT_FAILURE);}newNode->val = val;newNode->left = NULL;newNode->right = NULL;return newNode;
}

// 层序遍历（广度优先遍历）

void levelOrderTraversal(TreeNode* root) {if (root == NULL) return;// 创建一个队列TreeNode* queue[1000]; // 假设队列最大长度为1000int front = 0, rear = 0;// 将根节点入队queue[rear++] = root;while (front < rear) {// 出队一个节点TreeNode* node = queue[front++];printf("%d ", node->val);// 将左孩子和右孩子入队if (node->left) {queue[rear++] = node->left;}if (node->right) {queue[rear++] = node->right;}}
}int main() {// 创建一个简单的二叉树进行测试TreeNode* root = createNode(1);root->left = createNode(2);root->right = createNode(3);root->left->left = createNode(4);root->left->right = createNode(5);// 层序遍历二叉树levelOrderTraversal(root);// 清理内存（这里省略了详细的内存清理代码）return 0;
}

在上面的代码中，我们定义了一个固定大小的队列数组queue，以及两个指针front和rear来模拟队列的头部和尾部。需要注意的是，这里假设了队列的最大长度为1000，但在实际应用中，我们可能需要动态分配内存或使用链表来实现一个更灵活的队列。

在levelOrderTraversal函数中，我们首先将根节点入队，然后进入一个循环，直到队列为空。在每次循环中，我们出队一个节点并打印其值，然后将该节点的左孩子和右孩子（如果存在）入队。这样，我们就能按照层次顺序遍历整个二叉树。

注意：上面的层序遍历示例使用了C++的std::queue，因为C标准库并没有直接提供队列的数据结构。在纯C中，你需要自己实现一个队列或者使用数组来模拟队列。

在实际使用时，你可以根据需要选择适合的遍历方式。